为什么二次探测不能找到下一个插入的位置，而线性探测总是找到一个？

Question

问题

根据答案键（来自链接），1的答案是i，2的答案是ii。

我同意问题1的答案。线性探测将探索所有可能性，如果需要，将其包装到哈希表的开头。因此，它将在下一次插入时找到一个位置。如果插入一组映射到同一个bucket或一个bucket附近的值，将导致集群，性能将降低
我理解为什么问题2的答案不是I。二次增量通过不同的增量进行探测，以避免聚类问题。然而，一些人能解释二次探测“在下一次插入时可能找不到位置”背后的直觉吗？
二次探测函数定义为（从二次探测开始）
n次探测为（（h（k）n²）mod TableSize），直到探测到达零（未占用）

从我在另一个问题“二次探测”中学到的知识来看，二次探测有可能击中每一个桶。与线性探针一样，如果需要，二次探针也应该包装到哈希表的开头。那么，在这个问题中，为什么二次探头不能在下一次插入时找到位置，而线性探头可以？

Answer 1

一定有证据证明这一点。但是，我不明白在大多数情况下，二次探测怎么可能击中每一个桶。

假设桌子的大小是7，h（k）是0。对于第i次迭代，probe=i^2 mod 7。我测试了所有小于10000的I，对于任何I，它的计算结果总是为0、1、2或4。桶3、5和6永远不会被探测。

以下是我使用的脚本：

var hash_of_k = 0;
var table_size = 7;
var iteration_limit = 10000;
var buckets =  new Object();

//Probe buckets
for(var i=0; i<iteration_limit; i++){
  b = (hash_of_k+(i*i)) % table_size;
  buckets[b] = 1;
}

//Report which buckets were probed.
var buckets_probed = '';
for(b in buckets){
  buckets_probed += b + '  ';
}

alert(buckets_probed);

Answer 2

我认为问题是在什么情况下，二次探测根本无法找到下一个位置，以防发生碰撞。

在下面的例子中，我确实看到二次探测在与相同的结果键发生碰撞时无法找到位置。

假设哈希表大小为7。

下面是要插入23, 39, 9, 16, 30数字。

h（k，i）=[h（k）sqr（i）]模式7，其中h（k）=k模式7。

for i = 0, h(k,0) = h(k)
for i = 1, h(k,1) = [h(k) + 1] mod 7
for i = 2, h(k,2) = [h(k) + 4] mod 7
for i = 3, h(k,3) = [h(k) + 9] mod 7

23 --> 23 % 7 = 2

39 --> 39 % 7 = 4

9  --> 9 % 7 = 2 <--- Collision
   2 + 1 = 3

16 --> 16 % 7 = 2 <--- Collision
   2 + 1 = 3 <--- Collision
   2 + 4 = 6

30 --> 30 % 7 = 2 <--- Collision

   2 + 1 = 3 <--- Collision

   2 + 4 = 6 <--- Collision
   2 + 9 = 4 <--- Collision
   2 + 16 = 4 <--- Collision
   2 + 25 = 6 <--- Collision
   2 + 36 = 3 <--- Collision
   2 + 49 = 2 <--- Collision
   2 + 64 = 3 <--- Collision
   2 + 81 = 6 <--- Collision
   2 + 100 = 4 <--- Collision
   2 + 121 = 4 <--- Collision
   2 + 144 = 6 <--- Collision
   2 + 169 = 3 <--- Collision
   2 + 196 = 2 <--- Collision
   2 + 225 = 3 <--- Collision
   2 + 256 = 6 <--- Collision
   2 + 289 = 4 <--- Collision
   2 + 324 = 4 <--- Collision
   2 + 361 = 6 <--- Collision
   2 + 400 = 3 <--- Collision

任何键k（k mod size）等于2（如37、44、51、58等）都会出现这种情况。

Answer 3

为了找出h（k）n^2是否搜索所有可能性，您需要找出n^2是否占用了所有可能的值，例如哈希表大小。所以您需要知道通过选择n的所有N个可能性，是否可以让n^2占用所有N个可能的不同值。

（-n）^2=n^2，所以这里是平方函数的不同输入值，它们产生相同的输出值。因此，不可能产生所有N个不同的输出值，因为不同输入值的结果之间存在冲突。

示例-工作模式7. 1^2 = 6^2 = 1. 2^2 = 5^2 = 4. 3^2 = 4^2 = 2. 7^2 = 0。因此，如果您将输入平方（0, 1, 2, 3, 4, 5, 6)您将获得输出（0, 1, 4, 2, 2, 4, 1)并且您不能产生3、5或6-事实上，这个示例足以表明您不能保证搜索所有可能的插槽，但上面的数学足够简洁，比我的算术更可靠，并表明这里的行为非常一般。