散列表：为什么在开放寻址方案中删除困难 [英] Hash Table: Why deletion is difficult in open addressing scheme

问题描述

我试图理解开放寻址方法。我参考T.H.科尔曼关于这个主题的书，其中指出在公开寻址中删除是困难的。我完全停留在这一段：

I am trying to understand the open addressing method. I refer to T. H. Cormen's book on this topic, which states that deletion is difficult in open addressing. I am completely stuck at this paragraph:

从开放地址哈希表中删除很困难。当我们从插槽 i 中删除​​一个密钥时，我们不能简单地通过在其中存储 NIL 来将该插槽标记为空。这样做可能会导致在我们探测插槽 i 的过程中检索到任何密钥 k 并发现它已被占用。

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.

我不明白这点。请解释一些例子。

I don't understand this. Please explain it with some examples.

推荐答案

假设 hash（x）= hash（y）= hash （z）= i 。假设首先插入 x ，然后 y ，然后 z 。

在开放寻址中： table [i] = x ， table [i + 1] = y ， table [i + 2] = z 。

Assume hash(x) = hash(y) = hash(z) = i. And assume x was inserted first, then y and then z.
In open addressing: table[i] = x, table[i+1] = y, table[i+2] = z.

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

Now, assume you want to delete x, and set it back to NULL.

将搜索 z ，您会发现 hash（z）= i 和表[ i] = NULL ，您将返回错误答案： z 不在表格中。

When later you will search for z, you will find that hash(z) = i and table[i] = NULL, and you will return a wrong answer: z is not in the table.

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

To overcome this, you need to set table[i] with a special marker indicating to the search function to keep looking at index i+1, because there might be element there which its hash is also i.

这篇关于散列表：为什么在开放寻址方案中删除困难的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！