language-agnostic - 为什么随机探测在哈希表实现中没有更流行？

Question

根据各种来源，例如 Wikipedia 和 Google 发现的各种 .edu 网站，哈希表解决冲突的最常见方法是线性或二次探测和链接。随机探查被简要提及但没有给予太多关注。我已经实现了一个哈希表，它使用随机探测来解决冲突。假设有碰撞，解析工作如下:

对象的完整(32 位)散列用于作为线性同余随机数生成器的种子。

生成器生成 32 位数字，并采用模数来确定哈希表中的下一个要探测的位置。

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

此外，因为散列的大小通常是地址空间的大小(在 32 位机器上为 32 位)，所以在地址空间中放置足够多的项来在完整的 32 位散列中导致大量散列冲突是根本不可能的良好的散列方案下的空间。

那么，为什么随机探索这种不受欢迎的冲突解决策略呢？

Answer 1

使用线性查找(例如 double hasing )的原因之一是缓存局部性。
通过将第二个(rehash)函数添加为一个小整数，您很有可能会遇到相同的缓存行。这对于大型哈希非常重要。

由于其简单性，可能会使用链散列。