4

    我正在做数据结构实践中的一个练习题

问题
   1.Linear Probing 将（圈出一个）：
        i.随着插入更多值，性能会逐渐降低
       ii.可能在下一次插入时找不到位置
       iii.以上都不是

   2.二次探测将（圈一个）：
        i.随着插入更多值，性能逐渐降低
       ii.可能在下一次插入时找不到位置
       iii.以上都不是

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

我同意问题 1 的答案。线性探测将探索所有可能性，并在需要时回绕到哈希表的开头。因此它将在下一次插入时找到一个位置。如果您插入一堆映射到同一个存储桶或靠近一个存储桶的值，则会导致聚类并降低性能。
我明白为什么问题 2 的答案不是 i。二次增量概率通过不同的增量来避免聚类问题。然而，有些人可以解释二次探测“可能在下一次插入时找不到位置”背后的直觉吗？
二次探测函数定义为（来自二次探测）
第 n 个探针为 ((h(k) + n 2 ) mod TableSize) 直到探头达到零（未占用）

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

4

3 回答 3

3

要确定 h(k) + n^2 是否搜索所有可能性，您需要确定 n^2 是否占用了哈希表大小的所有可能值 - 比如说 N。所以您需要知道是否通过选择所有 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 - 事实上这个例子足以表明您不能保证搜索所有可能的插槽，但上面的数学足够简洁，比我的算术更可靠，并且表明这里的行为非常普遍。

于 2015-03-15T06:21:46.867 回答
3

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

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

假设哈希表大小为 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 size）等于 2 的任何键 k（如 37、44、51、58 等），都会出现这种情况。

于 2016-06-25T23:31:37.667 回答
1

一定有证据证明这一点。但是，在大多数情况下，我看不到二次探测如何击中每一个桶。

假设表大小为 7，h(k) 为 0。对于第 i 次迭代，probe = i^2 mod 7。我测试了所有小于 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);

您可以将迭代限制设置得更高，但这似乎并不实际。似乎二次探测的全部意义在于比线性探测更快地找到一个空桶。

于 2015-03-15T06:10:42.310 回答