从线性探测到二次探测（哈希碰撞）的转变

Question

从线性探测到二次探测（哈希碰撞）的转变

chashtablehash-collisionquadratic-probing

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;

因为我看到其他代码示例将其除以2。但是我不明白为什么...

1) 为什么要减去这个步骤？
2) 为什么要将其除以2？

- rfgamaral

请注意，二次探测只在表大小为质数且负载因子小于0.5时才有效；请参阅http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx，了解不同冲突解决策略的概述。 - Christoph

@Cristoph：那个说法并不完全正确。如果表的大小是质数，那么当负载因子<0.5时，保证它能够正常工作；但并不是说这是二次探测器生效的唯一情况。例如，使用2的幂作为表的大小和任意负载因子也可以有效地进行探测（请参见我的答案）。 - Matthew Slattery

@Mathew：'work'和'有效工作'之间有区别；如果负载因子过高，(次要)聚集可能再次成为一个问题 - Christoph

@Cristoph：当然（“任意负载因子”可能是我用词不当；无论使用何种高级探测方法，0.999的负载因子都不是一个好主意）。但是，对于哈希表来说，0.75是一个合理的负载因子，即使使用线性探测（只要哈希函数好），它也能够很好地工作，并且在使用二次探测和2的幂表大小时确实有效（探测访问所有桶，就像线性探测一样，但主要聚集减少了）- 因此，“只有在表大小为质数且负载因子<0.5时，二次探测才有效”这种说法是不正确的。 - Matthew Slattery

2个回答

4

您不需要修改哈希函数来进行二次探测。最简单的二次探测形式只需将连续平方数添加到计算位置，而不是线性的1、2、3。

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

alt text

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

alt text

你可以选择常量。

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

二次探测提供了很好的内存缓存，因为它保留了一些引用的局部性；但是，线性探测具有更好的局部性和更好的缓存性能。二次探测更好地避免了线性探测可能出现的聚集问题，但并非完全免疫。

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

因此，很难回答您的“为什么”问题。这里唯一的“为什么”是为什么您需要二次探测？有使用其他形式的探测并得到聚集表的问题吗？还是只是作业任务或自学？

请记住，迄今为止哈希表最常见的冲突解决技术是链接或线性探测。二次探测是一种启发式选项，适用于特殊情况，除非您非常了解自己在做什么，否则我不建议使用它。

- Eli Bendersky

抱歉，数学公式对我没有帮助。 :( 而且你没有给我比我已经阅读的更多的信息。 - rfgamaral

1

@Nazgulled：我真的不明白你遇到了什么问题 - 而且由于你没有得到其他答案，也许我不是唯一一个。我认为你应该尝试详细阐述你的问题并重新表达它，以便准确地解释你需要什么。 - Eli Bendersky

我看着数学公式，不理解它们，也不知道在代码中该怎么做。我需要知道用语言该怎么做，而不是数学公式。 - rfgamaral

@Nazgulled：我已经对我的答案进行了补充。我希望你意识到，要成功地进行编程，你必须理解公式，或者至少愿意去学习它们。 - Eli Bendersky

这是为了自学目的。我将有一个项目，需要使用哈希表（可能），但为此我将使用链接法，我只想学习不同的方法，以便在最终报告中写出它们，并解释为什么选择其中一种而不是另一种。对于线性探测，当我访问哈希表上的每个桶时就停止查找，但对于二次探测，我应该在何时停止查找？ - rfgamaral

@Nazgulled：我链接的页面有一个讨论——只要表的大小是质数，前M/2（M为大小）个样本就是唯一的。在那里或任何其他关于算法的在线资源中了解更多信息。 - Eli Bendersky

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matthew Slattery · Accepted Answer

如果哈希表的大小是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的幂，就保证会命中哈希表中的每个位置（因此如果有空桶，则保证找到一个）前提是。

下面是一个证明的草图：

假设n为表格大小，我们想证明在 i = 0…n-1 的范围内，(i * (i + 1)) / 2 (mod n) 将给出 n 个不同的值。
我们可以通过反证法来证明这一点。假设有少于n个不同的值：如果确实如此，在范围[0，n-1]中必须至少有两个不同的整数值，使得(i * (i + 1)) / 2 (mod n)相同。称这些为p和q，其中p < q。
即(p * (p+1)) / 2 = (q * (q+1)) / 2 (mod n)
=> (p² + p) / 2 = (q² + q) / 2 (mod n)
=> p² + p = q² + q (mod 2n)
=> q² - p² + q - p = 0 (mod 2n)
分解 => (q - p) (p + q + 1) = 0 (mod 2n)
(q - p) = 0 是平凡情况下的p = q。
(p + q + 1) = 0 (mod 2n)是不可能的：我们的p和q的值在[0，n-1]范围内，且q > p，因此(p + q + 1)必须在[2, 2n-2]范围内。
由于我们是在模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，而我们的奇数因子的质因子中没有一个是2）。
- 但是，（q - p）的最大值为n-1，（p + q + 1）的最大值为2n-2（如步骤9所示），因此两者都不可能是2n的倍数。
- 因此，这种情况也是不可能的。
因此，假设在步骤2中少于n个不同的值是错误的。

（如果表格大小不是2的幂，则在步骤10中会出现问题。）