诡异的Hashtable
工作之余,本人想验证测试Hashtable迭代时是按什么顺序输出的.结果却令人费解.
废话不说,先贴代码.
- C# code
using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Collections;namespace ConsoleApplication1{ class Program { static void Main(string[] args) { //测试A Hashtable hashA = new Hashtable(); hashA.Add("first", "顺序1"); hashA.Add("third", "顺序2"); hashA.Add("second", "顺序3"); Console.WriteLine("HashtableA"); foreach (string key in hashA.Keys) { Console.WriteLine("key:{0}--value:{1}", key, hashA[key].ToString()); } //结果 // key:first--value:顺序1 // key:third--value:顺序2 // key:second--value:顺序3 //断言A:Hashtable的迭代与添加键值对时的先后关系有关。 //测试B Hashtable hashB = new Hashtable(); hashB.Add("1", "顺序1"); hashB.Add("3", "顺序2"); hashB.Add("2", "顺序3"); Console.WriteLine("HashtableB"); foreach (string key in hashB.Keys) { Console.WriteLine("key:{0}--value:{1}", key, hashB[key].ToString()); } //结果 // key:1--value:顺序1 // key:2--value:顺序3 // key:3--value:顺序2 //断言B:居然按键的顺序输出的？推翻断言A. //测试C Hashtable hashC = new Hashtable(); hashC.Add("1", "顺序1"); hashC.Add("6", "顺序2"); hashC.Add("3", "顺序3"); Console.WriteLine("HashtableB"); foreach (string key in hashC.Keys) { Console.WriteLine("key:{0}--value{1}", key, hashC[key].ToString()); } //结果 // key:6--value:顺序2 // key:1--value:顺序1 // key:3--value:顺序3 //断言C:无语中....猜测会不会按HashCode输出的,决定输出HashCode看看 Console.WriteLine("输出各个key的HashCode"); Console.WriteLine("1: {0}","1".GetHashCode()); Console.WriteLine("2: {0}", "2".GetHashCode()); Console.WriteLine("3: {0}", "3".GetHashCode()); Console.WriteLine("6: {0}", "6".GetHashCode()); //结果 //1: -842352753 //2: -842352754 //3: -842352755 //6: -842352758 //再输出以组合字符串的key Console.WriteLine("输出各个HashA中key的HashCode"); Console.WriteLine("first: {0}", "first".GetHashCode()); Console.WriteLine("third: {0}", "third".GetHashCode()); Console.WriteLine("second: {0}", "second".GetHashCode()); //结果 //first: -1920740948 //third: -1952578413 //second: -792817032 //直接昏菜。。 //备注:经测试,使用int型作为key时,迭代时一定会按key的降序输出value. } }}诡异:Hashtable进行迭代时,到底是按什么输出的?
[解决办法]
根据 http://msdn.microsoft.com/en-us/library/ms379571%28VS.80%29.aspx#datastructures20_2_topic5
hash function不是简单的 H(key) = GetHash(key)
而是
H(key) = [GetHash(key) + 1 + (((GetHash(key) >> 5) + 1) % (hashsize 1))] % hashsize
或者
Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize 1)))] % hashsize
[解决办法]
[解决办法]
呵呵，我正好这两天在研究Hashcode
看到你的测试想法，给我一些启发：
测试后，发现实践与理论完全吻合（当然目前是比较简单的情况）
代码如下：
- C# code
using System;
using System.Collections;
class MyClass
{
static readonly int[] primes =
{
3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369
};
static int GetHashcode <T>(T key, int k, int hashsize)
{
//Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize 1)))] % hashsize
int k_code = key.GetHashCode();
return Math.Abs(k_code + k * (1 + (((k_code >> 5) + 1) % (hashsize - 1)))) % hashsize;
}
static void Main(string[] args)
{
//public Hashtable(int capacity, float loadFactor);
//Hashtable hs = new Hashtable { 1, 2, 3, 4, 5, };
//测试C
Hashtable hashC = new Hashtable(7);
hashC.Add("5", "顺序1");// <-HeadPos
hashC.Add("1", "顺序1");
hashC.Add("6", "顺序2");
hashC.Add("4", "顺序2");
hashC.Add("3", "顺序3");
Console.WriteLine("========HashtableB=========");
foreach (string key in hashC.Keys)
{
Console.WriteLine("Hk(key):{0:0000},Key:{1}", GetHashcode(key, 1, 7), key);
}
//0123456 <==capacity(容量)=7
// 1 3456 <==HeadPos=Hk(5)=5
// ^
// 3 4512 <==指针移动顺序
Console.ReadKey();
}
}
[解决办法]
哈希表散列存储的吧，比如散列码是7;那下面数的存储位置类似这样的：1,5,8,4,9,11,14
这里有7个数，假如有10个空间存放。
1%7=1: X1XXXXXXXX
5%7=5: X1XXX5XXXX
8%7=1: X18XX5XXXX
4%7=4: X18X45XXXX
9%7=2: X18945XXXX
11%7=4:X18945(11)XXXX
14%7=0:(14)18945(11)XXXX
X表示空。hash表大概像这样存的。
[解决办法]
[解决办法]
满三帮顶了：
http://topic.csdn.net/u/20090825/16/725bc96a-33f9-4c63-85ef-01d22d6c1ed2_3.html
顺一个string类型的hashcode算法
- C# code
using System;namespace ConsoleApplication8{ class Program { //项目属性对话框->配置属性->生成->允许不安全代码块->设为true static public unsafe int DotNetHash(string str) { fixed (char* charPtr = new String(str.ToCharArray())) { int hashCode = (5381 << 16) + 5381; int numeric = hashCode; int* intPtr = (int*)charPtr; for (int i = str.Length; i > 0; i -= 4) { hashCode = ((hashCode << 5) + hashCode + (hashCode >> 27)) ^ intPtr[0]; if (i <= 2) break; numeric = ((numeric << 5) + numeric + (numeric >> 27)) ^ intPtr[1]; intPtr += 2; } return hashCode + numeric * 1566083941; } } static void Main(string[] args) { string test = "test it!"; Console.WriteLine(test.GetHashCode()); Console.WriteLine(DotNetHash(test)); Console.ReadKey(); } }}
[解决办法]
满三了，借本贴记一下：
跟据java代码改的分离链接散列法
separate chaining hashing
- C# code
//Hash table with separate chainingusing System;namespace ConsoleApplication8{ public class Link { private int data; public Link next; public Link(int d){data = d;} public int getKey(){return data;} public void displayLink(){Console.WriteLine(data + " ");} } class SortedList { private Link first; public SortedList(){first = null;} public void insert(Link theLink) { int key = theLink.getKey(); Link previous = null; // start at first Link current = first; // until end of list, //or current bigger than key, while (current != null && key > current.getKey()) { previous = current; current = current.next; // go to next item } if (previous == null) // if beginning of list, first = theLink; else // not at beginning, previous.next = theLink; theLink.next = current; } public void delete(int key) { Link previous = null; Link current = first; while (current != null && key != current.getKey()) { previous = current; current = current.next; } // disconnect link if (previous == null) // if beginning of list delete first link first = first.next; else // not at beginning previous.next = current.next; //delete current link } public Link find(int key) { Link current = first; while (current != null && current.getKey() <= key) { // or key too small, if (current.getKey() == key) // found, return link return current; current = current.next; // go to next item } return null; // cannot find it } public void displayList() { Console.WriteLine("List: "); Link current = first; while (current != null) { current.displayLink(); current = current.next; } Console.WriteLine(""); } } public class HashChain { private SortedList[] hashArray; private int arraySize; public HashChain(int size) { arraySize = size; hashArray = new SortedList[arraySize]; for (int i = 0; i < arraySize; i++) hashArray[i] = new SortedList(); } public void displayTable() { for (int j = 0; j < arraySize; j++) { Console.WriteLine(j + ". "); hashArray[j].displayList(); } } public int hashFunc(int key) { return key % arraySize; } public void insert(Link theLink) { int key = theLink.getKey(); int hashVal = hashFunc(key); hashArray[hashVal].insert(theLink); } public void delete(int key) { int hashVal = hashFunc(key); // hash the key hashArray[hashVal].delete(key); } public Link find(int key) { int hashVal = hashFunc(key); // hash the key Link theLink = hashArray[hashVal].find(key); // get link return theLink; } public static void main(String[] args) { int aKey; Link dataItem; int size, initSize, keysPerCell = 100; size = 100; initSize = 10; HashChain hashTable = new HashChain(size); for (int i = 0; i < initSize; i++) { Random r = new Random(); aKey = (int)(r.Next() * keysPerCell * size); dataItem = new Link(aKey); hashTable.insert(dataItem); } hashTable.displayTable(); aKey = 100; dataItem = new Link(aKey); hashTable.insert(dataItem); aKey = 100; hashTable.delete(aKey); aKey = 50; dataItem = hashTable.find(aKey); if (dataItem != null) Console.WriteLine("Found " + aKey); else Console.WriteLine("Could not find " + aKey); } } class Test { static void Main(string[] args) { HashChain hc = new HashChain(3); Link link1 = new Link(1); Link link2 = new Link(3); Link link3 = new Link(2); hc.insert(link1); hc.insert(link2); hc.insert(link3); } }}