白话算法(6) 散列表(Hash Table) 从理论到实用（下）
【澈丹，我想要个钻戒。】【小北，等等吧，等我再修行两年，你把我烧了，舍利子比钻戒值钱。】
——自扯自蛋无论开发一个程序还是谈一场恋爱，都差不多要经历这么4个阶段：
1）从零开始。没有束缚的轻松感。似乎拥有无限的可能性，也有相当多的不确定，兴奋、紧张和恐惧。
2）从无到有。无从下手的感觉。一步一坎，进展缓慢。走弯路，犯错，投入很多产出很少。目标和现实之间产生强大的张力。疑惑、挫败、焦急和不甘心。
3）渐入佳境。快速成长。创新，充实，满足。但是在解决问题的同时往往会不可避免地引入更多的问题和遗憾。
4）接近成功。已经没有那么多的新鲜感和成就感，几乎是惯性般地努力前行。感觉成功在望，但又好像永远也不能100%搞定。有时，一心想要完成的易做图甚至超越了原本的目标。经过前面2篇，我们也来到了第4阶段。让我们深吸一口气，把遗留下来的这几个问题全部搞定吧。
1）能不能支持所有的对象而不仅限于整数？
2）如何支持所有整数而不只是正整数？
3）被删除了的槽仍然占用查找时间。
4）随着时间的推移，被标记为碰撞的槽越来越多，怎么办？
5）必须在创建容器的时候指定大小，不能自动扩张。
6）只是一个 HashSet，而不是HashTable。继续改造上一篇最后给出的 IntSet4。
支持所有对象而不仅限于整数
要想支持所有对象而不只是整数，就需要一个能把各种类型的对象变换成整数的方法。这一点得到了 .net 特别的优待，Object 类的 GetHashCode() 就是专门干这个的。它提供的默认实现是：对于引用类型，每创建一个新对象都会把Object里的一个内部的计数器增加1，并把计数器的值作为这个对象的 HashCode；对于 struct 对象，将基于每个字段的 HashCode 计算得出一个整型值作为对象的 HashCode。Object 的子类型可以 override GetHashCode() 函数，对于整数类型的变量，GetHashCode() 的返回值与变量的值相同；小数、字符串等都有自己的变换规则（至于具体的规则限于篇幅将不再详细介绍）。总之，我们只要调用对象的 GetHashCode() 函数，把得到的整型值作为 k 的值就行了。另外还需要一个 Object 类型的变量 Key 保存添加的对象，我们把这两个变量封装到一个名为 Bucket 的 struct 里，Add()、Remove()、Contains() 函数也要做相应的修改：
view sourceprint?01 public class HashSet1
02 {
03 [DebuggerDisplay("Key = {Key} k = {k}")]
04 private struct Bucket
05 {
06 public Object Key;
07 public int k; // Store hash code;
08 }
09 private Bucket[] _buckets;
10 private readonly int DELETED = -1;
11 private int GetHashCode(Object key)
12 {
13 return key.GetHashCode();
14 }
15 public HashSet1(int capacity)
16 {
17 int size = GetPrime(capacity);
18 _buckets = new Bucket[size];
19 }
20
21 public void Add(Object item)
22 {
23 int i = 0; // 已经探查过的槽的数量
24 Bucket bucket = new Bucket { Key = item, k = GetHashCode(item) };
25 do
26 {
27 int j = DH(bucket.k, i); // 想要探查的地址
28 if (_buckets[j].Key == null || _buckets[j].k == DELETED)
29 {
30 _buckets[j] = bucket;
31 return;
32 }
33 else
34 {
35 i += 1;
36 }
37 } while (i <= _buckets.Length);
38 throw new Exception("集合溢出");
39 }
40 public bool Contains(Object item)
41 {
42 int i = 0; // 已经探查过的槽的数量
43 int j = 0; // 想要探查的地址
44 int hashCode = GetHashCode(item);
45 do
46 {
47 j = DH(hashCode, i);
48 if (_buckets[j].Key == null)
49 return false;
50
51 if (_buckets[j].k == hashCode && _buckets[j].Key.Equals(item))
52 return true;
53 else
54 i += 1;
55 } while (i <= _buckets.Length);
56 return false;
57 }
58 public void Remove(Object item)
59 {
60 int i = 0; // 已经探查过的槽的数量
61 int j = 0; // 想要探查的地址
62 int hashCode = GetHashCode(item);
63 do
64 {
65 j = DH(hashCode, i);
66 if (_buckets[j].Key == null)
67 return;
68
69 if (_buckets[j].k == hashCode && _buckets[j].Key.Equals(item))
70 {&nbs
补充：综合编程 , 其他综合 ,
