本文首发于 vivo互联网技术 微信公众号
链接：mp.weixin.qq.com/s/5vxYoeARG…
作者：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时：
设置 indx = H（K）
如果表位置indx已经包含密钥，则无需插入它。Over
否则，如果表位置indx为空，则在其中插入键。Over
其他碰撞。设置 indx =（indx + 1）mod M.
如果 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时：
设置 indx = H（K）
如果表位置indx包含键，则返回FOUND。
否则，如果表位置 indx 为空，则返回NOT FOUND。
否则设置 indx =（indx + 1）modM。
如果 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））。
然后，用于双哈希的插入算法为：
设置 indx = H（K）; offset = H 2（K）
如果表位置indx已经包含密钥，则无需插入它。Over
否则，如果表位置 indx 为空，则在其中插入键。Over
其他碰撞。设置 indx =（indx + offset）mod M.
如果 indx == H（K），则表已满！就只能做哈希表的扩容了
哈希表为质数情况，双重hash在实践中非常有效
双重 Hash 也见：blog.csdn.net/chenxuegui1…
3、随机散列(Random hashing)
与双重哈希一样，随机哈希通过使探测序列取决于密钥来避免聚类。
使用随机散列时，探测序列是由密钥播种的伪随机数生成器的输出生成的（可能与另一个种子组件一起使用，该组件对于每个键都是相同的，但是对于不同的表是不同的）。
然后，用于随机哈希的插入算法为：
创建以 K 为种子的 RNG。设置indx = RNG.next() mod M。
如果表位置 indx 已经包含密钥，则无需插入它。Over
否则，如果表位置 indx 为空，则在其中插入键。Over
其他碰撞。设置 indx = RNG.next() mod M.
如果已探测所有M个位置，则放弃。就只能做哈希表的扩容了。
随机散列很容易分析，但是由于随机数生成的“费用”，它并不经常使用。双重哈希在实践中还是经常被使用。
4、分离链接(Separate chaining)
在具有哈希函数 H（K）的表中插入键K时
设置 indx = H（K）
将关键字插入到以 indx 为标题的链接列表中。（首先搜索列表，以避免重复。）
在具有哈希函数H（K）的表中搜索键K时
设置 indx = H（K）
使用线性搜索在以 indx 为标题的链表中搜索关键字。
使用哈希函数 H（K）删除表中的键K时
设置 indx = H（K）
删除链接列表中以 indx 为标题的键
优点：随着条目数量的增加，平均案例性能保持良好。甚至超过M；删除比开放地址更容易实现。
缺点：需要动态数据，除数据外还需要存储指针，本地性较差，导致缓存性能较差。
很明显，Java7 的 HashMap 就是一种分裂链接的实现方式。
分离链哈希分析
请记住表的填充程度的负载系数度量：α = N / M。
其中M是表格的大小，并且 N 是表中已插入的键数。
通过单独的链接，可以使 α> 1 给定负载因子α，我们想知道在最佳，平均和最差情况下的时间成本。
成功找到
新键插入和查找失败（这些相同），最好的情况是O（1），最坏的情况是O（N）。让我们分析平均情况
分裂链接的平均成本
假设负载系数为 α = N / M 的表
在M个链接列表中总共分配了N个项目（其中一些可能为空），因此每个链接列表的平均项目数为：
如果查找/插入失败，则必须穷举搜索表中的链表之一，并且表中链表的平均长度为α。因此，使用单独链接进行插入或不成功查找的比较平均次数为
成功查找后，将搜索包含目标密钥的链接列表。除目标密钥外，该列表中平均还有（N-1）/ M个密钥；在找到目标之前，将平均搜索其中一半。因此，使用单独链接成功找到的比较平均次数为
当α<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无关。
更多内容敬请关注 vivo 互联网技术 微信公众号
注：转载文章请先与微信号：Labs2020 联系。