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

本文首发于 vivo互联网技术
作者：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

image

上面实例很明显 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个项目（其中一些可能为空），因此每个链接列表的平均项目数为：

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

  image

• 成功查找后，将搜索包含目标密钥的链接列表。除目标密钥外，该列表中平均还有（N-1）/ M个密钥；在找到目标之前，将平均搜索其中一半。因此，使用单独链接成功找到的比较平均次数为

  image

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

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

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

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

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

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

开放式地址哈希分析

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

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

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

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

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

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

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

image

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

image

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

平均成功查找成本

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

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

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

image

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

image

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