开放寻址哈希表删除元素时为什么常用墓碑标记？

简化版

开放寻址中查找依赖连续探测序列。删除元素时如果直接把槽位置空，可能截断后续 key 的查找路径；墓碑标记表示“这里曾经有元素但已删除”，让查找继续探测，同时允许后续插入复用该槽。

详细版

开放寻址没有桶链表，冲突元素会沿着探测规则放到后续槽位。删除时要小心：

• 空槽通常表示“后面不用找了”。
• 如果把中间槽直接设为空，后面的冲突元素可能再也查不到。
• 墓碑槽表示“逻辑删除，但探测不能停止”。
• 插入时可以优先复用遇到的第一个墓碑槽。
• 墓碑太多会拖慢探测，需要定期 rehash 清理。

这题核心是理解墓碑不是为了省事，而是为了保护探测序列不断裂。

完整版教学

一、开放寻址的查找路径是什么

开放寻址把所有元素都放在数组槽位里。发生冲突时，不挂链表，而是按探测规则继续找下一个槽。

hash(key)=3
尝试 3，占用
尝试 4，占用
尝试 5，找到位置

查找时必须沿同样路径走。如果路径中遇到真正空槽，说明这个 key 当初不可能越过空槽插到后面，于是可以停止。

二、直接置空为什么会出错

假设线性探测表如下：

index: 0 1 2 3 4 5
value: _ _ A B C _

A、B、C 的原始 hash 可能都落在 2 附近。现在删除 B，如果把 3 号槽直接设为空：

value: _ _ A _ C _

查找 C 时，从 hash 起点往后探测，遇到 3 号空槽就停止，于是误以为 C 不存在。C 明明在 4 号槽，却被中间空洞截断了路径。

三、墓碑标记如何保护路径

墓碑槽不是空，也不是有效元素，而是第三种状态：已删除。

value: _ _ A DEL C _

查找时遇到 DEL 不能停止，要继续往后找。插入时遇到 DEL 可以记下来，后面如果没找到相同 key，就复用这个槽。

EMPTY：查找可停止
OCCUPIED：比较 key
DELETED：查找继续，插入可复用

这三态区分是开放寻址删除正确性的关键。

四、插入时怎么处理墓碑

插入要同时完成“是否已有相同 key”和“应该放哪里”。遇到第一个墓碑时不要立刻停止，因为后面可能已经存在相同 key。

常见逻辑：

firstDeleted = -1
for each probe slot:
  if slot is DELETED and firstDeleted == -1:
    firstDeleted = slot
  else if slot key equals target:
    update value
  else if slot is EMPTY:
    insert at firstDeleted if exists else EMPTY

这样既能复用墓碑，又不会把同一个 key 插入两次。

五、墓碑太多为什么会拖慢

墓碑保住了正确性，但会增加探测长度。查找不存在的 key 时，必须跨过大量墓碑，直到真正空槽才停止。

例如容量 1000 的表，只有 300 个有效元素，但有 500 个墓碑。逻辑负载看似 30%，探测却可能像 80% 满一样慢。

状态	对查找影响	对插入影响
有效元素	要比较 key	不可直接用
墓碑	不能停止	可复用
空槽	可停止	可插入

所以实现通常会在墓碑比例过高时 rehash，把有效元素重新插入新表，清除墓碑。

六、和拉链法删除有什么不同

拉链法删除节点只需要从链表中摘除，不会截断别的桶的查找路径。开放寻址的元素共享同一条探测路径，删除中间槽会影响后面元素。

记忆钩子：开放寻址里的空槽是“查找终点”，墓碑是“这里删过，但路还没断”。

七、常见误区与追问

• 误区：删除元素直接置空即可。 直接置空可能截断探测序列，让后面的 key 查不到。
• 误区：墓碑越多越好复用。 墓碑太多会拉长查找路径，需要 rehash 清理。
• 误区：插入遇到墓碑就立刻写入。 后面可能已有相同 key，要继续探测确认。
• 追问：拉链法需要墓碑吗？ 通常不需要，删除链表节点不会影响其他桶路径。
• 追问：墓碑算不算负载因子？ 实现上常同时关注有效元素数和占用槽位数，墓碑会影响探测性能。

八、加强记忆

墓碑是开放寻址删除的“路标”。有效元素用于比较，空槽表示路结束，墓碑表示这个位置空出来了但查找还要继续。它用一点状态复杂度换正确性，代价是积累太多后必须清理。