9. 散列删除¶
9.1. 删除¶
从散列表中删除记录时，有两个重要的 考虑事项。
删除一条记录不得妨碍后续的查找。 换句话说，查找过程仍必须经过 这个新清空的槽位，才能到达那些探测序列 经过该槽位的记录。 因此，删除过程不能简单地把槽位标记为空，因为 这会使探测序列中更靠后的记录被隔离。
我们不希望因为删除而使散列表中的位置 变得不可用。 被释放的槽位应当可供将来的插入使用。
这两个问题都可以通过在删除记录的位置放置一个 特殊标记来解决，这个标记称为 墓碑 。 墓碑表示某个记录曾占用该槽位，但 现在不再占用。 如果在沿探测序列查找时遇到墓碑， 查找过程会继续查找。 如果在插入期间遇到墓碑，那么该槽位 可以用来存储新记录。 然而，为避免插入重复的键，查找过程仍然 必须沿着探测序列继续前进，直到找到一个真正 空的位置，以确认表中没有重复项。 不过，新记录实际上会被插入到 遇到的第一个墓碑所在的槽位。
下面是一个练习。
使用墓碑可以让查找正确工作，并允许 重用被删除的槽位。 然而，在一系列插入和删除交替进行的 操作之后，有些槽位会包含墓碑。 这往往会拉长从记录的起始位置到记录本身 的平均距离，超过没有墓碑时 所能达到的距离。 典型的数据库应用会先把一批记录装载 到散列表中，然后进入插入和删除 交替进行的阶段。 在用初始的那批记录装载表之后， 最初的几次删除会拉长记录的 平均探测序列距离（它会 增加墓碑）。 随着时间推移，平均距离会达到一个平衡点，因为 插入会通过填充墓碑槽位来降低平均距离。 例如，在最初把记录装载到数据库之后， 平均路径距离可能是 1.2（即每次查找平均需要 在起始位置之外进行 0.2 次访问）。 在一系列插入和删除之后，由于墓碑， 这个平均距离可能增大到 1.6。 这看起来增幅很小，但它意味着在起始位置之外 的平均距离是删除前的三倍。
这个问题的两种可能解决方案是
删除时进行局部重组，以设法缩短平均 路径长度。 例如，删除一个键后，继续沿着该键的 探测序列前进，把探测序列中更靠后的 记录交换到最近被删除记录所在的槽位 （注意不要使任何键离开它的探测序列）。 这并非对所有的冲突解决策略都有效。
定期对表进行再散列，即把所有记录 重新插入到一个新的散列表中。 这不仅会移除墓碑，还提供了一个 把最常访问的记录放到其起始位置的 机会。
9.2. 散列删除总结问题¶
下面是一些练习题。
恭喜！你已经完成了散列这一教程。 总而言之，一个经过恰当调优的散列系统返回记录的 平均代价不到两次记录访问。 这使它成为已知的、用于存储记录数据库以支持 精确匹配查询的最有效方法。 遗憾的是，在实现范围查询， 或回答诸如"集合中哪条记录的键值最小？" 这样的问题时，散列并不有效。
