我最近一直在学习哈希表。有几个碰撞解决方案的例子，其中之一是二次探测。为什么有人会使用二次探测？他知道哈希表总是不到一半吗？如果是这样，他为什么一开始就使用这么大的桌子？
问问题
4675 次
2 回答
2
为什么有人会使用二次探测？
假设我们需要一些碰撞解决算法，
二次探测在封闭哈希表中可能是一种更有效的算法，因为它更好地避免了线性探测可能发生的聚类问题，尽管它不是免疫的。
二次探测并不完美，但它确实提供了一些优于替代方案的优势：
二次（或其他形式）链接的优点是
- 更简单的存储管理逻辑（无动态分配）
- 更快的插入（因为存储更简单）
- 总体上减少存储需求
他知道哈希表总是不到一半吗？
不必要; 这取决于使用的调整大小策略（如果有）。
考虑你在 QP 上的学习主要是教育性的。根据我的经验，实际的哈希表实现并不经常使用开放寻址。
于 2013-04-13T20:47:32.050 回答
1
Quadratic rehash 是一种非常简单快速的避免线性哈希聚类问题的方法。它通常仅在表大小为素数时使用（由于其他原因也可能很好）。
为避免担心“桌子半满”，最简单的方法是在某个时候切换到线性探头。（您可以将这种切换的阈值测试放在通常的if (index >= size) {index -= size;}块中，以避免任何性能损失。
于 2013-04-14T01:47:53.953 回答