知识卡片

结构图卡 · 5654.d.1.a.3.a.4.a

墓碑保留被删除后的搜索路径

理解等级:中级

开放寻址若把中间槽直接改为空,查询可能在这里停止,漏掉更后面的同桶键。墓碑把“原来有人、现在删除”和“从未占用的空槽”区分,使查询继续经过删除位置。

墓碑可被复用,但插入不能一遇墓碑就断定后面没有同键,应先确认是否需要更新已有键。墓碑积累会增加探测成本,重建或其他正确维护探测链的删除方法也可选择,并非所有开放寻址都只能墓碑删除。

结构图:

flowchart TD
 A[沿探测序列检查] --> B{槽状态}
 B -->|有效键匹配| C[返回目标]
 B -->|有效键不匹配| A
 B -->|墓碑| A
 B -->|从未使用的空槽| D[报告不存在]

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      我们可以采用「懒删除lazy deletion」机制:它不直接从哈希表中移除元素, 而是利用一 个常量TOMBSTONE 来标记这个桶。在该机制下,None TOMBSTONE 都代表空桶,都可以放置键值对。但不同 的是

    参考来源

    - 位置:《Hello 算法--Go版本》第06章《哈希表》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/3.html;spine 2,归一字符[19312,19422)) - 结论依据:实际空洞中断图6-7、墓碑语义及后文插入代码缺陷支持。 - 原始内容:我们可以采用「懒删除lazy deletion」机制:它不直接从哈希表中移除元素, 而是利用一 个常量TOMBSTONE 来标记这个桶。在该机制下,None TOMBSTONE 都代表空桶,都可以放置键值对。但不同 的是