你还应该知道的哈希冲突解决策略

  1. 云栖社区>
  2. vivo互联网技术>
  3. 博客>
  4. 正文

你还应该知道的哈希冲突解决策略

2020Labs 2020-05-06 10:36:23 浏览255
展开阅读全文

本文首发于 vivo互联网技术 微信公众号 
链接:https://mp.weixin.qq.com/s/5vxYoeARG1nC7Z0xTYXELA[](https://mp.weixin.qq.com/s/5vxYoeARG1nC7Z0xTYXELA)
作者:Xuegui Chen

哈希是一种通过对数据进行压缩, 从而提高效率的一种解决方法,但由于哈希函数有限,数据增大等缘故,哈希冲突成为数据有效压缩的一个难题。本文主要介绍哈希冲突、解决方案,以及各种哈希冲突的解决策略上的优缺点。

一、哈希表概述

哈希表的哈希函数输入一个键,并向返回一个哈希表的索引。可能的键的集合很大,但是哈希函数值的集合只是表的大小。

哈希函数的其他用途包括密码系统、消息摘要系统、数字签名系统,为了使这些应用程序按预期工作,冲突的概率必须非常低,因此需要一个具有非常大的可能值集合的散列函数。

密码系统:给定用户密码,操作系统计算其散列,并将其与存储在文件中的该用户的散列进行比较。(不要让密码很容易被猜出散列到相同的值)。

消息摘要系统:给定重要消息,计算其散列,并将其与消息本身分开发布。希望检查消息有效性的读者也可以使用相同的算法计算其散列,并与发布的散列进行比较。(不要希望伪造消息很容易,仍然得到相同的散列)。

这些应用的流行哈希函数算法有:

  • md5 : 2^128个值(找一个冲突键,需要哈希大约2 ^ 64个值)

  • sha-1:2^160个值(找一个冲突键,需要大约2^80个值)

二、哈希冲突

来看一个简单的实例吧,假设采用hash函数:H(K) = K mod M,插入这些值:217、701、19、30、145

H(K) = 217 % 7 = 0

H(K) = 701 % 7 = 1

H(K) = 19 % 7 = 2

H(K) = 30 % 7 = 2

H(K) = 145 % 7 = 5

上面实例很明显 19 和 30 就发生冲突了。

三、冲突解决策略

除非您要进行“完美的散列”,否则必须具有冲突解决策略,才能处理表中的冲突。
同时,该策略必须允许查找,插入和删除正确运行的操作!

冲突解决技术可以分为两类:开散列方法( open hashing,也称为拉链法,separate chaining )和闭散列方法( closed hashing,也称为开地址方法,open addressing )。这两种方法的不同之处在于:开散列法把发生冲突的关键码存储在散列表主表之外,而闭散列法把发生冲突的关键码存储在表中另一个槽内。

下面介绍业内比较流行的hash冲突解决策略:

  • 线性探测(Linear probing)

  • 双重哈希(Double hashing)

  • 随机散列(Random hashing)

  • 分离链接(Separate chaining)

上面线性探测、双重哈希、随机散列都是闭散列法,而分离链接则是开散列法。

1、线性探测(Linear probing)

插入一个值

使用散列函数H(K)在大小为M的表中插入密钥K时:

  1. 设置 indx = H(K)

  2. 如果表位置indx已经包含密钥,则无需插入它。Over

  3. 否则,如果表位置indx为空,则在其中插入键。Over

  4. 其他碰撞。设置 indx =(indx + 1)mod M.

  5. 如果 indx == H(K),则表已满!就只能做哈希表的扩容了

因此,线性探测基本上是在发生碰撞时对空槽进行线性搜索。

优点:易于实施;总是找到一个位置(如果有);当表不是很满时,平均情况下的性能非常好。

缺点:表的相邻插槽中会形成“集群”或“集群”键;当这些簇填满整个阵列的大部分时,性能会严重下降,因为探针序列执行的工作实际上是对大部分阵列的穷举搜索。

简单例子

如哈希表大小M = 7, 哈希函数:H(K) = K mod M。插入这些值:701, 145, 217, 19, 13, 749

H(K) = 701 % 7 = 1

