冲突解决：二次探测 vs. 链式地址法

Question

好的，我一直在进行哈希表和不同冲突解决问题的实验。我正在尝试弄清楚对于查找来说哪种更有效：使用分离链接还是二次探测进行冲突解决的哈希表。我的结果表明，即使对于小的负载因子（例如0.4或0.2），分离链接也比二次探测更快。这是真的吗，还是我的结果有误？

- user131441

Answer 1

使用链接法（chaining）和二次探测法（quadratic probing）两种哈希表处理方式的处理成本差异在于：
  （使用链接法）
  - 需要一个间接操作，即指针解引用
与
  （使用二次探测法）
  - 需要对一个[简单而复合]算术公式进行计算
  - 对新位置进行索引
  - 由此可能重复进行上述步骤（因为在这些位置存储的非目标值与探针值发生冲突，而链接法不必担心这个问题）。 因此，链接法更快，因为指针解引用是大多数CPU的“本地”指令，与数组索引相比几乎相同，在探测过程中执行的算术运算和可能的冲突成为额外开销，降低了二次探测法的效率。最简单的探测序列公式将需要几个CPU指令（初始化步骤号，通常是一些步骤号位移，加上当前位置/探针），这本身就比指针解引用慢几倍。 （可能的警告：请查看后面的“编辑”，因为它讨论了链接法可能会导致更多的CPU级别缓存未命中，从而使其比线性探测法效率更低）。

二次探测法（或其他形式的探测法）的优点是：

• 更简单的存储管理逻辑（无需动态分配内存）
• 更快的插入速度（由于存储更简单）
• 一般情况下减少了存储要求

在非常广泛的意义上思考空间与速度（或者也可以说是插入时间与搜索时间）的权衡，使用链接法会有存储开销（主要是指针本身，不考虑可能存在的堆管理开销），用于存储[对于探测法来说将是]“探测位置”的预计算值。由于这些计算很容易完成，因此在搜索时链接法更快。
编辑（感谢Ants Aasma）
关于预算位置的论点，需要注意的是，在现代CPU和它们的缓存中，运行小计算的成本可能比访问数据内存时的成本要低得多，因为缓存未命中的比率较低，因此建议使用按顺序探测（或更一般地，使用产生物理上靠近碰撞点的位置的探测函数）来探测，这可能比链接策略更有效。基于这个想法，纯顺序探测方法是最好的探测函数，因为它的计算非常简单，但更重要的是它最大化了缓存命中的几率。因此，在哈希函数具有良好分布且负载因子较小（因此在初始碰撞之后路径短/局部搜索路径）的情况下，应该尝试线性（或非常局部的）探测方法；但应避免提供非物理本地搜索路径的探针函数。

---

很难具体评论问题中提到的实验，例如不知道哈希的大小（如果此大小与CPU中的字/寄存器大小匹配，则算术运算可能更快），或者不知道碰撞比率（假设哈希函数很好，分布均匀）。在进行这方面的实验时，收集访问具有哈希槽的项与产生碰撞的项之间的单独计时/统计数据将会很有趣。

“即使负载因子很小，……”中的“即使”表明了您对链接优势相对于负载进一步增加的期望，因此随着冲突变得更多，链接的相对优势将进一步增加。我也认为这应该是正确的。此外，增加负载可能会显示探测的另一个缺点：在探测周期和/或更一般地没有空间来适合特定项目的情况。

- mjv

---

在当今的硬件中，计算CPU周期不会产生任何有意义的结果。相关的数字是缓存未命中的数量，一个未命中缓存的单个内存访问可能需要几百个周期。这表明，如果哈希函数具有良好的分布，并且负载因子合理，则可以通过进行顺序探测来获得更好的性能。 - Ants Aasma

@John：我建议你也尝试使用“纯线性探测函数”进行实验。正如之前所提到的，重要的是要关注哈希冲突比率，因为当负载因子处于中间水平时，探测方法可能达到最佳状态：在负载较低时，碰撞太少，无法使链接法处于明显劣势；而在负载过高时，探测碰撞的数量开始对探测方法相对于链接法造成不利影响。 - mjv

+1 这个值得不止一个赞，仅仅因为我不理解它。 - Rob Grant

@Robert G，哈哈... 也许我会继续这样做，即提供晦涩难懂的答案和通常华丽但有缺陷的阐述，以便人们给我点赞;-) 说正经的，这个论点相对简单（但可能是我常见的问题之一，概括不清），如果你感兴趣，我可以帮助你理解它（或进一步让你困惑...） - mjv

对于小的负载因子，二次探测法在缓存性能方面与线性探测法相当（因为两者的单冲突行为相同），但在某些哈希值聚集的情况下，它不太可能陷入退化行为。 - supercat