知识卡片

普通读书笔记卡 · 5619.f.7.h.4

碰撞定位后还要核对键

理解等级:中级

哈希只能缩小候选范围,不同字符串可以有相同散列值;按桶数取模后,不同散列值也可能进入同一桶。桶内链表必须逐个比较原始key,不能只靠哈希相同判等。若链长增长,桶内搜索仍退化到O(n),需同时考虑散列质量、装载与再分布策略。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      在查找一个键-元素对的时候就需要进行两次对比。第一次是对比键散列值,从而找到对应的散列桶;这在前文所述的散列段实现中已经有所体现。第二次是通过单链遍历桶中所有的键-元素对,逐一对比键本身。

    参考来源

    - 位置:《Go并发编程实战(第2版)》第05章《同步》(来源项目book-sources:extracted/Go并发编程实战(第2版)/_epub-src/OEBPS/text00000_split_009.html;归一字符[43518,43612)) - 结论依据:原文碰撞、取模映射及图中O(n)说明桶内原键比较不可省略。 - 原始内容:在查找一个键-元素对的时候就需要进行两次对比。第一次是对比键散列值,从而找到对应的散列桶;这在前文所述的散列段实现中已经有所体现。第二次是通过单链遍历桶中所有的键-元素对,逐一对比键本身。