知识卡片
删除槽不能直接置空
开放寻址查找遇到真正空槽即可停止,因为插入时也会停在该槽。
若删除旧键时直接置 NIL,后续键的探测路径会被截断,导致误判不存在。
墓碑标记 DELETED 保持路径可穿过,同时允许日后复用槽位;积累墓碑会改变搜索成本分析。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第11章 散列表 · 查看原书依据
it would be a mistake to mark that slot as empty by simply storing NIL in it.
参考来源
- 位置:《算法导论(第4版)》第 11 章 11.4 节(`OEBPS/chapter011.xhtml`,文本字符 [46500, 49500))。
- 结论依据:原文解释空槽停止条件、直接清空的错误及 DELETED 在插入/搜索中的不同处理。
- 原始内容:it would be a mistake to mark that slot as empty by simply storing NIL in it.