H(K) = 145 % 7 = 5

H(K) = 217 % 7 = 0

H(K) = 19 % 7 = 2

H(K) = 13 % 7 = 1(冲突) --> 2(已经有值) --> 3(插入位置3)

H(K) = 749 % 7 = 2(冲突) --> 3(已经有值) --> 4(插入位置4)

可见,如果哈希表如果不是很大,随着数据插入,冲突也会组件发生,探针遍历次数将会逐渐变低,检索过程也就成为穷举。

检索一个值

如果使用线性探测将键插入表中,则线性探测将找到它们!

当使用散列函数 H(K)在大小为N的表中搜索键K时:

  1. 设置 indx = H(K)

  2. 如果表位置indx包含键,则返回FOUND。

  3. 否则,如果表位置 indx 为空,则返回NOT FOUND。

  4. 否则设置 indx =(indx + 1)modM。

  5. 如果 indx == H(K),则返回NOT FOUND。就只能做哈希表的扩容了

问题:如何从使用线性探测的表中删除键?

能否进行“延迟删除”,而只是将已删除密钥的插槽标记为空? 

很明显,在线性探测很难做到,如果把位置置为空,那么如果后面的值也是哈希冲突,线性探测插入,则再也无法遍历这些值了。

2、双重哈希(Double hashing)

线性探测冲突解决方案会导致表中出现簇,因为如果两个键发生碰撞,则探测到的下一个位置对于这两个键都是相同的。

双重哈希的思想:使偏移到下一个探测到的位置取决于键值,因此对于不同的键可以不同。

需要引入第二个哈希函数 H 2(K),用作探测序列中的偏移量(将线性探测视为 H 2(K)== 1 的双重哈希)。

对于大小为 M 的哈希表,H 2(K)的值应在 1到M-1 的范围内;如果M为质数,则一个常见选择是 H2(K)= 1 +((K / M)mod(M-1))。

然后,用于双哈希的插入算法为:

  1. 设置 indx = H(K); offset = H 2(K)

  2. 如果表位置indx已经包含密钥,则无需插入它。Over

  3. 否则,如果表位置 indx 为空,则在其中插入键。Over

  4. 其他碰撞。设置 indx =(indx + offset)mod M.

  5. 如果 indx == H(K),则表已满!就只能做哈希表的扩容了

哈希表为质数情况,双重hash在实践中非常有效

双重 Hash 也见:https://blog.csdn.net/chenxuegui1234/article/details/103454285

3、随机散列(Random hashing)

与双重哈希一样,随机哈希通过使探测序列取决于密钥来避免聚类。

使用随机散列时,探测序列是由密钥播种的伪随机数生成器的输出生成的(可能与另一个种子组件一起使用,该组件对于每个键都是相同的,但是对于不同的表是不同的)。

然后,用于随机哈希的插入算法为:

  1. 创建以 K 为种子的 RNG。设置indx = RNG.next() mod M。

  2. 如果表位置 indx 已经包含密钥,则无需插入它。Over

  3. 否则,如果表位置 indx 为空,则在其中插入键。Over

  4. 其他碰撞。设置 indx = RNG.next() mod M.

  5. 如果已探测所有M个位置,则放弃。就只能做哈希表的扩容了。

随机散列很容易分析,但是由于随机数生成的“费用”,它并不经常使用。双重哈希在实践中还是经常被使用。

4、分离链接(Separate chaining)

在具有哈希函数 H(K)的表中插入键K时

  1. 设置 indx = H(K)

  2. 将关键字插入到以 indx 为标题的链接列表中。(首先搜索列表,以避免重复。)

在具有哈希函数H(K)的表中搜索键K时

  1. 设置 indx = H(K)

  2. 使用线性搜索在以 indx 为标题的链表中搜索关键字。

使用哈希函数 H(K)删除表中的键K时

  1. 设置 indx = H(K)

  2. 删除链接列表中以 indx 为标题的键

优点:随着条目数量的增加,平均案例性能保持良好。甚至超过M;删除比开放地址更容易实现。

缺点:需要动态数据,除数据外还需要存储指针,本地性较差,导致缓存性能较差。

很明显,Java7 的 HashMap 就是一种分裂链接的实现方式。

