知识卡片
哈希碰撞仍需处理
不同字符串仍可能产生相同的有限位宽哈希值。Monkey教学实现只用类型和哈希数字作map键,没有在命中后进一步区分碰撞的原始字符串,因此不能承诺所有不同字符串都能正确共存。书中提到链式法与开放寻址但未实现;这是适用边界,不应写成哈希函数已经消除碰撞。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 扩展解释器 · 查看原书依据
虽然可能性很小,但拥有不同Value的字符串仍可能具有相同的哈希值。当hash/fnv包为不同的值生成相同的整数时就会发生这种情况,这就是所谓的哈希碰撞。遇到这个问题的概率不大,但你要了解一些解决这个问题的众所周知的技术,例如单链法和开放式寻址法。限于篇幅,本书不会实现这些用于解决哈希碰撞
参考来源
- 位置:《用Go语言自制解释器》第4章《扩展解释器》(spine08;来源项目book-sources;extracted/用Go语言自制解释器/_epub-src/OEBPS/Text/epub_0008.html)。
- 结论依据:原文与相邻实现解释该机制及其约束;内容限定为本书Monkey教学实现。
- 原始内容:虽然可能性很小,但拥有不同Value的字符串仍可能具有相同的哈希值。当hash/fnv包为不同的值生成相同的整数时就会发生这种情况,这就是所谓的哈希碰撞。遇到这个问题的概率不大,但你要了解一些解决这个问题的众所周知的技术,例如单链法和开放式寻址法。限于篇幅,本书不会实现这些用于解决哈希碰撞