从线性探测转向二次探测(哈希碰撞)

Question

我目前使用线性探测器的实现是使用线性探测,现在我想转向二次探测(以后再进行链接,也可能是双重哈希).我已经阅读了一些文章,教程,维基百科等...但我仍然不知道我应该做什么.

基本上,线性探测的步长为1,这很容易做到.当从哈希表中搜索,插入或删除元素时,我需要计算哈希值,为此我执行此操作:

index = hash_function(key) % table_size;

然后,在搜索,插入或删除I循环通过表时,直到找到一个空闲桶,如下所示:

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 */);

对于二次探测,我认为我需要做的是改变计算"索引"步长的方式,但这是我不明白应该怎么做的.我见过各种代码,而且所有代码都有所不同.

此外,我已经看到了一些Quadratic Probing的实现,其中哈希函数被改变为适应(但不是全部).是真的需要改变还是我可以避免修改散列函数并仍然使用二次探测？

编辑: 在阅读了以下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？

Answer 1

如果表的大小是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 ² + 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. 当我们使用模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. 因此,假设少于n个不同的值(在步骤2中)必须是假的.

(如果表格大小不是 2的幂,则在步骤10中分崩离.)