散列表：为什么在开放地址法中删除操作很困难

Question

我正在尝试理解开放寻址法。我参考了 T.H. Cormen 的相关书籍，其中指出在开放寻址中删除操作很难。我完全无法理解以下段落：

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

请用一些例子来解释这一点。

- Nishant Kumar

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的元素。

- amit

---

Amit: 你能解释一下吗：常用的三种技术用于计算开放定址法所需的探测序列，它们分别是线性探测、二次探测和双哈希。这些技术都保证对于每个关键字 k，h(k, 1), h(k, 2), ., h(k, m) 是 0, 1, . . . , m - 1 的一个排列。然而，这些技术都无法满足均匀散列的假设，因为它们无法生成超过 m2 种不同的探测序列（而均匀散列需要 m! 种）。 - Nishant Kumar

@Amit 如果你假设 hash(x) = hash(y) = hash(z) = i，那么如何用开放寻址法表示它呢？在这种情况下，你需要维护一个记录的链表（或其他类型的链接）对吧？ - Geek

@amit 另外我在这里有一个相关的问题(http://stackoverflow.com/questions/12005405/are-open-addressing-in-hash-tables-only-useful-for-searching-how-do-the-elemen)，你能试着回答一下吗？ - Geek

@Geek：在“开放地址法”中，假设hash（x）=hash（y）= i，并且假设x是首先插入到索引i中的。那么，当您插入y时 - 您将其插入到不同的条目中。最简单的方法（虽然不是最好的方法）是：insert(y,position)=if (position is occupied) insert(y,position+1); else table[position]=y - amit

在协同散列中，设置值为 null 并保持“next”指针指向下一个索引并不难。在协调方法中，它类似于开放地址方法，但有“next”属性，用于指示表格中的下一个位置。 - M.kazem Akhgary

Answer 2

从线性探测开放地址哈希表中删除元素很简单。维基百科哈希表页面多年来一直有相关的伪代码。我不知道为什么现在没有了，但是这里有一个链接可以回到当时的版本：旧版维基百科哈希表页面，为了方便起见，以下是该伪代码：

function remove(key)
 i := find_slot(key)
 if slot[i] is unoccupied
     return   // key is not in the table
 j := i
 loop
     j := (j+1) modulo num_slots
     if slot[j] is unoccupied
         exit loop
     k := hash(slot[j].key) modulo num_slots
     if (j > i and (k <= i or k > j)) or
        (j < i and (k <= i and k > j)) (note 2)
         slot[i] := slot[j]
         i := j
 mark slot[i] as unoccupied

该页面还有一个对一些真实代码的引用。我认为这与插入具有完全相同的性能特征。

这种删除方法比常用的“标记删除并偶尔重新哈希”更好，因为上面的方法是恒定时间而不是平摊恒定时间。如果您拥有一个包含一百万个项的哈希表，并且要进行添加和删除操作，在“标记删除”方法中，偶尔的添加或删除将比之前和之后的操作慢上一百万倍——这不是一个良好的性能特征。

- hoopsnake

---

请纠正我，但是难道不是更简单的方法就是获取键的哈希值，然后比较键和slot[j]的哈希值是否相等吗？我的做法是找到最后一个占用的与key相同的哈希槽（从j = i + 1开始），然后将其移动到第i个槽中。您只需要进行一次移动操作，并且最多计算num_collisions次哈希 - 这个复杂度与contains(key)和insert(key)操作相同。 - recodeFuture

当所有插槽都被使用或标记时，搜索一个不存在的元素将永远持续下去，或者至少在最终得出它不存在之前遍历整个表。如果程序运行足够长的时间，这种情况必须发生。 - Meow Cat 2012

我不认为它会永远持续下去。首先找到下一个空槽，然后向后搜索可能散列到i的条目。如果找到（槽j），则将其放入第i个槽中。然后您重复此过程以获取槽j，直到找不到匹配项为止。当然，最坏情况下您需要扫描所有内容，但假设负载因子足够低，则应在O（1）时间内执行此操作。 - john16384

Answer 3

在开放寻址方案中，查找会触发一系列的探测，直到找到键或者找到一个空槽位为止。

如果一个键涉及到多个探测的链条，那么当其中的另一个键被移除，留下了一个需要步进的空槽位时，其将会丢失（无法被查找到）。

通常的解决方法是通过将其标记为空闲可重用但实际上并不为空来删除一个键。换言之，添加一个替代的步进石，以便于不会缩短到其他键的探测链。

希望这可以帮助你理解。

- Raymond Hettinger

---

奖励分数为提到已删除的插槽仍可供重用。 - Bram