白话算法(6.4) 能让 Dictionary 比 Hashtable 慢 600 倍？&
泛型 Dictionary 和 Hashtable 都是散列表的一种实现。只不过 Hashtable 使用的是双重散列法（开放寻址法的一种），而 Dictionary 使用的是除法散列法+链接法处理碰撞。知道了这一点，就可以写一个让 Dictionary 出丑的测试：
view sourceprint?01 int SIZE = 10103;
02 IDictionary<int, int> dict = new Dictionary<int, int>(SIZE);
03 Hashtable h = new Hashtable(SIZE);
04
05 for (int i = 0; i < 10000; i++)
06 {
07 dict.Add(i*SIZE, i);
08 h.Add(i*SIZE, i);
09 }
10
11 Stopwatch t = new Stopwatch();
12
13 t.Reset();
14 t.Start();
15 // 为了让测试效果明显，重复10万次查询
16 for (int i = 0; i < 100000; i++)
17 {
18 dict.ContainsKey(SIZE);
19 }
20 t.Stop();
21 Console.WriteLine("Dictionary:" + t.Elapsed.TotalMilliseconds.ToString() + "毫秒");
22
23 t.Reset();
24 t.Start();
25 // 为了让测试效果明显，重复10万次查询
26 for (int i = 0; i < 100000; i++)
27 {
28 h.ContainsKey(SIZE);
29 }
30 t.Stop();
31 Console.WriteLine("Hashtable:" + t.Elapsed.TotalMilliseconds.ToString() + "毫秒");
测试结果：
怎么样，效果很惊人吧？当然，计算倍数并没有什么实际意义，只不过听起来很恐怖，比较容易吸引眼球罢了。而且，这个测试对 Dictionary 是不公平的，毕竟是我故意制造了一个让 Dictionary 产生1万次碰撞的输入。一般情况下，Dictionary 和 Hashtable 的效率是不相上下的，在 Key 是原生类型的情况下 Dictionary 还略快一些。不过，这个测试也说明开放寻址法自有其优点，毕竟我们难以制造一个能让 Hashtable 出这么大的丑的测试。
上面那个测试让人心中不爽，但是在实际使用时一般不会有太大问题。当容量比较小时，使用除法散列法确实容易产生碰撞，但是就算达到极端的 O(n) 查找又如何——把百八十个项全部遍历一遍也用不了多少时间。当容量较大时，例如容量是 10103 时，要每隔 10103 个数字才发生一次碰撞，如果可以假设实际添加到字典中的项都是比较靠近的，就不会发生大量碰撞。
在阅读 Dictionary 源代码之前，我们先来做个独立思考，如何把上一篇使用双重散列法实现的 HashSet4 改造成泛型字典？HashSet4 到泛型字典
泛型字典在功能上与 Hashtable 的不同之处主要有2点：1）它的 Key 和 Value 都是泛型的；2）遍历 Key 得到的序列与添加时的顺序一致。
先看第一点：泛型。如果把 HashSet4 的 Key 的类型由 Object 改成泛型参数 TKey，就无法把 null 和 _bucket 赋值给 Key 了，这两个特殊的值分别表示槽是空槽和标记为删除的槽，所以要为 Bucket 增加一个状态属性，并修改 MarkDeleted() 和 IsEmputyOrDeleted() 函数：view sourceprint?01 public class HashSet4<TKey>
02 {
03 [DebuggerDisplay("Key = {Key} k = {k} IsCollided = {IsCollided}")]
04 private struct Bucket
05 {
06 public TKey Key;
07 private int _k; // Store hash code; sign bit means there was a collision.
08 public BucketState State;
09 public int k
10 {
11 get { return _k & 0x7FFFFFFF; } // 返回去掉最高的碰撞位之后的 _k
12 set
13 {
14 _k &= unchecked((int)0x80000000); // 将 _k 除了最高的碰撞位之外的其它位全部设为0
15 _k |= value; // 保持 _k 的最高的碰撞位不变，将 value 的值放到 _k 的后面几位中去
16 }
17 }
18 // 是否发生过碰撞
19 public bool IsCollided
20 {
21 get { return (_k & unchecked((int)0x80000000)) != 0; } // _k 的最高位如果为1表示发生过碰撞
22 }
23 // 将槽标记为发生过碰撞
24 public void MarkCollided()
25 {
26 _k |= unchecked((int)0x80000000); // 将 _k 的最高位设为1
27 }
28
29 public void MarkDeleted()
30 {
31 State = BucketState.Deleted;
32 k = 0;
33 }
34
35 public bool IsEmputyOrDeleted()
36 {
37 return State == BucketState.Empty || State == BucketState.Deleted;
38 }
39 }
40 private enum BucketState
41 {
42 Empty = 0,
43 Full = 1,
44 Deleted = 2
45 }
46 // ...
47 }
Rehash()、Add()、Contains()、Remove() 也要做相应的修改：
show sourceview sourceprint?001 public class HashSet4<TKey>
002 {
003 // 将老数组中的项在大小为 newSize 的新数组中重新排列
004 private void Rehash(int newSize)
005 {
006 _occupancy = 0; // 将标记为碰撞的槽的数量重新设为0
007 Bucket[] newBuckets = new Bucket[newSize]; // 新数组
008 // 将老数组中的项添加到新数组中
009 for (int oldIndex = 0; oldIndex < _b
补充：综合编程 , 其他综合 ,
