我目前对哈希表的实现是使用线性探测，现在我想转向二次探测(后来转向链接，也可能是双哈希)。我已经阅读了一些文章、教程、维基百科等......但我仍然不知道我应该做什么。
基本上，线性探测的步长为 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？
最佳答案
您不必修改二次探测的哈希函数。二次探测的最简单形式实际上只是将结果平方添加到计算位置而不是线性 1、2、3。
有一个很好的资源 here 。以下内容取自那里。这是使用简单多项式 c(i) = i^2 时最简单的二次探测形式:
在更一般的情况下，公式是:
你可以选择你的常量。
但是请记住，二次探查仅在某些情况下有用。正如 Wikipedia entry 所说:
编辑: 与计算机科学中的许多事物一样，二次探测的精确常数和多项式是启发式的。是的，最简单的形式是 i^2 ，但您可以选择任何其他多项式。维基百科给出了 h(k,i) = (h(k) + i + i^2)(mod m) 的例子。
因此，很难回答您的“为什么”问题。这里唯一的“为什么”是你为什么需要二次探测？在其他形式的探测和获取聚簇表时遇到问题？或者这只是家庭作业，或自学？
请记住，到目前为止，哈希表最常见的冲突解决技术是链接或线性探测。二次探测是一种可用于特殊情况的启发式选项，除非您非常清楚自己在做什么，否则我不建议使用它。
关于c - 从线性探测转向二次探测(哈希冲突)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2348187/