深入论证哈希表开放地址之双重散列(Double Hashing)算法

本文尝试记录近期实现双重散列算法的过程中，对哈希表和开放地址法的更深层次的感悟。并深入论证其中的理论依据。

哈希表很常见，已渗透到编程的各个领域。除了常见的链地址法之外，开放地址法一直是略有神秘的存在。通过研究这个相对小众算法，发现其中有一些新鲜的思想给人启迪。

哈希表的设计思想，以及其中解决问题的经验曾启发其他数据结构和算法的发展。在数据结构的发展中是一个绝对重要的结构。对区块链、摘要加密都产生了重要影响。甚至人工智能中的降维概念也和哈希表有深远的渊源。

通过研究双重散列，可以更好的理解哈希表的数学原理，以及数据结构设计上的参考。例如，处理冲突的方法、动态扩容的策略，以及对优秀哈希函数的需求，都是数据结构设计中重要的考量。

哈希表

哈希表的本质

哈希表的本质就是降维投影。

降维

一个对象实际上就是一个二维的树，对象的每个Field是一个节点，原始类型的Field是叶子节点，而对象类型的Field又是一个分支节点。

将二维的对象树降维成一个整数的过程就是哈希。好的哈希算法要求降维过程中每一个节点的细微变化将对最终的数产生极大影响。

投影

而将有限个哈希数，从大区间（整数区间）进入一个小的区间（数组区间），这个过程就是投影。
目的是以尽量少的数组容量放置这些哈希数。
假如有N个数，一般会选一个大于N的数M作为数组容量，让数组不要过于拥挤，减少冲突。
N / M 称为加载因子(Load Factor)，常用加载因子是0.75，正好是3/4，方便计算。

取模

投影的方法借助取模这个数学工具。将任意整数 k 对 M 取模，结果一定在 [0, M-1] 之间。

冲突

两个数投影到同一个位置，重叠时称为哈希冲突，解决哈希冲突的不同方式产生了两种主要流派：

主流是链地址法 (Seperate Chaining)，也称为链表法
另一种是开放地址法 (Open Addressing)，也叫做闭哈希。

链地址

链地址法是一种简单可靠的哈希表实现方法。对于哈希冲突的所有的键，以链表或树的形式形成纵深堆叠。
链表法不算复杂，而且无论是增删改查性能都极为出色，因此绝大部分哈希表都采用此法。
由于非常常见，因此不作赘述。

开放地址

开放地址法采用算法将冲突的键放在其他空位上。

假设一个哈希表的容量是M，LoadFactor是0.75，则最多存储0.75M个键。
换句话说，其中必有0.75M个位置可以存值。
假如其中有key的哈希重复，只要没有超出容量，则必然有其他空位可以存这个值。

开放地址法就是通过算法，以尽可能少的步骤，在重叠时找到空位存储重叠的键值对。

开放地址法

开放地址法是一种比较小众的算法，因为：

删除、扩容等操作比较麻烦
算法本身就比较难以理解，写不好容易有漏洞或死循环

因此，一般的哈希表都采用链地址法，不过一些只读哈希表会采用开放地址法。

只读哈希表只需要通过Builder构造数据，一次成型，避免了删除、扩容等复杂情况
开放地址法可以通过一个数组存储所有数据，不需要任何Entry对象，节省内存
由于key, value可以挨在一起存储，对缓存友好，查询性能较高。

探测

从冲突的位置找空位的过程称为探测（Probe）。

线性探测

其中k就是key，也就是要哈希的键。h1(k)就是原本的哈希函数
重叠的哈希，从重叠的位置开始，依次向后一个一个位置找空位。
也就是 h1(k) + 1, h1(k) + 2, h1(k) + 3 ... 以此类推
从重叠的位置开始，或者用算法算出一个比较分散的位置开始。总之最后会回到顺序查找的思路。
此法最大的问题是，顺序探测的复杂度最终会和数据规模相关，也就是最坏情况是 O(n)。

线性探测的主聚集问题

主聚集问题就是说，h1(k) 可能计算出的索引大量堆积在一起，形成了连续的块。
此时，如果发生重叠，则从重叠的位置要跨越整个堆积的块，才能找到空位。
更糟糕的是，新的空位会在原有堆积块的末尾，导致堆积块越来越大。
因此很容易发生一旦聚集就往最坏情况走的趋势。

