散列表(Hash Table)从理论到实用（中）

不用链接法还有别的方法能处理碰撞吗扪心自问我不敢问这个问题。链接法如此的自然、直接以至于我不敢相信还有别的甚至是更好的方法。推动科技进步的人永远是那些敢于问出比外行更天真、更外行的问题并且善于运用丰富的想象力找到新的可能性而且有能力运用科学的方法实践的人。如果可以不用链表把节省下来的链表的指针所占用的空间用作空槽就可以减少碰撞的机会提高查找速度。使用开放寻址法处理碰撞不用额外的链表以及任何其它额外的数据结构就只用一个数组在发生碰撞的时候怎么办呢答案只能是再找另一个空着的槽啦这就是开放寻址法(open addressing)。但是这样难道不是很不负责任的吗想象一下有一趟对号入座的火车假设它只有一节车厢上来一位坐7号座位的旅客。过了一会儿又上来一位旅客他买到的是一张假票也是7号座位这时怎么办呢列车长想了想让拿假票的旅客去坐8号座位。过了一会儿应该坐8号座位的旅客上来了列车长对他说8号座位已经有人了你去坐9号座位吧。哦9号早就有人了10号也有人了那你去坐11号吧。可以想见越到后来当空座越来越少时碰撞的几率就越大寻找空座愈发地费劲。但是如果是火车的上座率只有50%或者更少的情况呢也许真正坐8号座位的乘客永远不会上车那么让拿假票的乘客坐8号座位就是一个很好的策略了。所以这是一个空间换时间的游戏。玩好这个游戏的关键是让旅客分散地坐在车厢里。如何才能做到这一点呢答案是对于每位不同的旅客使用不同的探查序列。例如对于旅客 A探查座位 782356……直到找到一个空位对于旅客B探查座位 25667713……直到找到一个空位。如果有 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 个槽保存 0int.MatValue 但是不能处理碰撞的 IntSet1:12345678910111213141516171819202122232425publicclassIntSet1{privateobject[] _values newobject[10];privateintH(intvalue){returnvalue % 10;}publicvoidAdd(intitem){_values[H(item)] item;}publicvoidRemove(intitem){_values[H(item)] null;}publicboolContains(intitem){if(_values[H(item)] null)returnfalse;elsereturn(int)_values[H(item)] item;}}现在想用开放寻址法处理碰撞该怎么改造它最简单的方法是如果发现 values[8] 已经被占用了就看看 values[9] 是否空着如果 values[9] 也被占用了就看看 values[0] 是不是还空着。完整的描述是先使用 H() 函数获取 k 的第一个地址如果这个地址已被占用就探查下一个紧挨着的地址如果还是不能用就探查下一个紧挨着的地址如果到达了数组的末尾就卷绕到数组的开头如果探查了 m 次还是没有找到空槽就说明数组已经满了这就是线性探查linear probing。实现代码是123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354publicclassIntSet2{privateobject[] _values newobject[10];privateintH(intvalue){returnvalue % 10;}privateintLH(intvalue,inti){return(H(value) i) % 10;}publicvoidAdd(intitem){inti 0;// 已经探查过的槽的数量do{intj LH(item, i);// 想要探查的地址if(_values[j] null){_values[j] item;return;}else{i 1;}}while(i 10);thrownewException(集合溢出);}publicboolContains(intitem){inti 0;// 已经探查过的槽的数量intj 0;// 想要探查的地址do{j LH(item, i);if(_values[j] null)returnfalse;if((int)_values[j] item)returntrue;elsei 1;}while(i 10);returnfalse;}publicvoidRemove(intitem){// 有点不太好办}}在 Add() 函数中先探查 LH(value, 0)它等于 H(value)如果发生了碰撞就继续探查 LH(value, 1)它是 H(value) 的下一个地址LH() 里面的 “... % 10”的意思是数组最后一个槽的下一个槽是第一个槽的意思。在 Contains() 函数里使用和 Add() 函数一样的探查序列如果找到了 item 返回 true如果遇到了 null说明 item 不在数组中。比较麻烦的是 Remove() 函数。不能简单地把要删除的槽设为 null那样会导致 Contains() 出错。举个例子如果依次把 31323 添加到 IntSet2 中会执行 _values[3] 3_values[4] 13_values[5] 23。然后Remove(13) 执行 _values[4] null。这时再调用 Contains(23)会依次检查 _values[3]、_values[4]、_values[5] 直到找到 23 或遇到 null由于 _values[4] 已经被设为 null 了所以 Contains(23) 会返回 false。有一个解决此问题的方法是在 Remove(23) 时把 _values[4] 设为一个特殊的值例如 -1而不是 null。这样 Contains(23) 就不会在 _values[4] 那里因为遇到 null 而返回错误的 false 了。并且在 Add() 里遇到 null 或 -1 都视为空槽修改之后的代码如下123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172publicclassIntSet2{privateobject[] _values newobject[10];privatereadonlyintDELETED -1;privateintH(intvalue){returnvalue % 10;}privateintLH(intvalue,inti){return(H(value) i) % 10;}publicvoidAdd(intitem){inti 0;// 已经探查过的槽的数量do{intj LH(item, i);// 想要探查的地址if(_values[j] null|| (int)_values[j] DELETED){_values[j] item;return;}else{i 1;}}while(i 10);thrownewException(集合溢出);}publicboolContains(intitem){inti 0;// 已经探查过的槽的数量intj 0;// 想要探查的地址do{j LH(item, i);if(_values[j] null)returnfalse;if((int)_values[j] item)returntrue;elsei 1;}while(i 10);returnfalse;}publicvoidRemove(intitem){inti 0;// 已经探查过的槽的数量intj 0;// 想要探查的地址do{j LH(item, i);if(_values[j] null)return;if((int)_values[j] item){_values[j] DELETED;return;}else{i 1;}}while(i 10);}}但是这种实现 Remove() 函数的方法有个很大的问题。想象一下如果依次添加 0、1、2、3、4、5、6、7、8、9然后再 Remove 0、1、2、3、4、5、6、7、8这时再调用 Contains(0)此函数会依次检查 _values[0]、_values[1]..._values[9]这是完全无法接受的这个问题先放一放我们在下一篇还会继续讨论解决这个问题的方法。线性探查法虽然比较容易实现但是它有一个叫做一次群集primary clustering的问题。就像本文开篇所讨论的如果 7、8、9 号座位已被占用下一个上车的旅客无论他的票是7号、8号还是9号都会被安排去坐10号下一个上车的旅客无论他的票是7号、8号、9号还是10号都会被安排去坐11号……如果有 i 个连续被占用的槽下一个空槽被占用的概率就会是 (i 1)/m就像血栓一样一旦堵住就会越堵越厉害。这样使用线性探查法很容易产生一长串连续被占用的槽导致 Contains() 函数速度变慢。对于线性探查法由于初始位置 LH(k, 0) H(k) 确定了整个探查序列所以只有 m 种不同的探查序列。二次探查可以在发生碰撞时不像线性探查那样探查下一个紧挨着的槽而是多偏移一些以此缓解一次群集的问题。二次探查quadratic probing让这个偏移量依赖 i 的平方h(k, i) (h(k) c1i c2i2) mod m其中c1 和 c2 是不为0的常数。例如如果取 c1 c2 1二次探查的散列函数为1234privateintQH(intvalue,inti){return(H(value) i i * i) % 10;}对于数值 7QH() 给出的探查序列是 7、9、3、9……由于初始位置 QH(k, 0) H(k) 确定了整个探查序列所以二次探查同样只有 m 种不同的探查序列。通过让下一个探查位置以 i 的平方偏移不容易像线性探查那样让被占用的槽连成一片。但是由于只要探查的初始位置相同探查序列就会完全相同所以会连成一小片、一小片的这一性质导致一种程度较轻的群集现象称为二次群集secondary clusering。双重散列造成线性探查法和二次探查法的群集现象的罪魁祸首是一旦初始探查位置相同整个探查序列就相同。这样一旦出现碰撞事情就会变得更糟。是什么造成一旦初始探查位置相同整个探查序列就相同呢是因为线性探查法和二次探查法都是让后续的探查位置基于初始探查位置即 H(k)向后偏移几个位置而这个偏移量不管是线性的还是二次的都仅仅是 i 的函数但是只有 k 是不同的对不对所以必须想办法让偏移量是 k 的函数才行。以线性探查为例要想办法让 LH(k, i) 是 k 和 i 的函数而不是 H(k) 和 i 的函数。说干就干我们试着把线性探查H(k) k % 10LH(k, i) (H(k) i) % 10改造一下先试试把 k 乘到 i 上面去即H(k) k % 10LH(k, i) (H(k) i * k) % 10这有效果吗很不幸LH(k, i) (H(k) i * k) % 10 (H(k) i * (k%10) % 10 (H(k) i * H(k)) % 10 (H(k) * (1 i)) % 10结果 LH(k, i) 还是 H(k) 和 i 的函数。再试试把 k 加到 i 上即H(k) k % 10LH(k, i) (H(k) i k) % 10这个怎么样LH(k, i) (H(k) i k) % 10 (H(k) i k%10) % 10 (H(k) i H(k)) % 10 (2*H(k) i) % 10太不幸了LH(k) 仍然是 H(k) 和 i 的函数。好像怎么折腾都不行除非把 H(K) 变成乘法散列法或者使用双重散列(double hashing)法h(k, i) (h1(k) i*h2(k)) mod m其中 h1(k) 和 h2(k) 是两个不同的散列函数。例如可以让h1(k) k mod 13h2(k) k mod 11h(k, i) (h1(k) i*h2(k)) mod 10这样h(7, i) 产生的探查序列是 7、4、1、8、5……h(20, i) 产生的探查序列是 7、6、5、4、3……这回终于达到了初始探查位置相同但是后续探查位置不同的目标。h2(k) 的设计很有讲究搞不好会无法探查到每个空槽。以刚刚实现的 h(k, i) 为例h(6, i) 的探查序列是“6、2、8、4、0、6、2、8、4、0”如果恰巧数组中的“6、2、8、4、0”这几个位置都被占用了将会导致程序在还有空槽的状态下抛出“集合溢出”的异常。要避免这种情况要求h2(k) 与 m 必须互质。可以看一看如果 h2(k) 与 m 不是互质的话为什么会有无法探查数组的所有的槽的后果。例如 h2(6)6 与 10 有公约数2把它们代入 h(k, i)h(6, i) (h1(6) i * h2(6)) mod 10 (6 i * 6) mod 10 (6 (i * 6) mod 10) mod 10 (6 2*((i*6) mod 5)) mod 10由于 (i*6) mod 5) 只有 5 个不同的值所以 h(6, i) 也只有 5 个值。而 h(16, i) (3 5*((i*5) mod 2)) mod 10 只有2个值真是太糟糕了。