本节解释线性探测配合墓碑标记时的一般删除与查找原理。请先自行尝试练习,再阅读下面的解释与例子。
为何不能把删除位置直接设为空
哈希函数选出主位置,但碰撞时需要规则寻找另一位置。线性探测把有 个位置的表编号为 。
定义 5.2.1
(探测序列)
若键 的主位置是 ,其探测序列为
从 起计,第 次探测检查位置 。
这个序列恰好遍历每个位置一次,即使 不是素数也一样。因此即使没有从未使用的位置,也必须在最多 次探测后停止。
定义 5.2.2
(位置的状态)
每个位置恰有三种状态之一:从未使用、带键和值的存活记录,或已删除(墓碑)。
从未使用与已删除都没有存活记录,但查找时意义不同。遇到匹配的存活键就找到了;遇到墓碑则继续;若表一直按以下规则维护,遇到从未使用的位置便可判定不存在。若之前仍未作出判断,完成全部 次探测也可判定不存在。
插入、删除与重复键
定义 5.2.3
(带墓碑的查找、插入与删除)
每项操作都沿键 的探测序列进行,最多探测 次。
- 查找。 在首个存有 的存活位置停止,并返回其值。在首个从未使用的位置,或完成 次探测后,以“不存在”停止。遇到墓碑和存有其他键的存活位置则继续。
- 插入。 记住首个遇到的墓碑,但继续探测。若键已存活,就在该位置更新其值。若遇到从未使用的位置, 必不存在:有已记下的墓碑就放在墓碑,否则放在该从未使用的位置。若 次探测都找不到 或从未使用的位置,有墓碑就放在已记下的墓碑;没有墓碑则报告表已满。
- 删除。 先查找。找到键就把其位置标记为已删除;若键不存在,表保持不变。
若不完成扫描就立即使用较早的墓碑,可能会为路径更后处仍然存活的键产生重复条目。表满时仍可更新已有键。墓碑保留了探测路径经过该删除位置的所有存活键的查找路径。把所有存活记录正确地重新插入新表,可以清除墓碑。
例子:绕回与更新
例题 5.2.4
(绕回、墓碑与更新)
取 ,这里非负整数键使用 。在新表依次插入 、、,三者的主位置均为 ,分别放在 。删除键 ,在 留下墓碑。
| 操作 | 依次检查的位置 | 结果 |
|---|---|---|
| 查找 17 | 5, 0, 1 | 在 1 找到;0 的墓碑不会终止查找。 |
| 插入 17,值为 C | 5, 0, 1 | 更新位置 1;不要在 0 再插入一个 17。 |
| 插入 23,值为 d | 5, 0, 1, 2 | 位置 2 从未使用,故 23 不存在;重用首个墓碑 0。 |
操作后位置 分别存有键 ,位置 仍从未使用。最后一次插入探测超过最终放置位置,因为必须先排除表中已有 。
反例模式
用“从未使用”代替墓碑来删除
假设上面的例子中,删除 时在位置 写入“从未使用”,而不是墓碑。此时表中的存活记录是位置 的键 和位置 的键 。查找 时先探测位置 (另一个键),再探测位置 ,它从未使用,于是以“不存在”停止。但 其实存活于位置 ,答案是错的。同一张表还会让之后插入 时在位置 放入第二个副本。
失败的原因正是下一节的不变量被破坏:位置 在 的探测路径上、在其存储位置之前,却是从未使用。删除必须写入墓碑,让查找可以越过,这样已存储键的路径上才不会出现从未使用的位置。
例题 5.2.5
(没有从未使用位置的表)
取 、。插入 :它们放在位置 ,表中全是存活位置。更新 的值需探测位置 ,即使表已满也能成功。插入新键 则探测 ,找不到匹配、从未使用的位置或墓碑,就报告表已满。
现在删除 ,在位置 留下墓碑。再插入 :探测位置 (键 )、位置 (墓碑,记住)和位置 (键 )。完成全部 次探测,没有遇到从未使用的位置或键 ,所以 不存在,放在已记下的墓碑,即位置 。其后查找不存在的键 (主位置 )会探测 ,让它结束的是 次探测的上限。
例题 5.2.6
(墓碑使失败查找变长)
取 、。把 插入位置 ,然后删除 和 ,只有键 仍然存活。查找 ,其主位置为 :位置 是另一个键,位置 和 是墓碑,位置 从未使用。因此查找作了四次探测才报告不存在,尽管只有一个存活条目。反复插入与删除可以让大部分位置都是墓碑,那时失败查找可接近 次探测。重建到新位置可使计数重置。
常见错误
(未完成扫描就在首个墓碑插入)
在第一个例子中,再次插入值为 的 ,但一见到首个墓碑(位置 )就放在那里。位置 和 便都存有存活的 。删除 时先找到位置 并把它变成墓碑;其后查找 会越过它,在位置 找到旧条目。已删除的键带着过时的值重新出现。扫描必须持续到找到该键或确定它不存在,这时才可使用墓碑。
常见错误
(探测没有上限)
对第二个例子中已满的表,若查找 时只在从未使用的位置停止,就永远不会停止:没有这样的位置,探测下标会无限绕圈。“最多探测 次”是算法的一部分,不是优化。同一个上限也限制插入:没有从未使用位置的表,插入也必须在 次探测后停止。
停止规则为何正确
假设表初始时全部从未使用,且所有更新均遵循上述规则。
命题 5.2.7
(带墓碑的线性探测的不变量)
从全部从未使用的表开始,经过任意一串查找、插入和删除之后,下列两项恒成立。
- 每个键至多出现在一个存活位置。
- 若键 存活于位置 ,则 的探测路径上从主位置起、直到 之前(不含 )的位置,没有从未使用的位置。
证明
(从未使用的位置只会减少)
初始时没有存活位置,两项显然成立。下面证明每项操作都保持它们。
查找不改变任何东西。更新存活键的值不改变位置状态。删除把一个存活位置变成墓碑:该处的键不再存活,涉及它的条件随之消失;其他存活键的位置与路径不变,路径上各位置的“从未使用”状态也与之前相同。
考虑插入 。若 已存活,扫描到达它的位置并更新其值,其余不变。否则,扫描在它覆盖的路径部分找不到 的存活副本;它在首个从未使用的位置停止,或在完整的 个位置循环后停止。由第二项,存活的 不可能位于首个从未使用的位置之后,也不可能在整个循环之外,所以 不存在,放入一个位置后至多有一个存活副本。所选位置是首个经过的墓碑,或扫描停止处的从未使用位置。在它之前路径上的位置都已检查过,并且都不是从未使用,否则扫描早已在该处停止。所以 满足第二项。
最后,放入 是把墓碑或从未使用位置变成存活位置。从未使用位置的数目只会减少,也没有墓碑或存活位置会再变回从未使用。原来路径在存储位置之前没有从未使用位置的键 ,路径上仍然没有。因此两项持续成立。
证明透视
为何墓碑不等于从未使用
使查找正确的不变量具有单调性:从未使用位置的集合只会缩小,因为插入填满位置,删除写入的是墓碑而非从未使用。形如“我的位置之前没有从未使用位置”的条件,因此只会受益于各项更改,不会被破坏。唯一性则依赖另一项要素:插入在写入之前要扫描到能证明该键不存在,所以首个墓碑只是候选位置。去掉第一项要素,删除就可能抹去某个键的路径,如反例所示;去掉第二项,更新就可能产生重复。重建到新位置同样安全,因为它从没有存活位置的表开始,并按同样规则重新插入。
命题 5.2.8
(查找的正确性)
在上述不变量下,查找 至多检查 个位置。若 存活于表中就返回其值,否则报告不存在。
证明
(扫描不会越过存活的键)
规则规定最多探测 次。设 存活于位置 。由第二项,路径上 之前没有从未使用的位置,所以查找不会提前以“不存在”停止。它只会越过墓碑和存有其他键的位置;由唯一性,首个匹配的存活位置就是 ,所以它到达 并返回该处的值。
设 不存活。没有任何探测找到匹配的存活位置,所以查找只会以“不存在”结束,即在首个从未使用的位置,或完成 次探测之后。它没有漏掉任何存活副本,因为根本没有。
这些结论依赖维护不变量,任意损坏的表未必符合。
概念视角几何
在圆周上阅读不变量
把 个位置按编号顺序放在一个圆周上。若有位置从未使用,这些位置就把圆周切成若干段弧。第二项不变量说的是:每个存活键 与其主位置 在同一段弧上,并且沿编号递增方向看,位于 处或其后。因此从 出发的查找,在到达 之前不会碰到切口。若没有从未使用的位置,这段弧就是整个圆周,而 次探测的上限便取代了切口的作用。
成本与练习
每次操作最多探测 个位置,故最坏探测成本为 ; 个位置使用 空间。即使存活记录很少,大量墓碑仍可能使失败查找很长。要主张一般的期望常数时间,必须另加哈希与占用情况的假设,不能只凭有哈希函数就得出。
快速检查
(取 、,插入 3、7、11 后删除 7。查找 11 时依次检查哪些位置?为何首个墓碑不能结束查找?)
解答 · 答案
键 放在位置 ;键 的主位置是 ,放在位置 ;键 的主位置是 ,发现位置 和 都已占用,放在位置 。删除 在位置 留下墓碑。查找 依次检查位置 ,在位置 找到。位置 的墓碑只是记录曾经有键在那里,而 是在位置 被占用时放到它后面的。若查找在墓碑处停止,就会错误地报告 不存在。
快速检查
(若每个位置不是存活就是已删除,且没有存活键 ,分别说明有墓碑和没有墓碑时如何插入 。为何必须限制扫描次数?)
解答 · 答案
有墓碑时,扫描全部 个位置而找不到 ,记住首个遇到的墓碑,并把 插入该处。没有墓碑时,每个位置都存有其他键,表已满,插入应报告失败。必须在 次探测后停止,因为没有从未使用的位置可以结束扫描;没有上限,探测下标会无限绕圈。
快速检查
(解释为何立即在首个墓碑插入会破坏键的唯一性。构造一个更后位置有匹配存活键的简短例子。)
解答 · 答案
墓碑并没有说明该键在路径更后处是否已经存活。取 、,插入 ,它们占用位置 。删除 ,在位置 留下墓碑。若再次插入 时立即放在首个墓碑,位置 就有第二个存活的 ,排在位置 的旧条目之前。这时两个存活位置存有键 ,第一项不变量不成立。正确的插入会继续到位置 ,发现 已存活,就更新它。