在HashTable中进行二次探测的运行时间是多少？ [英] What is the runtime for quadratic probing in a HashTable?

问题描述

这是一个类似于线性探测运行时的问题但它涉及二次探测。

对于线性探测，理论最坏情况是O（n）是合理的，因为在最坏的情况下，您可能不得不遍历每个桶（n个桶）

运行时会用于二次探测？我知道以二次方式-1,4,9,16，......的二次探测。我最初的想法是它是log n（指数）的一些变化，但是没有一致的基数。

解决方案

如果散列表中存在 n - 1 占用的桶，在检查空桶的顺序时，不能排除在找到空桶之前需要测试 n 桶的可能性。因此，二次探测的最坏情况不能比 O（n）更好。

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

This is a similar question to Linear Probing Runtime but it regards quadratic probing.

It makes sense to me that "Theoretical worst case is O(n)" for linear probing because in the worst case, you may have to traverse through every bucket(n buckets)

What would runtime be for quadratic probing? I know that quadratic probes in a quadratic fashion -1, 4, 9, 16, ..... My initial thought was that it's some variation of log n(exponential) but there isn't a consistent base.

解决方案

If there are n - 1 occupied buckets in your hash table, then regardless of the sequence in which you check for an empty bucket, you cannot rule out the possibility that you will need to test n buckets before finding an empty one. The worst case for quadratic probing therefore cannot be any better than O(n).

It could be worse, however: it's not immediately clear to me that quadratic probing will do a good job of avoiding testing the same bucket more than once. (That's not an issue with linear probing if you choose a step size that is relatively prime to the number of buckets.) I would guess that quadratic probing doesn't revisit the same buckets enough times to make the worst case worse than O(n), but I cannot prove it.

这篇关于在HashTable中进行二次探测的运行时间是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！