为什么可以使用tombstone bucket进行插入？

Question

https://research.cs.vt.edu/AVresearch/hashing/deletion.php

上面的网页是这样写的。

如果沿着探测序列搜索时遇到墓碑，则搜索过程将继续搜索。当在插入过程中遇到墓碑时，该槽可用于存储新记录。

我不太明白为什么第二句话是有效的。假设三个键k1、k2、k3都有相同的散列。利用开放寻址线性探测，它们被插入到哈希表中。哈希表存储桶如下所示。k1位于散列值所指向的位置。

... k1 k2 k3 ...

现在删除k1。哈希表如下所示，其中T表示一个墓碑。

... T k2 k3 ...

然后，我再次插入k3，它首先到达T，然后使用它，所以我在哈希表中得到两个K3。这对我来说没有任何意义。

... k3 k2 k3 ...

谁能解释为什么第二句话是有意义的？

Answer 1

“然后，我再次插入k3”<-这就是你错的地方。在处理第二次尝试插入k3时，您仍然必须搜索墓碑，直到找到未使用的存储桶，如果您没有看到k3，您将返回并覆盖该墓碑，而不是将其附加到未使用存储桶位置的冲突集群。

这与“在插入过程中遇到墓碑时，该槽可用于存储新记录”有关。-这不是在逐个存储桶迭代期间应用的简单if-then规则；只有在更广泛的意义上，“插入期间”指的是搜索过去的墓碑和现有的但不同的元素，直到找到一个未使用的存储桶，如果确实到达了一个未使用的存储桶，但已经看到了墓碑，那么只有到那时才能返回并覆盖墓碑。