解决哈希（HASH）冲突的主要方法

左手的ㄟ右手 2022-07-19 11:57 275阅读 0赞

虽然我们不希望发生冲突，但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的长度，而且事先并不知道关键字的具体取值时。冲突就难免会发 生。另外，当关键字的实际取值大于哈希表的长度时，而且表中已装满了记录，如果插入一个新记录，不仅发生冲突，而且还会发生溢出。因此，处理冲突和溢出是 哈希技术中的两个重要问题。

1、开放定址法  
 　用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。 沿此序列逐个单元地查找，直到找到给定 的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的 地址则表明表中无待查的关键字，即查找失败。  
注意：  
①用开放定址法建立散列表时，建表前须将表中所有单元(更严格地说，是指单元中存储的关键字)置空。  
②空单元的表示与具体的应用相关。  
 　 按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、线性补偿探测法、随机探测等 。  
（1）线性探查法(Linear Probing)  
该方法的基本思想是：  
 将散列表T\[0..m-1\]看成是一个循环向量，若初始探查的地址为d(即h(key)=d)，则最长的探查序列为：  
 d，d+l，d+2，…，m-1，0，1，…，d-1  
 　即:探查时从地址d开始，首先探查T\[d\]，然后依次探查T\[d+1\]，…，直到T\[m-1\]，此后又循环到T\[0\]，T\[1\]，…，直到探查到T\[d-1\]为止。  
探查过程终止于三种情况：  
 　(1)若当前探查的单元为空，则表示查找失败（若是插入则将key写入其中）；  
 (2)若当前探查的单元中含有key，则查找成功，但对于插入意味着失败；  
 　(3)若探查到T\[d-1\]时仍未发现空单元也未找到key，则无论是查找还是插入均意味着失败(此时表满)。  
利用开放地址法的一般形式，线性探查法的探查序列为：  
 h i =(h(key)+i)％m 0≤i≤m-1 //即d i =i  
用线性探测法处理冲突，思路清晰，算法简单，但存在下列缺点：  
① 处理溢出需另编程序。一般可另外设立一个溢出表，专门用来存放上述哈希表中放不下的记录。此溢出表最简单的结构是顺序表，查找方法可用顺序查找。  
② 按上述算法建立起来的哈希表，删除工作非常困难。假如要从哈希表 HT 中删除一个记录，按理应将这个记录所在位置置为空，但我们不能这样做，而只能标上已被删除的标记，否则，将会影响以后的查找。  
③ 线性探测法很容易产生堆聚现象。所谓堆聚现象，就是存入哈希表的记录在表中连成一片。按照线性探测法处理冲突，如果生成哈希地址的连续序列愈长 ( 即不同关键字值的哈希地址相邻在一起愈长 ) ，则当新的记录加入该表时，与这个序列发生冲突的可能性愈大。因此，哈希地址的较长连续序列比较短连续序列生长得快，这就意味着，一旦出现堆聚 ( 伴随着冲突 ) ，就将引起进一步的堆聚。  
（2）线性补偿探测法  
线性补偿探测法的基本思想是：  
将线性探测的步长从 1 改为 Q ，即将上述算法中的 j ＝ (j ＋ 1) % m 改为： j ＝ (j ＋ Q) % m ，而且要求 Q 与 m 是互质的，以便能探测到哈希表中的所有单元。  
【例】 PDP-11 小型计算机中的汇编程序所用的符合表，就采用此方法来解决冲突，所用表长 m ＝ 1321 ，选用 Q ＝ 25 。  
  
（3）随机探测  
随机探测的基本思想是：  
将线性探测的步长从常数改为随机数，即令： j ＝ (j ＋ RN) % m ，其中 RN 是一个随机数。在实际程序中应预先用随机数发生器产生一个随机序列，将此序列作为依次探测的步长。这样就能使不同的关键字具有不同的探测次序，从而可以避 免或减少堆聚。基于与线性探测法相同的理由，在线性补偿探测法和随机探测法中，删除一个记录后也要打上删除标记。  
  
2、拉链法  
（1）拉链法解决冲突的方法  
 　拉链法解决冲突的做法是： 将所有关键字为同义词的结点链接在同一个单链表中 。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数 组T\[0..m-1\]。凡是散列地址为i的结点，均插入到以T\[i\]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于 1，但一般均取α≤1。  
