【原创】测一下Hashtable的排序规则

faunus

[size=14.399999618530273px]表面上是无规律的，实际上还是有规律的。
[size=14.399999618530273px]

[size=14.399999618530273px]

1. using System;
   
2. using System.Collections;
   
3. class MyClass
   
4. {
   
5.     static readonly int[] primes =
   
6.      {
   
7.         3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
   
8.         1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
   
9.         17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
   
10.         187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
    
11.         1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369
    
12.      };
    
13.     static int GetHashcode(object key, int k, int hashsize)
    
14.     {
    
15.         //Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize
    
16.         int k_code = key.GetHashCode();
    
17.         return Math.Abs(k_code + k * (1 + (((k_code >> 5) + 1) % (hashsize - 1)))) % hashsize;
    
18.     }
    
19.     static void Print(Hashtable hs)
    
20.     {
    
21.         Console.WriteLine("============Hashtable Test=================");
    
22.         foreach (string key in hs.Keys)
    
23.         {
    
24.             Console.WriteLine("Hk(key):{0:0000},Key:{1}", GetHashcode(key, 1, 7), key);
    
25.         }
    
26.     }
    
27.     static void Main(string[] args)
    
28.     {
    
29.         //public Hashtable(int capacity, float loadFactor);
    
30.         //Hashtable hs = new Hashtable { 1, 2, 3, 4, 5, };
    
31.         //测试C
    
32.         Hashtable hashC = new Hashtable(7);
    
33.         hashC.Add("5", "顺序1");
    
34.         hashC.Add("1", "顺序1");
    
35.         hashC.Add("6", "顺序2");
    
36.         hashC.Add("4", "顺序2");
    
37.         hashC.Add("3", "顺序3");//<-EndPos(操作完后移动到下一个位置,即"4")
    
38.         Print(hashC);
    
39.         Console.WriteLine("add all");
    
40.         //0123456<==capacity(容量)=7
    
41.         // 1 3456<==最后一次操作的下一位置
    
42.         //   ^^
    
43.         // 4 5123<==指针移动顺序  
    
44. 
    
45.         hashC.Remove("0");
    
46.         Print(hashC);
    
47.         Console.WriteLine("hashC.Remove('0');");
    
48.         hashC.Remove("0");
    
49.         Print(hashC);
    
50.         Console.WriteLine("hashC.Remove('0');");
    
51.         hashC.Remove("4");//删除指针下移
    
52.         Print(hashC);
    
53.         Console.WriteLine("hashC.Remove('4');");
    
54.         hashC.Remove("0");
    
55.         Print(hashC);
    
56.         Console.WriteLine("hashC.Remove('4');");
    
57.         hashC.Add("2", "---");//添加不移动指针?!这次没动
    
58.         Print(hashC);
    
59.         Console.WriteLine("hashC.Add('2');");
    
60.         
    
61.         Console.ReadKey();
    
62.     }
    
63. }

复制代码

[size=14.399999618530273px]

faunus

结果如下：

============Hashtable Test=================
Hk(key):0004,Key:4
Hk(key):0005,Key:5
Hk(key):0006,Key:6
Hk(key):0001,Key:1
Hk(key):0003,Key:3
add all
============Hashtable Test=================
Hk(key):0004,Key:4
Hk(key):0005,Key:5
Hk(key):0006,Key:6
Hk(key):0001,Key:1
Hk(key):0003,Key:3
hashC.Remove('0');
============Hashtable Test=================
Hk(key):0004,Key:4
Hk(key):0005,Key:5
Hk(key):0006,Key:6
Hk(key):0001,Key:1
Hk(key):0003,Key:3
hashC.Remove('0');
============Hashtable Test=================
Hk(key):0005,Key:5
Hk(key):0006,Key:6
Hk(key):0001,Key:1
Hk(key):0003,Key:3
hashC.Remove('4');
============Hashtable Test=================
Hk(key):0005,Key:5
Hk(key):0006,Key:6
Hk(key):0001,Key:1
Hk(key):0003,Key:3
hashC.Remove('4');
============Hashtable Test=================
Hk(key):0005,Key:5
Hk(key):0006,Key:6
Hk(key):0001,Key:1
Hk(key):0002,Key:2
Hk(key):0003,Key:3
hashC.Add('2');

[1]测试了键值hashcode无冲突情况
[2]容量指定为第一个给定素数=7
[3]内部停留指针所在的位置：最后操作的位置向下移动一格
[4]Foreach时，从HeadPos开始，按顺序输出，容器可以看作一个环形队列
[5]字符的hashcode与Hk(key)完全一样



Hashcode分配规律:
[1]默认值的情况
3(素数表中的第一个情况)



[2]给定初始值的情况
如果给定初始值，它会在素数表中找比设置大小大的数的最小值。



[3]自然增长的情况
首个3，再表中取比这个数的两倍大的最小值，依次类推。

3 -> 7 -> 17 -> 37 -> 89 -> 197 -> 431 -> 919 -> 1931 -> 4049 -> 8419 -> 17519 -> 36353 -> 75431 -> ...


[4]给定初始值自然增长情况
参照[3],区别在于首字符的设定

[5]素数间隔
从23开始,后一个素数/前一个素数,约等于1.2