我最近一直在学习哈希表。这里有一些关于碰撞分辨率的例子，其中之一就是二次探测。为什么有人要用二次探测?他知道哈希表总是少于半满吗?如果是这样，为什么他一开始要用这么大的桌子呢?
为什么有人会使用二次探测?
假设我们需要一些碰撞解析算法，
二次探测在封闭哈希表中可能是一种更有效的算法，因为它更好地避免了线性探测可能出现的聚类问题，尽管它不是免疫的。
(来自维基百科)
二次探测并不完美，但它确实提供了一些替代方案的优势:
二次链(或其他形式)的优点是
- 更简单的存储管理逻辑(无动态分配)
- 更快的插入(为了更简单的存储)
- 一般降低存储需求
(选自mjv的回答)
他知道哈希表总是小于半满吗?
不一定;这取决于所使用的大小调整策略(如果有的话)。
认为你对QP的学习主要是教育性的。根据我的经验，实际的哈希表实现通常不使用开放寻址。
二次散列是一种非常简单、快速的方法，可以避免线性散列的聚类问题。它通常只在表大小为素数时使用(这也可能用于其他原因)。
为了避免担心"表是半满的"，最简单的方法是在某个点切换到线性探针。(您可以将这种切换的阈值测试放在通常的if (index>= size) {index -= size;}块中，以避免任何性能损失。