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

Question

我正在做 Data Structures Practice 的练习题

问题
1.Linear Probing will(圈选一个):
i.随着更多值的插入，性能逐渐下降
ii.下次插入可能找不到位置
iii.以上都不是

2.二次探测将(圈出一个):
i.随着更多值的插入，性能逐渐下降
ii.下次插入可能找不到位置
iii.以上都不是

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

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

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

Answer 1

要查明 h(k) + n^2 是否搜索所有可能性，您需要查明 n^2 是否占用所有可能的值 mod 哈希表大小 - 比如说 N。所以您需要知道是否通过选择所有n 的 N 种可能性你可以让 n^2 占据所有 N 种可能的不同值。

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

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