3

我当前的哈希表实现是使用线性探测，现在我想转向二次探测（后来也转向链接，也许还有双重哈希）。我已经阅读了一些文章、教程、维基百科等……但我仍然不知道我应该做什么。

基本上，线性探测的步长为 1，这很容易做到。在哈希表中搜索、插入或删除元素时，我需要计算一个哈希值，为此我这样做：

index = hash_function(key) % table_size;

然后，在搜索、插入或删除时，我循环遍历表，直到找到一个空闲的存储桶，如下所示：

do {
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) {
        // FOUND ELEMENT

        return;
    } else {
        index = (index + 1) % table_size;
    }
while(/* LOOP UNTIL IT'S NECESSARY */);

至于二次探测，我认为我需要做的是改变“索引”步长的计算方式，但这就是我不明白我应该怎么做的。我见过各种各样的代码，它们都有些不同。

此外，我还看到了一些二次探测的实现，其中散列函数被更改以适应它（但不是全部）。是否真的需要这种更改，或者我可以避免修改散列函数并仍然使用二次探测？

编辑： 阅读下面 Eli Bendersky 指出的所有内容后，我想我明白了。这是http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx的部分代码： 

15   for ( step = 1; table->table[h] != EMPTY; step++ ) {
16     if ( compare ( key, table->table[h] ) == 0 )
17       return 1;
18 
19     /* Move forward by quadratically, wrap if necessary */
20     h = ( h + ( step * step - step ) / 2 ) % table->size;
21   }

有两件事我没有得到......他们说二次探测通常使用c(i)=i^2. 然而，在上面的代码中，它做的更像是c(i)=(i^2-i)/2

我已准备好在我的代码上实现这一点，但我只会这样做：

index = (index + (index^index)) % table_size;

...并不是：

index = (index + (index^index - index)/2) % table_size;

如果有的话，我会这样做：

index = (index + (index^index)/2) % table_size;

...因为我已经看到其他代码示例跳水了两个。虽然不明白为什么...

1）为什么要减去步骤？
2）为什么它会跳水2？

4

2 回答 2

11

如果您的表大小是 2 的幂，则有一种特别简单和优雅的方式来实现二次探测：

step = 1;

do {
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) {
        // FOUND ELEMENT

        return;
    } else {
        index = (index + step) % table_size;
        step++;
    }
} while(/* LOOP UNTIL IT'S NECESSARY */);

不是从原始索引查看偏移量 0、1、2、3、4...，而是查看偏移量 0、1、3、6、10...（第 i个探针位于偏移量（i* (i+1))/2，即它是二次的）。

如果表大小是 2 的幂，则可以保证命中哈希表中的每个位置（因此，如果有一个空桶，则可以保证找到一个空桶） 。

这是一个证明的草图：

  1. 给定一个 n 的表大小，我们想要表明我们将得到 n 个不同的 (i*(i+1))/2 (mod n) 值，其中 i = 0 ... n-1。
  2. 我们可以用反证法来证明这一点。假设有少于 n 个不同的值：如果是这样，则在 [0, n-1] 范围内的 i 必须至少有两个不同的整数值，使得 (i*(i+1))/2 (mod n ) 是一样的。称它们为 p 和 q，其中 p < q。
  3. 即 (p * (p+1)) / 2 = (q * (q+1)) / 2 (mod n)
  4. => (p 2 + p) / 2 = (q 2 + q) / 2 (mod n)
  5. => p 2 + p = q 2 + q (mod 2n)
  6. => q 2 - p 2 + q - p = 0 (mod 2n)
  7. 因式分解 => (q - p) (p + q + 1) = 0 (mod 2n)
  8. (q - p) = 0 是平凡的情况 p = q。
  9. (p + q + 1) = 0 (mod 2n) 是不可能的：我们的 p 和 q 值在 [0, n-1] 范围内，并且 q > p，所以 (p + q + 1) 必须在范围 [2, 2n-2]。
  10. 由于我们正在使用模 2n，我们还必须处理两个因子都非零但相乘得到 0（模 2n）的棘手情况：
    • 观察两个因子 (q - p) 和 (p + q + 1) 之间的差是 (2p + 1)，这是一个奇数 - 所以其中一个因子必须是偶数，而另一个必须是奇数。
    • (q - p) (p + q + 1) = 0 (mod 2n) => (q - p) (p + q + 1) 可以被 2n 整除。 如果 n （因此 2n ）是 2 的幂，则这要求偶数因子是 2n 的倍数（因为 2n 的所有质因数都是 2，而奇数因数的质因数都不是）。
    • 但是 (q - p) 的最大值为 n-1，而 (p + q + 1) 的最大值为 2n-2（如步骤 9 所示），因此两者都不能是 2n 的倍数。
    • 所以这种情况也是不可能的。
  11. 因此，有少于 n 个不同值（在步骤 2 中）的假设一定是错误的。

（如果表大小不是2 的幂，则在第 10 步将分崩离析。）

于 2010-02-28T02:05:00.840 回答
4

您不必为二次探测修改散列函数。最简单的二次探测形式实际上只是将结果平方添加到计算的位置，而不是线性 1、2、3。

这里有一个很好的资源。以下内容取自那里。这是使用简单多项式时最简单的二次探测形式c(i) = i^2：

替代文字

在更一般的情况下，公式是：

替代文字

你可以选择你的常数。

但是请记住，二次探测仅在某些情况下有用。正如维基百科条目所述：

二次探测提供了良好的内存缓存，因为它保留了一些参考位置；但是，线性探测具有更大的局部性，因此具有更好的缓存性能。二次探测更好地避免了线性探测可能发生的聚类问题，尽管它不是免疫的。

编辑：像计算机科学中的许多事情一样，二次探测的精确常数和多项式是启发式的。是的，最简单的形式是i^2，但您可以选择任何其他多项式。维基百科给出了这个例子h(k,i) = (h(k) + i + i^2)(mod m)。

因此，很难回答您的“为什么”问题。这里唯一的“为什么”是你为什么需要二次探测？其他形式的探测和获取聚簇表有问题吗？还是只是家庭作业，还是自学？

请记住，到目前为止，哈希表最常见的冲突解决技术是链接或线性探测。二次探测是一种可用于特殊情况的启发式选项，除非您知道自己做得很好，否则我不建议您使用它。

于 2010-02-27T17:10:09.543 回答