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