gpt4 book ai didi

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

转载 作者:搜寻专家 更新时间:2023-11-01 01:58:43 26 4
gpt4 key购买 nike

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

最佳答案

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

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

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

  • 更简单的存储管理逻辑(无动态分配)
  • 更快的插入(为了更简单的存储)
  • 总体上降低了存储要求

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

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

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

    关于java - 碰撞分辨率 : Quadratic Probing vs. 单独链接,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1830597/

    26 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com