知识卡片
墓碑保留被删除后的搜索路径
开放寻址若把中间槽直接改为空,查询可能在这里停止,漏掉更后面的同桶键。墓碑把“原来有人、现在删除”和“从未占用的空槽”区分,使查询继续经过删除位置。
墓碑可被复用,但插入不能一遇墓碑就断定后面没有同键,应先确认是否需要更新已有键。墓碑积累会增加探测成本,重建或其他正确维护探测链的删除方法也可选择,并非所有开放寻址都只能墓碑删除。
结构图:
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 都代表空桶,都可以放置键值对。但不同 的是