知识卡片
碰撞定位后还要核对键
哈希只能缩小候选范围,不同字符串可以有相同散列值;按桶数取模后,不同散列值也可能进入同一桶。桶内链表必须逐个比较原始key,不能只靠哈希相同判等。若链长增长,桶内搜索仍退化到O(n),需同时考虑散列质量、装载与再分布策略。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 05 同步
原书出处 · 1 处
- · 查看原书依据
在查找一个键-元素对的时候就需要进行两次对比。第一次是对比键散列值,从而找到对应的散列桶;这在前文所述的散列段实现中已经有所体现。第二次是通过单链遍历桶中所有的键-元素对,逐一对比键本身。
参考来源
- 位置:《Go并发编程实战(第2版)》第05章《同步》(来源项目book-sources:extracted/Go并发编程实战(第2版)/_epub-src/OEBPS/text00000_split_009.html;归一字符[43518,43612))
- 结论依据:原文碰撞、取模映射及图中O(n)说明桶内原键比较不可省略。
- 原始内容:在查找一个键-元素对的时候就需要进行两次对比。第一次是对比键散列值,从而找到对应的散列桶;这在前文所述的散列段实现中已经有所体现。第二次是通过单链遍历桶中所有的键-元素对,逐一对比键本身。