哈希表中二次探测的运行时间是多少？

Question

这是一个与 Linear Probing Runtime 类似的问题，但它涉及二次探测。

对我来说 "Theoretical worst case is O(n)" 对于线性探测是有意义的，因为在最坏的情况下，您可能必须遍历每个桶（n 个桶）

二次探测的运行时间是多少？我知道以二次方式进行二次探测 -1, 4, 9, 16, ..... 我最初的想法是它是 log n(exponential) 的一些变化，但没有一致的基数。

Answer 1

如果您的哈希 table 中有 n - 1 个已占用的桶，那么无论您检查空桶的顺序如何，都不能排除您需要测试的可能性n 个桶，然后才找到一个空桶。因此，二次探测的最坏情况不会比 O(n).

好多少。

然而，情况可能更糟：我不是很清楚二次探测是否可以很好地避免多次测试同一个桶。 （如果您选择的步长相对于桶的数量而言是质数，那么这不是线性探测的问题。）我 猜测 二次探测不会重新访问相同的桶足够多次使最坏的情况比 O(n) 更糟，但我无法证明这一点。