为什么随机探测在哈希表实现中不太流行？

Question

根据维基百科和谷歌发现的各种.edu网站等多个来源，哈希表解决冲突的最常见方式是线性探测、二次探测和链接法。虽然随机探测被简单地提到了一下，但并没有受到太多关注。我已经实现了一个使用随机探测解决冲突的哈希表。假设存在冲突，则解决方法如下：

1. 使用对象的完整（32位）哈希来种子化线性同余随机数生成器。
2. 生成器生成32位数字，并取模以确定在哈希表中下一个要探测的位置。

这有一个非常好的特性，即使在模空间中有很多哈希冲突，只要在完整的32位哈希空间中冲突很少，查找和插入时间都预计为O(1)。由于探测序列是伪随机的，所以与线性探测不同，模空间冲突不会导致聚类行为。由于整个系统都是开地址的，而且没有在任何地方使用链表，因此不需要在每次插入时执行内存分配，不像链接法。

此外，由于哈希的大小通常是地址空间的大小（32位机器上为32位），因此在良好的哈希方案下，不可能在完整的32位哈希空间中放入足够多的项以导致大量的哈希冲突。

那么，为什么随机探测是如此不受欢迎的冲突解决策略呢？

- dsimcha

Answer 1

使用线性查找（如双重哈希）的原因之一是缓存局部性。通过使第二个（重新哈希）函数成为一个小整数的加法，最有可能命中相同的缓存行。这对于大型哈希非常重要。

链式哈希可能由于其简单性而被使用。

- Anna

Answer 2

Python的字典实现可以做到这一点。在dictobject.c中有一个非常好的注释，它说：

...
The first half of collision resolution is to visit table indices via this
recurrence:

    j = ((5*j) + 1) mod 2**i

For any initial j in range(2**i), repeating that 2**i times generates each
int in range(2**i) exactly once (see any text on random-number generation for
proof).
...

看起来很像是一个线性同余随机数发生器！

请注意，这种随机数发生器的完整状态只有i位——为了避免重复访问条目——因此您不能有意义地使用“[t]对象的完整（32位）哈希”来初始化RNG。Python最初使用哈希中的i位来初始化j。如果有另一个冲突，就从哈希中抓取另外5位并将其混合在一起。（阅读那个评论的其余内容，特别是谈到PERTURB_SHIFT的地方。）它以这种方式继续，每次冲突时添加更多位，直到使用完整个哈希代码。这样，Python利用了哈希代码提供的相当数量的任意性，并且代码简单而快速。

这是我读过的最好的代码之一。它在《优雅代码》的第18章中被介绍。所以我会说你找对了什么东西！

- Jason Orendorff

---

有趣。我的实现只是不能保证永远不会再次访问相同的 slot。我进行了一些 Monte Carlo 模拟，并得出结论，在实践中，这种情况发生的频率太低，不必担心。即使允许多次访问同一 slot，您仍然可以获得预期的 O(1) 查找时间。 - dsimcha

Answer 3

可能的原因是线性探测或二次探测具有相同的最坏时间复杂度（O（表的大小）），相同的最佳时间复杂度（O（1）），更易于实现，比良好的随机数生成器更快（因为速度是哈希表的主要卖点）。但我不确定。您是否使用其他碰撞解决方法实现了自己的哈希表，并在不同情况下比较了两者？那将非常有启发性。

- Thomas

Answer 4

你是否遇到过这样的问题：在向非稀疏表中插入元素时，无法保证在开始迭代重复元素之前，您会访问哈希表的所有元素？

因此，插入时间不会被明确定义。

- Aaron

---

如果有一个好的随机数生成器，它应该平等地访问所有桶。对于线性探测和二次探测，插入时间也没有明确定义。 - Thomas

你可以限制那种情况发生的概率 :) - Anna

Answer 5

我认为随机哈希很少使用的原因是，当从32位哈希计算出小哈希值时，哈希冲突很少发生，除非哈希函数存在问题，否则32位哈希函数的所有比特都有很大可能会匹配（例如，仅使用密钥的一部分计算哈希）。如果哈希函数良好且负载因子合理较低，则线性探测和二次探测提供良好的缓存局部性（请记住，大多数哈希碰撞将通过查看仅一个额外项来解决，这个额外项将是跟随第一个猜测的那个，在线性和二次探测中都是如此）。在线性探测中，在所有密钥映射到相同值的情况下，甚至在它们映射到少量值的情况下，性能略优。链式哈希允许轻松删除项。

- supercat