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

Question

的练习题

问题
1.Linear 探索意愿（圈选一个）：
i.gradually 随着插入的值越来越多，性能会下降
ii.May找不到位置就下次插入
iii.None 以上

2.Quadratic 探索意愿（圈选一个）：
i.gradually 随着插入的值越来越多，性能会下降
ii.May找不到位置就下次插入
iii.None 以上

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

我同意问题 1 的回答。线性探测将探索所有可能性，并在需要时换行到哈希表的开头。因此它将在下一次插入时找到一个位置。如果您插入一堆映射到同一个桶或接近一个桶的值，则会导致聚类并且性能会下降。
我明白为什么问题 2 的答案不是 i。二次增量概率不同的增量以避免聚类问题。然而，有些人可以解释二次探测背后的直觉 "may not find a location on the next insertion"
二次探测函数定义为（来自 Quadratic Probing）
第 n 个探测器是 ((h(k) + n²) mod TableSize) 直到探测器达到零（未占用）

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

Answer 1

在某处一定有这方面的证据。但是，在大多数情况下，我看不到二次探测如何影响每个桶。

假设 table 大小为 7，h(k) 为 0。对于第 i 次迭代，probe = i^2 mod 7。我测试了所有 i 小于 10,000 并且对于任何 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

要找出 h(k) + n^2 是否搜索所有可能性，您需要找出 n^2 是否占据所有可能的值 mod 散列 table 大小 - 假设 N .所以你需要知道通过选择n的所有N种可能性是否可以让n^2占据所有N种可能的不同值。

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

示例 - 工作 mod 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 - 事实上这个例子足以表明你不能保证搜索所有可能的槽，但上面的数学足够简洁，比我的算法更可靠，同时也表明这里的行为是非常普遍的。

Answer 3

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

在下面的示例中，我确实看到二次探测无法在与相同结果键发生冲突的情况下找到位置。

假设哈希 table 大小为 7。

这里是要插入的号码 23, 39, 9, 16, 30。

h(k, i) = [h(k) + sqr(i)] mod 7 其中 h(k) = k mod 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 mod 大小) 等于 2 的任何密钥 k 都是这种情况（例如 37、44、51、58 等

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

How can quadratic probing fail to find a location on the next insertion while linear probing always finds one?

java

algorithm

hash

quadratic-probing

linear-probing