知识卡片

普通读书笔记卡 · 1474.e

碰撞处理有两条路径

理解等级:中级

哈希碰撞指不同键落到同一哈希位置,不能只凭哈希值认定键相等。拉链法让同一桶连接多个条目;开放寻址法在表内按探测序列寻找可用位置。两者在额外指针、数据局部性和装载后的探测成本上各有取舍;判断具体语言的 map 实现时仍要核对其版本。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《Go语言底层原理剖析》第8章《哈希表与Go语言实现机制》8.1节(源文件:`_epub-src/OEBPS/Text/0012.xhtml`) - 结论依据:原文定义碰撞,分别说明拉链法的链式连接、指针与缓存成本,以及开放寻址法的探测策略;本卡只保留通用分类,不沿用原文对旧版 Go map 的线性探测定性。 - 原始内容:哈希碰撞导致同一个桶中可能存在多个元素,有多种方式可以避免哈希碰撞,一般有两种主要的策略:拉链法及开放寻址法。……拉链法将同一个桶中的元素通过链表的形式进行链接……开放寻址法(Open Addressing)……将按某种探测策略操作,直到找到未使用的数组插槽为止。