从线性探测转向二次探测（哈希冲突）

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

基本上，线性探测的步长为 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 */);

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

另外，我已经看到了二次探测的一些实现，其中哈希函数被更改以适应这种情况（但不是全部）。是否真的需要进行这种更改，或者我可以避免修改哈希函数并仍然使用二次探测吗？

EDIT:在阅读了 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 倍？

如果您的表大小是 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 */);

Instead of looking at offsets 0, 1, 2, 3, 4... from the original index, this will look at offsets 0, 1, 3, 6, 10... (the i^th probe is at offset (i*(i+1))/2, i.e. it's quadratic).

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

这是证明的草图：

1. 给定一个 n 的表大小，我们想要证明我们将得到 n 个不同的值 (i*(i+1))/2 (mod n)，其中 i = 0 ... n-1。
2. 我们可以用反证法来证明这一点。假设有少于 n 个不同的值：如果是这样，则 i 在 [0, n-1] 范围内必须至少有两个不同的整数值，使得 (i*(i+1))/2 (mod n ）是一样的。称这些为 p 和 q，其中 p
3. 即 (p * (p+1)) / 2 = (q * (q+1)) / 2 (mod n)
4. => (p² + p) / 2 = (q² + q) / 2 (mod n)
5. => p² + p = q² + q (mod 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. As we are working modulo 2n, we must also deal with the tricky case where both factors are non-zero, but multiply to give 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 个不同值的假设必定是错误的。

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