为什么随机探测在哈希表实现中不受欢迎？

Question

根据各种来源,例如维基百科和谷歌发现的各种.edu网站,哈希表解决冲突的最常见方式是线性或二次探测和链接.简要提及随机探测,但没有给予太多关注.我已经实现了一个使用随机探测来解决冲突的哈希表.假设存在冲突,解决方案的工作方式如下:

1. 对象的完整(32位)散列用于为线性同余随机数生成器设定种子.
2. 生成器生成32位数字,并采用模数来确定哈希表中接下来要探测的位置.

这具有非常好的属性,无论模数空间中有多少哈希冲突,只要在完整的32位哈希空间中存在很少的冲突,查找和插入时间预期为O(1).由于探测序列是伪随机的,因此与线性探测不同,模数空间碰撞不会产生聚类行为.由于整个系统是开放式地址,并且不在任何地方使用链接列表,因此与链接不同,您不需要在每次插入时执行内存分配.

此外,因为散列的大小通常是地址空间的大小(32位机器上的32位),所以根本不可能在地址空间中容纳足够的项以在完整的32位散列中导致大量的散列冲突良好的哈希方案下的空间.

那么,为什么随机探测这种不受欢迎的碰撞解决策略呢？

Answer 1

使用线性查找(例如双重哈希)的原因之一是缓存局部性.通过使第二个(rehash)函数成为一个小整数的加法,大多数机会是你会遇到相同的缓存行.这对于大型哈希来说非常重要.

由于其简单性,可能会使用链式哈希.

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).
...

对我来说，当然看起来像一个线性同余 RNG！

请注意，此类 RNG 的完整状态只有i位（必须如此，以避免重新访问条目），因此您无法有意义地使用“对象的完整（32 位）哈希值”来种子RNG。Python 最初使用哈希中的i位来为j播种。如果再次发生冲突，它会从散列中获取另外 5 位并将它们放入混合中。（阅读该评论的其余部分，特别是其中谈到PERTURB_SHIFT.) It continues that way, adding more bits with each collision, until it has used up the whole hash code. This way Python uses a decent amount of whatever randomness the hash code offers, and the code is simple and fast.

这是我读过的一些最好的代码。它在Beautiful Code的第 18 章中有介绍。所以我想说你正在做某事！