知识卡片
碰撞处理决定桶内查找成本
不同键落到同一桶叫碰撞,可用链表保存多个项,查找时逐项核验;也可按探测规则使用其他空槽。链头插入便宜,链越长查找越贵,最坏可退化为线性。
排序链可在超过目标时提前停止某些失败查找,但仍有排序维护成本。插入也须定义重复键是更新、拒绝还是保留多个值,不能让同桶被误当同键。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 7.19 哈希算法 · 查看原书依据
这叫作碰撞。 图7-41 哈希碰撞 我们通过用哈希链替换桶来解决这个问题,哈希链最简单的形式是单链表,如图7-42所示。 图7-42 哈希链 在哈希链管理中有许多权衡。我们可以在链的头部插入碰撞,如图7-42所示,因为插入速度很快。但是随着链变长,查找速度会减
参考来源
- 位置:《计算机系统解密》7.19 哈希算法(来源项目book-sources,源文件:extracted/计算机系统解密/_epub-src/text/part0086.html)
- 结论依据:本项全部正文与图表实际读取,区分作者示例、推导与实现边界;纠错另有明确说明。
- 原始内容:这叫作碰撞。 图7-41 哈希碰撞 我们通过用哈希链替换桶来解决这个问题,哈希链最简单的形式是单链表,如图7-42所示。 图7-42 哈希链 在哈希链管理中有许多权衡。我们可以在链的头部插入碰撞,如图7-42所示,因为插入速度很快。但是随着链变长,查找速度会减