从线性探测转向二次探测（哈希碰撞）

Question

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

基本上，线性探测的步长为 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/datastructs/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 倍？

Answer 1

您不必修改散列函数为二次探测。二次探测的最简单形式实际上只是增加随之而来的平方计算出的位置，而不是直链1，2，3

的

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

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

你可以选择你的常量。

请，记住，但是，该二次探测只在某些情况下是有用的。作为 Wikipedia条目状态：

  

二次探测提供了良好的存储器   缓存因为它保留了一些   的参考局部性;然而，线性   探测具有更大的局部性和，   因此，更好的缓存性能。   二次探查更好地避免   可与发生聚类问题   线性探测，尽管它不是   免疫

---

修改像在计算机科学许多事情，确切的常量和二次探测的多项式是启发式。是的，最简单的形式是i^2，但你可以选择任何其他的多项式。维基百科给出了h(k,i) = (h(k) + i + i^2)(mod m)的例子

因此，很难回答你“为什么”的问题。唯一的“为什么”，这是为什么你需要二次方的所有探测？经与其他形式的探测和获取群集表的问题？或者是它只是一个家庭作业，或自我学习？

请注意，迄今为止哈希表中最常见的冲突解决技术要么链或线性探测。二次探测可用于特殊情况下，启发式选项，除非你知道自己在做什么的非常好，我不建议使用它。

Answer 2

如果您的表大小是 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...（我^th 探头的偏移量为 (i*(i+1))/2，即它是二次的）。

这保证会命中哈希表中的每个位置（因此，如果有的话，您一定会找到一个空桶） 假如 表的大小是 2 的幂。

---

这是证明的草图：

1. 给定一个 n 的表大小，我们想要表明我们将得到 (i*(i+1))/2 (mod n) 的 n 个不同值，其中 i = 0 ...n-1。
2. 我们可以用反证法来证明这一点。假设不同值少于 n 个：如果是这样，则 i 在 [0, n-1] 范围内必须至少有两个不同的整数值，使得 (i*(i+1))/2 (mod n) 相同。称这些为 p 和 q，其中 p < q。
3. IE。(p * (p+1)) / 2 = (q * (q+1)) / 2 (mod n)
4. =>（p² + p) / 2 = (q² + q) / 2 (mod n)
5. => p² + p = q² + q (模 2n)
6. => q² -p² + 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 (mod 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. 因此，（步骤 2 中）少于 n 个不同值的假设一定是错误的。

（如果表大小为 不是 2 的幂，这在第 10 步就崩溃了。）