Office中国论坛/Access中国论坛

标题: 【原创】测一下Hashtable的排序规则 [打印本页]
作者: faunus    时间: 2014-2-24 11:16
标题: 【原创】测一下Hashtable的排序规则
[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<==指针移动顺序  

  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    时间: 2014-2-24 11:16
结果如下：

============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



欢迎光临 Office中国论坛/Access中国论坛 (http://www.office-cn.net/) Powered by Discuz! X3.3