白话算法(6) 散列表(Hash Table)从理论到实用（中）
不用链接法，还有别的方法能处理碰撞吗？扪心自问，我不敢问这个问题。链接法如此的自然、直接，以至于我不敢相信还有别的（甚至是更好的）方法。推动科技进步的人，永远是那些敢于问出比外行更天真、更外行的问题，并且善于运用丰富的想象力找到新的可能性，而且有能力运用科学的方法实践的人。
如果可以不用链表，把节省下来的链表的指针所占用的空间用作空槽，就可以减少碰撞的机会，提高查找速度。使用开放寻址法处理碰撞
不用额外的链表，以及任何其它额外的数据结构，就只用一个数组，在发生碰撞的时候怎么办呢？答案只能是，再找另一个空着的槽啦！这就是开放寻址法(open addressing)。但是这样难道不是很不负责任的吗？想象一下，有一趟对号入座的火车，假设它只有一节车厢，上来一位坐7号座位的旅客。过了一会儿，又上来一位旅客，他买到的是一张假票，也是7号座位，这时怎么办呢？列车长想了想，让拿假票的旅客去坐8号座位。过了一会儿，应该坐8号座位的旅客上来了，列车长对他说8号座位已经有人了，你去坐9号座位吧。哦？9号早就有人了？10号也有人了？那你去坐11号吧。可以想见，越到后来，当空座越来越少时，碰撞的几率就越大，寻找空座愈发地费劲。但是，如果是火车的上座率只有50%或者更少的情况呢？也许真正坐8号座位的乘客永远不会上车，那么让拿假票的乘客坐8号座位就是一个很好的策略了。所以，这是一个空间换时间的游戏。玩好这个游戏的关键是，让旅客分散地坐在车厢里。如何才能做到这一点呢？答案是，对于每位不同的旅客使用不同的探查序列。例如，对于旅客 A，探查座位 7，8，23，56……直到找到一个空位；对于旅客B，探查座位 25，66，77，1，3……直到找到一个空位。如果有 m 个座位，每位旅客可以使用 <0, 1, 2, ..., m-1> 的 m! 个排列中的一个。显而易见，最好减少两个旅客使用相同的探查序列的情况。也就是说，希望把每位旅客尽量分散地映射到 m! 种探查序列上。换句话说，理想状态下，如果能够让每个上车的旅客，使用 m! 个探查序列中的任意一个的可能性是相同的，我们就说实现了一致散列。（这里没有用“随机”这个词儿，因为实际是不可能随机取一个探查序列的，因为在查找这名旅客时还要使用相同的探查序列）。
真正的一致散列是难以实现的，实践中，常常采用它的一些近似方法。常用的产生探查序列的方法有：线性探查，二次探查，以及双重探查。这些方法都不能实现一致散列，因为它们能产生的不同探查序列数都不超过 m2 个（一致散列要求有 m! 个探查序列）。在这三种方法中，双重散列能产生的探查序列数最多，因而能给出最好的结果（注：.net framework 的 HashTable 就是使用的双重散列法）。
在上一篇中，我们实现了一个函数 h(k)，它的任务是把数值 k 映射为一个数组（尽量分散）的地址。这次，我们使用开发寻找法，需要实现一个函数 h(k, i)，它的任务是把数值 k 映射为一个地址序列，序列的第一个地址是 h(k, 0)，第二个地址是 h(k, 1)……序列中的每个地址都要尽可能的分散。线性探查
有这样一个可以用 10 个槽保存 0～int.MatValue （但是不能处理碰撞）的 IntSet1:
view sourceprint?01 public class IntSet1
02 {
03 private object[] _values = new object[10];
04
05 private int H(int value)
06 {
07 return value % 10;
08 }
09
10 public void Add(int item)
11 {
12 _values[H(item)] = item;
13 }
14 public void Remove(int item)
15 {
16 _values[H(item)] = null;
17 }
18 public bool Contains(int item)
19 {
20 if (_values[H(item)] == null)
21 return false;
22 else
23 return (int)_values[H(item)] == item;
24 }
25 }
现在想用开放寻址法处理碰撞，该怎么改造它？最简单的方法是，如果发现 values[8] 已经被占用了，就看看 values[9] 是否空着，如果 values[9] 也被占用了，就看看 values[0] 是不是还空着。完整的描述是，先使用 H() 函数获取 k 的第一个地址，如果这个地址已被占用，就探查下一个紧挨着的地址，如果还是不能用，就探查下一个紧挨着的地址，如果到达了数组的末尾，就卷绕到数组的开头，如果探查了 m 次还是没有找到空槽，就说明数组已经满了，这就是线性探查（linear probing）。实现代码是：
view sourceprint?01 public class IntSet2
02 {
03 private object[] _values = new object[10];
04
05 private int H(int value)
06 {
07 return value % 10;
08 }
09
10 private int LH(int value, int i)
11 {
12 return (H(value) + i) % 10;
13 }
14
15 public void Add(int item)
16 {
17 int i = 0; // 已经探查过的槽的数量
18 do
19 {
20 int j = LH(item, i); // 想要探查的地址
21 if (_values[j] == null)
22 {
23 _values[j] = item;
24 return;
25 }
26 else
27 {
28 i += 1;
29 }
30 } while (i <= 10);
31 throw new Exception("集合溢出");
32 }
33 public bool Contains(int item)
34 {
35 int i = 0; // 已经探查过的槽的数量
36 int j = 0; // 想要探查的地址
37 do
38 {
39 j = LH(item, i);
40 if (_values[j] == null)
41 return false;
42
43 if ((int)_values[j] == item)
44
补充：综合编程 , 其他综合 ,
