知识卡片

普通读书笔记卡 · 5654.d.1.a.3.a

有限桶必需处理冲突

理解等级:中级

当可能的键比桶更多,不同键映射到同一桶不可避免。冲突本身不是错误,不能正确区分和保存这些键,才会造成错取、覆盖或错删。

增大容量可能缓解碰撞,但不能保证消除所有冲突,相同哈希值甚至会持续同桶。可靠哈希表必须有冲突处理机制,不应以反复扩容直到零冲突作为通用终止策略。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      理论上一定存在“多个输入对应相同输出”的情况 。 对于上述示例中的哈希函数,当输入的key 后两位相同时,哈希函数的输出结果也相同。例如,查询学号为 12836 和20336 的两个学生时,我们得到: 12836 % 1

    参考来源

    - 位置:《Hello 算法--Go版本》第06章《哈希表》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/3.html;spine 2,归一字符[14593,14703)) - 结论依据:原文冲突原因与两个学号同桶、扩容策略实际展开,纠正冲突即错误与扩到无冲突的保证。 - 原始内容:理论上一定存在“多个输入对应相同输出”的情况 。 对于上述示例中的哈希函数,当输入的key 后两位相同时,哈希函数的输出结果也相同。例如,查询学号为 12836 和20336 的两个学生时,我们得到: 12836 % 1