java - 碰撞分辨率 : Quadratic Probing vs. 单独链接

Question

好的，所以我一直在用哈希表和不同的冲突解决问题做一些实验。我试图找出哪个更有效地进行查找，一个使用单独链接或二次探测来解决冲突的哈希表。我的结果表明，即使对于 0.4 或 0.2 等小负载因子，单独链接也比二次探测更快。是这种情况还是我的结果有误？

Answer 1

两种方法之间的 处理成本 的差异是
(带链接)
- 一个间接，即指针解引用
对比
(二次探测)
- [简单但复合] 算术公式的评估
- 索引到新位置
- 可能的重复(由于探测值和存储在这些位置的非目标值之间发生冲突；链接不必担心。

因此，链接速度更快应该不足为奇 ；指针取消引用是大多数 CPU 的“ native ”指令，与索引数组的指令相当(在大多数情况下相同)，将算术运算和可能的冲突作为不利于探测的开销。最简单的探测序列公式将需要一些 CPU 指令(初始化 stepNr，通常是 stepNr 的一些移位，添加到当前位置/探测)，这本身比指针取消引用慢几倍。 (可能的警告:请稍后参阅“编辑”，因为它讨论了链接如何导致更多 CPU 级缓存未命中，从而使其效率低于线性探测)

二次(或其他形式)链接的优点是

更简单的存储管理逻辑(无动态分配)

更快的插入(为了更简单的存储)

总体上降低了存储要求

从非常广泛的角度考虑空间与速度(或插入时间与搜索时间)的折衷，链接的存储开销(主要用于指针本身，不考虑可能的堆管理开销)用于 存储[探测的结果]“探测位置”的预先计算值 。由于这些计算很容易完成，链接方法在搜索时更快。
编辑 (感谢 Ants Aasma)
这个论点[关于预先计算的位置]的一个警告是，在现代 CPU 及其缓存上，运行小计算的成本可能远低于缓存未命中时访问 [数据] 内存的成本。这表明顺序探测 (或更普遍地使用产生物理上靠近碰撞点的位置的探测函数)可能优于链接策略，因为缓存未命中率较低。从这个角度来看，纯顺序探测方法是探测函数中最好的，因为它的计算非常简单，但更重要的是因为它最大化了缓存命中的几率。考虑到这一点，当散列函数具有良好的分布并且负载因子很小(因此在初始冲突后具有短/局部搜索路径) 应该尝试使用线性(或非常局部)探测方法 ；然而，应该避免探测提供非物理本地搜索路径的函数。

很难对问题 中提到的实验进行具体评论，例如不知道散列的大小(如果该大小与 CPU 中的字/寄存器的大小匹配，则算术可以更快)，或者不知道散列的大小碰撞率(让我们假设一个好的、分布良好的散列函数)。
当您不断尝试这个时，收集一组单独的时间/统计数据来访问具有哈希槽的项目与产生冲突的项目会很有趣。

“...even for small load factor...”中的“even”表示您期望链接的相对优势应随着负载的增加而进一步增加，因此碰撞变得越来越多。我也希望情况会如此。
此外，增加负载可能说明 探测 的另一个缺点:探测周期的情况和/或更一般地，当没有空间容纳特定项目时。