algorithm - 哈希表 : Why deletion is difficult in open addressing scheme

Question

我正在尝试了解开放式寻址方法。我引用了 T. H. Cormen 关于这个主题的书，其中指出在公开寻址中删除是困难的。我完全停留在这一段:

Deletion from an open-address hash table is difficult. When we delete a key from slot i, we cannot simply mark that slot as empty by storing NIL in it. Doing so might make it impossible to retrieve any key k during whose insertion we had probed slot i and found it occupied.

我不明白这个。请举例说明。

Answer 1

假设 hash(x) = hash(y) = hash(z) = i。并假设首先插入 x，然后插入 y，然后插入 z。
在开放寻址中:table[i] = x, table[i+1] = y, table[i+2] = z.

现在，假设您要删除 x，并将其设置回 NULL。

稍后搜索z时，您会发现hash(z) = i和table[i] = NULL，并且您将返回错误答案:z 不在表中。

为了克服这个问题，你需要设置 table[i] 一个特殊的标记，指示搜索函数继续查看索引 i+1，因为可能有是其散列也是 i 的元素。