二次探测

二次探测并不是指第二次探测！实际上二次指的是二次方。

二次探测是线性探测的改进法。每一轮探测非线性增长。
意思就是说 h1(k) + 二次方公式，这个公式不是线性公式，而是二次方公式。
一般直接简单的采用 i^2^。

二次探测的次聚集问题

二次探测可以解决主聚集的问题。但是容易引发次聚集问题。

次聚集问题就是说，二次探测时，每个重叠的 h1(k) 都是一样的（因为重叠了嘛）。
而二次探测的公式也一样，因此对每一个相同的 h1(k) 二次探测的每一轮的值也一样，这样就发生了次聚集。
次聚集并非物理上连在一起，而是逻辑上聚集。

伪随机探测

不直接用顺序索引顺序探测，而是采用伪随机数生成一个系列的数，用伪随机数序列的第i个值作为偏移来探测。
伪随机数要求对每个输入，输出应当相同，因此不是真正的随机数。如果真随机，则get的时候就无法再快速找到。
伪随机数序列可以解决主聚集，次聚集等问题。
但主要问题是伪随机数的生成比较复杂，比较耗时。

双重散列

双重散列 Double Hashing 是一种稍微复杂的算法，当出现重叠的哈希时，我们希望避免依次顺序查找空位，而是通过算法让每一轮的探测分散，尽量避免和已有数据的位置冲突。

因此我们引入第二个哈希公式，并让第二个哈希算法对每一个重复的key用不同的路径探测，以便尽量避免次聚集问题。

双重散列深入探讨

双重散列算法碰到重复的哈希键，会通过一个探测公式来轮询查找。

探测公式

探测公式一般选择：

代码示例：

int hash1 = h1(key);
//发现重复，index位置不是空的，且不是当前的key
//开始 Double Hashing
int hash2 = h2(key);
for (int i = 1; i < M; i++) {
  int index2 = floorMod(hash1 + i * hash2, M);
  // todo 探测index2是否空位
}

其中i是探测的循环次数，h1和h2是2个哈希算式。
第一个哈希算式就是原有的哈希算式。一般就是
第二个哈希算式有多种选择，常见的算式：

标准h2(k)算式

常见双重散列公式
一般M是一个质数，此处R选择比M略小的质数。

h2(k)的取值范围

会落在 [0, R - 1] 的区间，类似落在 [0, M-1]。
而则落入 [1, R] 的区间。因此避免了0值。

因为如果 h2(k) 出现0值，则带入探测公式，会永远在一个位置探测，出现死循环。

双重散列是否解决了主聚集和次聚集问题？

双哈希中不是线性增长的，因此避免了主聚集问题。

代码中 h2(k) 在循环之前算好，每一轮循环都是，那么是不是也会引发次聚集问题？

实际上不会，因为两个不同的k，假设是 k1, k2，如果 h1(k1) = h1(k2)，那么会发生重叠。
但是由于 h2 和 h1 的算法不同，因此（除非碰巧重叠）
因此两者的探测路径是不同的，从而避免了次聚集问题。

为什么双重散列可以找到空位？

双重散列不是很直观，感觉引入第二个哈希之后，探测的顺序几乎是不确定的。
那很容易产生疑问：一定能找到空位吗？理论依据是什么？

拆解命题

首先我们来拆解问题，从一个重叠的点 h1(k) 出发，探测空位的本质是什么？
实际上是能够不重复的遍历剩余的M-1个槽位。

即：探测序列在 i 从 1 增加到 M-1 的过程中，要证明：

能够生成 M-1 个不同的哈希地址
并且这些地址会覆盖哈希表中，除了重叠点之外所有 M-1 个槽位。

先证明h2(k)与M互质

互质 coprime: 整数 a 和 b 互质，当且仅当它们的最大公约数 (GCD) 为 1，即

已知

M是一个质数
R是一个质数
R < M

证明

由于 M 是一个质数。质数 M 的唯一正因子只有 1 和 M 本身。
任何一个整数 x，只要 1 <= x < M，那么 x 都不可能是 M 的倍数。
由于 h2(k) 取值范围 [1,R]，且 R < M
因此 h2(k) 满足 1 <= h2(k) < M，所以必然与M互质

