data-structures - 使用二次探测实现哈希表的原因

Question

我最近一直在学习哈希表。有几个碰撞解决方案的例子，其中之一是二次探测。为什么有人会使用二次探测？他知道哈希表永远不会满一半吗？如果是这样，他为什么一开始就使用这么大的 table ？

Answer 1

Why would someone use quadratic probing?

假设我们需要一些冲突解决算法，

Quadratic probing can be a more efficient algorithm in a closed hash table, since it better avoids the clustering problem that can occur with linear probing, although it is not immune.

(From Wikipedia)

二次探测并不完美，但 it does offer some advantages over alternatives:

The advantages of quadratic (or other forms of) chaining are

• simpler logic for storage management (no dynamic allocation)
• faster inserts (for reason of simpler storage)
• reduced storage requirement in general

(from mjv's answer)

Does he know that the hash table will always be less than half full?

不一定；这取决于所使用的调整大小策略(如果有的话)。

考虑您在 QP 上的学习主要是教育性的。实用的哈希表实现不经常使用 open addressing,根据我的经验。