Hash 冲突解决方法

何为 Hash 冲突

假设 Hash 表大小为 5(即 5 个槽位),现在要把 2,5,6,7,8 这几个数存储到 Hash 表中,假设 hash 函数为hash(num)=num % size

简单计算下,第一个数 2 的 hash 值为 2 所以放到第三个槽中,第二个数 5 的 hash 值为 0 放到第一个槽中,第三个数 6 的 hash 值为 1 放到第二个槽中,如下图所示:

1 号槽 2 号槽 3 号槽 4 号槽 5 号槽
5 6 2

第四个数 7 的 hash 值也为 2,应该放到第二个槽位,但是第二个槽位中已经放有数据了,这种情况就属于 hash 冲突。
简单来说,就是两个不同的数据经过 hash 函数计算之后得到了相同的 hash 值,这就叫做 hash 冲突。

如何解决冲突

开放地址法

开放地址法也称为再散列法

基本原理

当关键字 key 的哈希地址 p=hash(key)出现冲突时,以 hash 值 p 为基础,产生另一个哈希地址 p1,如果 p1 仍然冲突,再以 p 为基础,产生另一个哈希地址 p2,…,直到找出一个不冲突的哈希地址 pi ,然后将相应元素存入其中

基本公式
1
2
p = hash(key)
h = (p + di) % m

上面的公公式中:

  1. hash(key)是根据关键字 key 计算得到的 hash 值 p
  2. di是一个增量序列,根据这个增量序列取值的区分,开放地址法也有不同的区分
  3. m是 hash 表的表长 (表大小)
线性探测再散列

当上述公式中的增量序列di的取值为递增顺序取值时即为线性探测再散列

1
di = 1,2,3,4,5 ... n-1,n   (n <= m - 1)

这种方式在发生 hash 冲突时,会逐步向后移动一个位置,顺序的查看下一个槽位,一直到找出下一个空的槽位或是直到查遍全表

当 hash 值 p 出现冲突时,则将数据放到(p + 1) % m处,如果此时还存在冲突,则将数据放到(p + 2) % m处,如果再次存在冲突,则将数据放到(p + 3) % m处,依次类推

二次探测再散列

di的取值规则如下时则称为二次探测再散列

1
1*1,-1*1, 2*2,-2*2, 3*3,-3*3, ..., k*k,-k*k   (k <= m/2)

当 hash 值 p 出现冲突时,则将数据放到(p + 1) % m处,如果此时还存在冲突,则将数据放到(p - 1) % m处,如果再次存在冲突,则将数据放到(p + 4) % m处,如果依然存在冲突,则将数据放到(p - 4) % m处,依次类推

伪随机探测再散列

di的取值是随机数序列时则称为伪随机探测再散列

1
2
di = 随机数序列
// 假设有个随机数序列:2,8,3,5,11,6,7

当 hash 值 p 出现冲突时,则将数据放到(p + 2) % m处,如果此时还存在冲突,则将数据放到(p + 8) % m处,如果再次存在冲突,则将数据放到(p + 3) % m处,如果依然存在冲突,则将数据放到(p + 5) % m处,依次类推

缺点
  • 对开放地址法构造的哈希表,删除结点不能简单地将被删结 点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元 (即开放地址) 都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点
  • 开放地址法要求哈希表空间大于或等于装填数据数目

再哈希法

这种方式是构造多个不同的哈希函数

1
hi = RHi(key)     i=1,2,3,...,k

当哈希值hi = RH1(key)发生冲突时,再计算hi = RH2(key)…. 一直到不产生冲突为止。

优缺点

这种方式不容易产生聚集,但是增加了计算时间

链地址法

这种方法的原理是将所有哈希值为 i 而导致冲突的元素构成一个同义词单链表,并将单链表的头指针存在哈希表的第 i 个槽位中。因此对哈希值为 i 的元素的查找、添加、删除都是在此单链表中进行。结构如下图
这里写图片描述

这里写图片描述

优点
  1. 处理冲突简单,无堆积现象,即非同义词不会产生冲突,平均查找路径较短
  2. 链地址法中各链表的节点空间都是动态申请的,因此链地址法比较适合构造 Hash 表前无法确定表长的业务场景
  3. 链地址法构造的哈希表删除操作比较容易实现,只需要简单的删除链表上对应的节点即可
缺点

链地址法的指针需要额外的空间

建立公共溢出区

这种方法的原理是将哈希表分为基本表和溢出表两部分,凡是和基本表中元素发生冲突的元素均存入溢出表