【例】设有 m ＝ 5 ， H(K) ＝ K mod 5 ，关键字值序例 5 ， 21 ， 17 ， 9 ， 15 ， 36 ， 41 ， 24 ，按外链地址法所建立的哈希表如下图所示：  
![解决哈希（HASH）冲突的主要方法][HASH]  
（2）拉链法的优点  
与开放定址法相比，拉链法有如下几个优点：  
① 拉链法处理冲突简单 ，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；  
②由于拉链法中各链表上的 结点空间是动态申请的 ，故它更适合于造表前无法确定表长的情况；  
③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；  
④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。  
  
（3）拉链法的缺点

拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指

哈希表及处理冲突的方法

哈希法又称散列法、杂凑法以及关键字地址计[算法][Link 1]等，相应的表称为哈希表。这种方法的基本思想是：首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f，使得p=f(k)，f称为哈希函数。创建哈希表时，把关键字为k的元素直接存入地址为f(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p=f(k)，从而达到按关键字直接存取元素的目的。

当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即k1≠k2 ，但H（k1）=H（k2），这种现象称为**冲突，**此时称k1和k2为**同义词。**实际中，冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。

综上所述，哈希法主要包括以下两方面的内容：

1）如何构造哈希函数

2）如何处理冲突。

### 8.4.1哈希函数的构造方法 ###

构造哈希函数的原则是：①函数本身便于计算；②计算出来的地址分布均匀，即对任一关键字k，f(k) 对应不同地址的概率相等，目的是尽可能减少冲突。

下面介绍构造哈希函数常用的五种方法。

1． 数字分析法

如果事先知道关键字集合，并且每个关键字的位数比哈希表的地址码位数多时，可以从关键字中选出分布较均匀的若干位，构成哈希地址。例如，有80个记录，关键字为8位十进制整数d1d2d3…d7d8，如哈希表长取100，则哈希表的地址空间为：00~99。假设经过分析，各关键字中d4和d7的取值分布较均匀，则哈希函数为：h(key)=h(d1d2d3…d7d8)=d4d7。例如，h(81346532)=43，h(81301367)=06。相反，假设经过分析，各关键字中d1和d8的取值分布极不均匀，d1 都等于5，d8 都等于2，此时，如果哈希函数为：h(key)=h(d1d2d3…d7d8)=d1d8，则所有关键字的地址码都是52，显然不可取。

2． 平方取中法

当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。

例：我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11，E的内部编码为05，Y的内部编码为25，A的内部编码为01, B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501，同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后，取出第7到第9位作为该关键字哈希地址，如图8.23所示。

<table style="font-size:14px; line-height:26px; margin:0px 0px 0px 50.35pt; padding:0px; font-family:simsun; color:rgb(51,51,51); border-collapse:collapse; border:none; background-color:rgb(231,238,244)"> 
 <tbody style="line-height:28px"> 
 <tr> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border:1pt solid windowtext"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> 关键字 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:solid solid solid none; border-top-color:windowtext; border-right-color:windowtext; border-bottom-color:windowtext; border-top-width:1pt; border-right-width:1pt; border-bottom-width:1pt; border-left-width:initial; border-left-color:initial"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> 内部编码 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:solid solid solid none; border-top-color:windowtext; border-right-color:windowtext; border-bottom-color:windowtext; border-top-width:1pt; border-right-width:1pt; border-bottom-width:1pt; border-left-width:initial; border-left-color:initial"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> 内部编码的平方值 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:solid solid solid none; border-top-color:windowtext; border-right-color:windowtext; border-bottom-color:windowtext; border-top-width:1pt; border-right-width:1pt; border-bottom-width:1pt; border-left-width:initial; border-left-color:initial"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> H(k)关键字的哈希地址 </td> 
 </tr> 
 <tr> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:none solid solid; border-right-color:windowtext; border-bottom-color:windowtext; border-left-color:windowtext; border-right-width:1pt; border-bottom-width:1pt; border-left-width:1pt; border-top-width:initial; border-top-color:initial"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> KEYA </td> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:none solid solid none; border-top-width:initial; border-top-color:initial; border-left-width:initial; border-left-color:initial; border-bottom-color:windowtext; border-bottom-width:1pt; border-right-color:windowtext; border-right-width:1pt"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> 11050201 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:none solid solid none; border-top-width:initial; border-top-color:initial; border-left-width:initial; border-left-color:initial; border-bottom-color:windowtext; border-bottom-width:1pt; border-right-color:windowtext; border-right-width:1pt"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> 122157778355001 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:none solid solid none; border-top-width:initial; border-top-color:initial; border-left-width:initial; border-left-color:initial; border-bottom-color:windowtext; border-bottom-width:1pt; border-right-color:windowtext; border-right-width:1pt"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> 778 </td> 
 </tr> 
 <tr> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:none solid solid; border-right-color:windowtext; border-bottom-color:windowtext; border-left-color:windowtext; border-right-width:1pt; border-bottom-width:1pt; border-left-width:1pt; border-top-width:initial; border-top-color:initial"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> KYAB </td> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:none solid solid none; border-top-width:initial; border-top-color:initial; border-left-width:initial; border-left-color:initial; border-bottom-color:windowtext; border-bottom-width:1pt; border-right-color:windowtext; border-right-width:1pt"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> 11250102 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:none solid solid none; border-top-width:initial; border-top-color:initial; border-left-width:initial; border-left-color:initial; border-bottom-color:windowtext; border-bottom-width:1pt; border-right-color:windowtext; border-right-width:1pt"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> 126564795010404 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:none solid solid none; border-top-width:initial; border-top-color:initial; border-left-width:initial; border-left-color:initial; border-bottom-color:windowtext; border-bottom-width:1pt; border-right-color:windowtext; border-right-width:1pt"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> 795 </td> 
 </tr> 
 <tr> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:none solid solid; border-right-color:windowtext; border-bottom-color:windowtext; border-left-color:windowtext; border-right-width:1pt; border-bottom-width:1pt; border-left-width:1pt; border-top-width:initial; border-top-color:initial"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> AKEY </td> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:none solid solid none; border-top-width:initial; border-top-color:initial; border-left-width:initial; border-left-color:initial; border-bottom-color:windowtext; border-bottom-width:1pt; border-right-color:windowtext; border-right-width:1pt"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> 01110525 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:none solid solid none; border-top-width:initial; border-top-color:initial; border-left-width:initial; border-left-color:initial; border-bottom-color:windowtext; border-bottom-width:1pt; border-right-color:windowtext; border-right-width:1pt"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> 001233265775625 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:none solid solid none; border-top-width:initial; border-top-color:initial; border-left-width:initial; border-left-color:initial; border-bottom-color:windowtext; border-bottom-width:1pt; border-right-color:windowtext; border-right-width:1pt"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> 265 </td> 
 </tr> 
 <tr> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:none solid solid; border-right-color:windowtext; border-bottom-color:windowtext; border-left-color:windowtext; border-right-width:1pt; border-bottom-width:1pt; border-left-width:1pt; border-top-width:initial; border-top-color:initial"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> BKEY </td> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:none solid solid none; border-top-width:initial; border-top-color:initial; border-left-width:initial; border-left-color:initial; border-bottom-color:windowtext; border-bottom-width:1pt; border-right-color:windowtext; border-right-width:1pt"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> 02110525 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:none solid solid none; border-top-width:initial; border-top-color:initial; border-left-width:initial; border-left-color:initial; border-bottom-color:windowtext; border-bottom-width:1pt; border-right-color:windowtext; border-right-width:1pt"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> 004454315775625 </td> 
 <td style="margin:0px; padding:0cm 5.4pt; font-family:Verdana,宋体,sans-serif; border-style:none solid solid none; border-top-width:initial; border-top-color:initial; border-left-width:initial; border-left-color:initial; border-bottom-color:windowtext; border-bottom-width:1pt; border-right-color:windowtext; border-right-width:1pt"> <p style="margin:0cm 0cm 0.0001pt; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:25px; text-align:center; font-size:10.5pt; font-family:'Times new roman'"> 315 </td> 
 </tr> 
 </tbody> 
</table>

图8.23平方取中法求得的哈希地址

3． 分段叠加法

这种方法是按哈希表地址位数将关键字分成位数相等的几部分（最后一部分可以较短），然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。具体方法有**折叠法**与**移位法。**移位法是将分割后的每部分低位对齐相加，折叠法是从一端向另一端沿分割界来回折叠（奇数段为正序，偶数段为倒序），然后将各段相加。例如：key=12360324711202065,哈希表长度为1000，则应把关键字分成3位一段，在此舍去最低的两位65，分别进行移位叠加和折叠叠加，求得哈希地址为105和907，如图8.24所示。

1 2 31 2 3

6 0 33 0 6

2 4 72 4 7

1 1 22 1 1

\+）0 2 0\+）0 2 0

—————————————————

1 1 0 59 0 7

（a）移位叠加(b) 折叠叠加

图8.24 由叠加法求哈希地址

4． 除留余数法

假设哈希表长为m，p为小于等于m的最大素数，则哈希函数为

h（k）=k  %  p ，其中%为模p取余运算。

例如，已知待散列元素为（18，75，60，43，54，90，46），表长m=10，p=7，则有

h(18)=18 % 7=4h(75)=75 % 7=5h(60)=60 % 7=4

h(43)=43 % 7=1h(54)=54 % 7=5h(90)=90 % 7=6

h(46)=46 % 7=4

此时冲突较多。为减少冲突，可取较大的m值和p值，如m=p=13，结果如下：

h(18)=18 % 13=5h(75)=75 % 13=10h(60)=60 % 13=8

h(43)=43 % 13=4h(54)=54 % 13=2h(90)=90 % 13=12

h(46)=46 % 13=7

此时没有冲突，如图8.25所示。

0123456789101112

图8.25除留余数法求哈希地址

5． 伪随机数法

采用一个伪随机函数做哈希函数，即h(key)=random(key)。

在实际应用中，应根据具体情况，灵活采用不同的方法，并用实际数据测试它的性能，以便做出正确判定。通常应考虑以下五个因素 ：

l计算哈希函数所需时间 （简单）。

l关键字的长度。

l哈希表大小。

l关键字分布情况。

l记录查找频率

**8.4.2  处理冲突的方法**

通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。下面以创建哈希表为例，说明解决冲突的方法。常用的解决冲突方法有以下四种：

1.开放定址法

这种方法也称**再散列法，**其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：

Hi=（H（key）\+di）% m i=1，2，…，n

其中H（key）为哈希函数，m 为表长，di称为**增量序列。**增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：

l线性探测再散列

dii=1，2，3，…，m-1

这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

l二次探测再散列

di=12，\-12，22，\-22，…，k2，\-k2( k<=m/2 )

这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。

l伪随机探测再散列

di=伪随机数序列。

具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。

例如，已知哈希表长度m=11，哈希函数为：H（key）= key  %  11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。如果用线性探测再散列处理冲突，下一个哈希地址为H1=（3 + 1）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 + 2）% 11 = 5，还是冲突，继续找下一个哈希地址为H3=（3 + 3）% 11 = 6，此时不再冲突，将69填入5号单元，参图8.26 (a)。如果用二次探测再散列处理冲突，下一个哈希地址为H1=（3 + 12）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 - 12）% 11 = 2，此时不再冲突，将69填入2号单元，参图8.26 (b)。如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，……..，则下一个哈希地址为H1=（3 + 2）% 11 = 5，仍然冲突，再找下一个哈希地址为H2=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元，参图8.26 (c)。

012345678910

（a） 用线性探测再散列处理冲突

012345678910

（b） 用二次探测再散列处理冲突

012345678910

（c） 用伪随机探测再散列处理冲突

图8.26开放地址法处理冲突

从上述例子可以看出，线性探测再散列容易产生“二次聚集”，即在处理同义词的冲突时又导致非同义词的冲突。例如，当表中i, i+1 ,i+2三个单元已满时，下一个哈希地址为i, 或i+1 ,或i+2，或i+3的元素，都将填入i+3这同一个单元，而这四个元素并非同义词。线性探测再散列的优点是：只要哈希表不满，就一定能找到一个不冲突的哈希地址，而二次探测再散列和伪随机探测再散列则不一定。

2.再哈希法

这种方法是同时构造多个不同的哈希函数：

Hi=RH1（key）i=1，2，…，k

当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

3.链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

例如，已知一组关键字（32，40，36，53，16，46，71，27，42，24，49，64），哈希表长度为13，哈希函数为：H（key）= key % 13，则用链地址法处理冲突的结果如图8.27所示：

图8.27链地址法处理冲突时的哈希表

本例的平均查找长度ASL=(1\*7+2\*4+3\*1)=1.5

4、建立公共溢出区

这种方法的基本思想是：将哈希表分为**基本表**和**溢出表**两部分，凡是和基本表发生冲突的元素，一律填入溢出表

[HASH]: http://sjjg.js.zwu.edu.cn/SFXX/sanlie/tupian/8.17.jpg
[Link 1]: http://lib.csdn.net/base/31