反证法，证明重复的不合理性！

假设存在两个不同的探测次数 i1 和 i2 (其中 0 < i1 < i2 < M)，
它们生成了相同的哈希地址，也就是：

根据模算术的性质，这等价于：

或者说：
是 M 的倍数。
也就是：
(其中 k 是某个整数)
这意味着 M 能够整除。

由于我们已经证明了 h2(k) 和 M 互质
根据数论中的欧几里得引理的推论（或称作高斯引理）：

如果一个质数 P 整除 a * b，那么 P 必然整除 a，或 P 必然整除 b。

也就是说，如果 M 整除且，那么 M 必然整除 B。
也就是要求 M 整除，且（已证互质）。
因此，M 必须整除，也就是要满足。

但是，我们知道。这意味着。
当 n=0 时，，不可能，因为；
当 n=1 时，，不可能，因为 i2 < M 且 i1 < M，(i2-i1) 不可能大于等于M。

反证成功，由反面的假设，引出了悖论，说明假设是错误的。
说明 i1 和 i2 无法生成相同的地址。

因此，i 从 1 到 M-1 的 M-1 个迭代过程，会生成 M-1 个互不相同的哈希地址。
由于探测公式是取 M 的模，因此这些地址全都小于M。
由于哈希表只有 M 个槽位，排除起始位置，这 M-1 个不同的地址必然会覆盖所有剩下的 M-1 个槽位。

R的取值

R取小于M的最接近M的质数。

R是否可以大于M？

不能，因为R如果大于M，则 h2(k) 的值有可能大于等于M，则结果中可能出现重复。

R是否可以取 [1,M-1] 的任意值？

最好不要，尽量靠近M，则结果可以有更多的多样性，可以更快的找到空位。
取一个极端的例子，如果R为1，则双哈希会退化为线性探测。

k mod 1 = 0
1-(k mod 1) = 1
所以 h2(k) 永远是1
所以双哈希的公式变为线性探测的公式

所以R要取小于M的尽可能大的质数。

M的取值

最后一个问题，就是M如何取值？
具体的，我们有m个数，如何确定一个合适的质数M来构造开放地址哈希表？

质数的运算始终是一个难题，我的做法是手工构造一个具有合适稀疏程度的质数表。
这个质数表通过程序代码预先推算出来，并通过效率测试不断优化。
由于不需要全部质数，因此还是可以接受的。

方案1：计算质数

目前尚无特别准确的质数计算法。只能大概估算，然后验证是否质数。

方案2：查表法

查表法需要构造一个质数表，通过二分法可以快速查找。
但一个完整的质数表实在太大了，空间代价太大。

方案3：混合法

对于较小的质数，采用查表法。例如，保存1000以内的质数表。
对于超出质数表的情况，采用质数检测。

其他h2(k)算式

模R加1

加一避免为0，实际效果与 R - (k mod R) 一样。
但对于特殊情况，如果M=R+1时，此法可能溢出导致重叠。
举例：M=3,R=2
差为1的质数对应该仅此一例，因为只有2是偶数。特例特殊处理即可。

`M-2`作为模数

M-2忘记是在哪里看到的。反复证明了一下，发现前提条件 M 不一定是质数，取奇数即可。
如果M是奇数，则与M-2互质。
但M如果不是质数怎么保证第一轮哈希均匀分布？可能会牺牲第一轮的均匀分布，造成一定聚集。
因此M还是取质数。实际上只有2是偶质数，其他所有质数本身就是奇数。
所以M-2应该也可行，排除特例2即可。
具体的h2(k)：

此方案有效，而且避免了R的质数查询，计算简单，效果不错！

k mod (M-2)结果在 [0, M-3]
1 + (k mod (M-2))结果在 [1, M-2]，满足不为0
由于M是质数，h2(k)的结果小于M且大于0，因此h2(k)与M互质

看起来M-2是一个不错的选择。那么为什么不用M-1呢？
按照定理推论：

两个相邻的自然数一定互质 (M-1)
两个相邻的奇数一定互质 (M-2)

所以，其实M-2或M-1可以看作是的一种特例，也就是 R 取 M-2 或 M-1。