分离链哈希分析

请记住表的填充程度的负载系数度量:α = N / M。

其中M是表格的大小,并且 N 是表中已插入的键数。

通过单独的链接,可以使 α> 1 给定负载因子α,我们想知道在最佳,平均和最差情况下的时间成本。

成功找到

新键插入和查找失败(这些相同),最好的情况是O(1),最坏的情况是O(N)。让我们分析平均情况

分裂链接的平均成本

假设负载系数为 α = N / M 的表
在M个链接列表中总共分配了N个项目(其中一些可能为空),因此每个链接列表的平均项目数为:

  • 如果查找/插入失败,则必须穷举搜索表中的链表之一,并且表中链表的平均长度为α。因此,使用单独链接进行插入或不成功查找的比较平均次数为

    
    ![](https://oscimg.oschina.net/oscnet/up-d1abf33898b7083dff803fcf6c509158bcf.JPEG)
    
    
  • 成功查找后,将搜索包含目标密钥的链接列表。除目标密钥外,该列表中平均还有(N-1)/ M个密钥;在找到目标之前,将平均搜索其中一半。因此,使用单独链接成功找到的比较平均次数为

    
    ![](https://oscimg.oschina.net/oscnet/up-f2b7ba6592698925f4b91f9bb40b39a6819.JPEG)
    
    

当α<1时,它们分别小于1和1.5。并且即使当α超过1时,它们仍然是O(1),与N无关。

四、开散列方法 VS 闭散列方法

如果将键保留为哈希表本身中的条目,则可以使用线性探测,双重和随机哈希... 这样做称为“开放式寻址”,也称为“封闭式哈希”。

另一个想法:哈希表中的条目只是指向链表(“链”)头部的指针;链接列表的元素包含键... 这称为“单独链接”,也称为“开放式哈希”。

通过单独的链接,冲突解决变得容易:只要在其链表中插入一个键,就可以将其插入(为此,可以使用比链表更高级的数据结构;但是正如我们将看到的,链表在一般情况下效果很好)。

让下面我们看一下这些策略的时间成本。

开放式地址哈希分析

分析哈希表“查找”或“插入”性能时,一个有用的参数是负载系数 α = N / M。

其中 M 是表格的大小,并且 N 是表中已插入的键数负载系数是表满度的一种度量。

给定负载因子 α ,我们想知道在最佳,平均和最差情况下的时间成本。

成功找到
对所有键,最好的情况是O(1),最坏的情况是O(N),新键插入和查找失败(这些相同),所以让我们分析平均情况。
我们将给出随机哈希和线性探测的结果。实际上,双重哈希类似于随机哈希;

平均不成功的查找/插入成本

假定负载系数为α= N / M的表。考虑随机散列,因此聚类不是问题。每个探针位置是随机且独立生成的对于每个探针,找到空位置的可能性为(1-α)。查找空位置将停止查找或插入,这是一个伯努利过程,成功概率为(1-α)。该过程的预期一阶到达时间为 1 /(1-α)。所以:

使用随机哈希进行插入或不成功查找的探针的平均数量为

使用线性探测时,探头的位置不是独立的。团簇形成,当负载系数高时会导致较长的探针序列。可以证明,用于线性探测的插入或未成功发现的探针的平均数量约为

当 α 接近1时,这些平均案例时间成本很差,仅受M限制;但当 α 等于或小于7.75(与M无关)时,效果还不错(分别为4和8.5)

平均成功查找成本

假定负载系数为 α= N / M 的表。考虑随机散列,因此聚类不是问题。每个探针位置是随机且独立生成的。

对于表中的键,成功找到它所需的探针数等于将其插入表中时所采用的探针数。每个新密钥的插入都会增加负载系数,从0开始到α。

因此,通过随机散列成功发现的探测器的平均数量为

通过线性探测,会形成簇,从而导致更长的探针序列。可以证明,通过线性探测成功发现的平均探针数为

当α接近1时,这些平均案例时间成本很差,仅受M限制;但当α等于或小于7.75时好(分别为1.8和2.5),与M无关。

网友评论

登录后评论
0/500
评论
2020Labs
+ 关注
所属团队号: vivo互联网技术