知识卡片
有限桶必需处理冲突
当可能的键比桶更多,不同键映射到同一桶不可避免。冲突本身不是错误,不能正确区分和保存这些键,才会造成错取、覆盖或错删。
增大容量可能缓解碰撞,但不能保证消除所有冲突,相同哈希值甚至会持续同桶。可靠哈希表必须有冲突处理机制,不应以反复扩容直到零冲突作为通用终止策略。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 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