7

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

  1. 对象的完整（32 位）散列用于播种线性同余随机数生成器。
  2. 生成器生成 32 位数字并取模来确定哈希表中接下来要探测的位置。

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

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

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

4

5 回答 5

7

使用线性查找（例如double hasing）的原因之一是缓存局部性。通过使第二个（重新散列）函数成为一个小整数的加法，您很可能会遇到相同的缓存行。这对于大哈希非常重要。

由于其简单性，可能会使用链式哈希。

于 2009-11-10T18:32:42.113 回答
4

可能的原因是线性或二次探测

  • 具有相同的最坏情况时间复杂度（O（表格大小））
  • 具有相同的最佳情况时间复杂度 (O(1))
  • 更容易实现
  • 比好的 RNG 更快（因为速度是哈希表的主要卖点）

但我不确定。您是否使用另一种冲突解决方案实现了自己的哈希表并在不同情况下比较了两者？那将是非常有启发性的。

于 2009-11-10T18:30:55.207 回答
4

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位——必须是，以避免重新访问条目——所以你不能有意义地使用“[t]he full (32-bit) hash of an object”来播种随机数发生器。Python 最初使用哈希中的i位为j播种。如果再次发生冲突，它会从哈希中获取另外 5 位并将它们扔进混合中。（阅读该评论的其余部分，特别是它谈到的地方。）它继续这种方式，在每次碰撞时添加更多位，直到它用完整个哈希码。通过这种方式，Python 使用了相当数量的哈希码提供的随机性，并且代码简单快速。PERTURB_SHIFT

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

于 2009-11-19T22:16:33.117 回答
0

你不会有这样的问题，即插入到一个非稀疏填充的表中，不能保证在开始迭代重复元素之前你会命中哈希表的所有元素吗？

结果插入时间不会被很好地定义。

于 2009-11-10T18:23:14.537 回答
0

我认为随机散列没有被大量使用的原因是，当从 32 位散列计算一个小的散列值时，散列冲突很容易发生，除非散列函数有“错误”，在这种情况下，有一个散列函数的所有 32 位都匹配的可能性很大（例如，因为只有部分密钥用于计算散列）。如果散列函数不错，并且负载因子相当低，线性和二次探测提供良好的缓存局部性（请记住，大多数散列冲突将通过只查看一个额外的项目来解决，线性和二次探测都是第一个猜测之后的那个）。在所有键映射到相同值的情况下，线性探测提供了更好的性能，有时即使它们映射到少量值。

于 2011-01-07T23:56:52.463 回答