哈希表:为什么在开放寻址方案中删除很困难

Question

我试图理解开放寻址方法.我参考TH Cormen关于这个主题的书,其中指出在开放式寻址中删除是很困难的.我完全陷入这一段:

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

我不明白这一点.请用一些例子解释一下.

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.

Answer 2

在开放寻址方案中,查找调用一系列探测,直到找到密钥或找到空槽.

如果一个钥匙涉及几个探头的链条,它将丢失(找不到),如果沿着链条的某个地方,其他一个钥匙被移除,留下一个需要踏脚石的空槽.

通常的解决方案是通过将其插槽标记为可用于重用但实际上不为空来删除密钥.换句话说,添加替换垫脚石使得探针链到其他键不会被切断.

希望这有助于您的理解.

Answer 3

从线性探测开放寻址哈希表中删除很简单.维基百科哈希表页面上有伪代码多年.我不知道为什么不再存在,但这里有一个永久链接,它是:旧的维基百科哈希表页面,这里为了您的方便是伪代码:

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

在该页面上还有一些真实代码的参考.我相信这与插入具有完全相同的性能特征.

这种删除方法比使用频繁的'删除标记并偶尔重新删除所有内容'更好,因为上述方法是恒定时间而不是分摊的常量时间.如果您有一个包含一百万个项目的哈希表,您要添加和删除,在"删除标记"方法中,偶尔添加或删除的时间比其之前和之后的时间长一百万倍 - 这不是一个良好的性能特点.