哈希表解决冲突的两种方式

╰半夏微凉° 2024-02-19 16:57 47阅读 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，则无论是查找还是插入均意味着失败(此时表满)。  
**利用开放地址法的一般形式，线性探查法的探查序列为：**  
hi=(h(key)+i)％m 0≤i≤m-1 //即di=i  
**用线性探测法处理冲突，思路清晰，[算法][Link 1]简单，但存在下列缺点：**  
① 处理溢出需另编程序。一般可另外设立一个溢出表，专门用来存放上述哈希表中放不下的记录。此溢出表最简单的结构是顺序表，查找方法可用顺序查找。  
② 按上述算法建立起来的哈希表，删除工作非常困难。假如要从哈希表 HT 中删除一个记录，按理应将这个记录所在位置置为空，但我们不能这样做，而只能标[上已][Link 2]被删除的标记，否则，将会影响以后的查找。  
③ 线性探测法很容易产生堆聚现象。所谓堆聚现象，就是存入哈希表的记录在表中连成一片。按照线性探测法处理冲突，如果生成哈希地址的连续序列愈长 ( 即不同关键字值的哈希地址相邻在一起愈长 ) ，则当新的记录加入该表时，与这个序列发生冲突的可能性愈大。因此，哈希地址的较长连续序列比较短连续序列生长得快，这就意味着，一旦出现堆聚 ( 伴随着冲突 ) ，就将引起进一步的堆聚。  
（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 ，按外链地址法所建立的哈希表如下图所示：

![0_1313338831ie1l.gif][]  
（2）拉链法的优点  
**与开放定址法相比，拉链法有如下几个优点：**  
①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；  
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；  
③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；  
④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。  
  
（3）拉链法的缺点  
　拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

http://hi.baidu.com/zkheartboy/blog/item/b181470f301b79296159f3d0.html

#### 直接定址法 ####

例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。

#### 数字分析法 ####

有学生的生日数据如下：

年.月.日

75.10.03

75.11.23

76.03.02

76.07.12

75.04.21

76.02.15

...

经分析，第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。

#### 平方取中法 ####

取关键字平方后的中间几位为哈希地址。

#### 折叠法 ####

将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。

例如：每一种西文图书都有一个国际标准图书编号，它是一个10位的[十进制][Link 3]数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，可采用此法构造一个四位数的哈希函数。

#### 除留余数法 ####

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。

H(key)=key MOD p (p<=m)

#### 随机数法 ####

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即

H(key)=random(key），其中random为随机函数。通常用于关键字长度不等时采用此法。

若已知哈希函数及冲突处理方法，哈希表的建立步骤如下：

Step1.　取出一个数据元素的关键字key，计算其在哈希表中的存储地址D=H(key）。若存储地址为D的存储空间还没有被占用，则将该数据元素存入；否则发生冲突，执行Step2。

Step2.　根据规定的冲突处理方法，计算关键字为key的数据元素之下一个存储地址。若该存储地址的存储空间没有被占用，则存入；否则继续执行Step2，直到找出一个存储空间没有被占用的存储地址为止。

### 冲突 ###

无论哈希函数设计有多么精细，都会产生冲突现象，也就是2个关键字处理函数的结果映射在了同一位置上，因此，有一些方法可以避免冲突。

#### 拉链法 ####

拉出一个动态链表代替静态[顺序存储结构][Link 4]，可以避免哈希函数的冲突，不过缺点就是链表的设计过于麻烦，增加了编程[复杂度][Link 5]。此法可以完全避免哈希函数的冲突。

#### 多哈希法 ####

设计二种甚至多种哈希函数，可以避免冲突，但是冲突几率还是有的，函数设计的越好或越多都可以将几率降到最低（除非人品太差，否则几乎不可能冲突）。

#### 开放地址法 ####

开放地址法有一个公式：Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1）

其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,...m-1，称[线性][Link 6]探测再散列。

如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,4,-4,9,-9,16,-16,...k\*k,-k\*k(k<=m/2）

称二次探测再散列。如果di取值可能为伪随机数列。称伪随机探测再散列。

#### 建域法 ####

假设哈希函数的值域为\[0,m-1\]，则设向量HashTable\[0..m-1\]为基本表，另外设立存储空间向量OverTable\[0..v\]用以存储发生冲突的记录。

例题1

已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key) = key%7 计算散列地址，并散列存储在散列表A【0....6】中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为

依次进行取模运算求出哈希地址：（关键是这个图）  
![787_1412934249163_11.bmp][]  
74 应该放在下标为4 的位置，由于25 已经放在这个地方，所以74往后移动，放在了下标 为5的位置上了。 由于是等概率查找，所以结果为：1/6\*（1+3+1+1+2+4）= 2.0

例题2

一道哈希表用二次探测再散列法解决冲突的问题  
设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) 【南京理工大学 2001 一、15 （1.5分）】  
  
A．8 B．3 C．5 D．9  
答案为A,为什么我计算出来是D呢?  
我的计算步骤如下:  
15，38，61，84用哈希函数H(key)=key%11计算后得地址:4,5,6,7  
49计算后为5,发生冲突.  
用***二次探测再散列***法解决冲突:  
1:(key+1^2)%11=(49+1)%11=6,仍然发生冲突.  
2:(key-1^2)%11=(49-1)%11=4,仍然发生冲突.  
3:(key+2^2)%11=(49+4)%11=9,不再发生冲突.  
得出结果为D  
  
\------解决方案--------------------  
答案A是正确的  
(key+1^2)%14=(49+1)%14=8，不再发生冲突..  
Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列  
这里m=14 不是11

[Link 1]: http://lib.csdn.net/base/datastructure
[Link 2]: https://www.baidu.com/s?wd=%E4%B8%8A%E5%B7%B2&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[0_1313338831ie1l.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/5f520e4a05c94b8db1c39820a21cdbcd.png
[Link 3]: http://baike.baidu.com/view/359301.htm
[Link 4]: http://baike.baidu.com/view/3585963.htm
[Link 5]: http://baike.baidu.com/view/544149.htm
[Link 6]: http://baike.baidu.com/view/300474.htm
[787_1412934249163_11.bmp]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/8dcdfc627e8244db81c4e4653fc945fe.png