我没有看到M-1有什么问题，也许是一种约定俗成？

当 M 取 2^n^-1 时，M/2 也同样符合 2^n^ - 1。
2^n^ - 1就是所谓的梅森数，梅森数虽然不一定全都是质数，但实际编程中很多场景会使用，因为 2^n^ - 1 用于取模是特别快的，只需要位与就可以。
此时，第一个哈希h1(k)=k & M通过位与实现取模，结果覆盖 [0, M-1]。
第二个哈希用 M >>> 1，(k & (M>>>1)) + 1 结果只能覆盖 M的一半左右。
此方案存在严重缺陷。

梅森数继续探讨

梅森数虽然并非都是质数，但却是离质数很近的数。
因此哈希表的容量一般都取 2^n^，为啥呢？因为方便取模运算。计算，只需要 $Misplaced &$ 即可，不需要算质数这么复杂的问题。
而且效果还行，这么多案例在用说明这个trade-off还是蛮香的。万一重复了，链地址法将重复的键都用链表或树堆在一起。
因此，尝试令 M=2^n^-1，R=M-2，并验证可行性。因为此方案规避了质数问题。

经过实际代码验证，此方案也不可行。当 M 不是质数时，不能够代入质数互质的推论。所以会出现重复。

例如 M=15时，R=13，如果 k = 1
此时 h2(k) = 16mod13=3
i=1, index=(1 * 3) mod 15=3
i=6, index=(6 * 3) mod 15=3
重复了

也就是说如果M取梅森数，R取M-2时，不能保证M-1轮循环可以探测所有空位。

质数

关于质数还存在探讨空间。
前面我们提到获取质数的几种方案，现在我们来详细讨论一下。

质数检测
查表法：保存质数表，通过二分查找快速找到下一个质数。
混合法：小数查表，大数检测

实际上，在Java中，已经有质数检测的实现，位于BigInteger类中：

public static BigInteger probablePrime(int bitLength, Random rnd);
public BigInteger nextProbablePrime()
public boolean isProbablePrime(int certainty)

这个质数运算法基于米勒-拉宾素性检验法。
不要被方法中的 probable 骗了，这是对于BigInteger任意大的数来说的，存在微乎其微的不确定性。
对于32位整数来说，保证运算结果的准确性。
对于小于 (大约 ) 的数：
如果一个数通过了基数 2, 7, 61 的米勒-拉宾素性检验，那么它就保证是质数。
（这个结论由 Jaeschke 在 1993 年证明。）
对于long的取值范围64位整数，米勒-拉宾法一样是准确的，确定的。

因此，使用 BigInteger 的质数检测方法是可靠的。
仅当需要更高效率时，可以考虑查表法，用一定空间换更高效率。

提供我的性能测试结果：针对一个5位数12345测试。
查表法大约9纳秒，自行实现的MillerRabin大约是100倍，BigInteger大约是1万倍。

Benchmark                  Mode  Cnt      Score     Error  Units
benchNextPrimeArray        avgt   10      9.329 ±   0.173  ns/op
benchNextPrimeMillerRabin  avgt   10   1429.032 ±  17.370  ns/op
benchNextPrimeBigInteger   avgt   10  86497.642 ± 846.024  ns/op

BigInteger内部实现是基于BigInteger对象的，而且考虑的很多很全面。
我自行实现的MillerRobin的Certainty取10，而BigInteger默认取100，这是100倍差异的主要原因。
推荐查表法，结合自行实现的MillerRabin，能够取得比较不错的稳定效果。

总结

通过一番探索可以发现，双哈希算法的结果不重复探索所有空位其实是通过探测公式保证的。
而h2(k)只要不为0且小于M即可。
M必须取质数，此时R可以取 M-2、M-1 或取小于M的质数都可以完成双哈希算法。

感想

本文写作时随想随写，边证边写。
因此虽然主要证明过程是基于，但最后发现更好。且两者其实类似。

写作过程有些啰嗦有些重复的地方。
前面的过程也不打算做大的修改，失败的尝试也是有价值的。
过程也留在这里，万一有人发现过程有误，还请不吝赐教。

本文采用 CC BY 4.0 许可协议，转载请注明出处。