具有开放寻址、非惰性删除(无逻辑删除)的哈希表

Question

在具有冲突解决而不是线性探测(但仍然是开放寻址)的开放寻址哈希表中，有可能有非惰性删除(没有逻辑删除)吗？

对于线性探测，有一种算法here。我想知道，当我们有二次探测/双重散列时，是否有一个非惰性删除的算法？

Answer 1

对于任何具有任何值的非线性探测算法，都没有这样的算法。它适用于线性探测，因为探测序列是可逆的。如果探测序列是可逆的，那么所有元素都遵循相同的探测序列(尽管根据初始哈希，它们将在序列中的不同位置开始)。因此，次要散列不会阻止探测收敛，从而导致以线性探测为特征的已用节点的群集。

换句话说，任何允许通过沿探测序列向后移动未删除的元素来删除的探测算法将具有与线性探测相同的对负载因子的敏感性，而不具有由线性探测提供的参考局部性的优势。

Answer 2

通过纯删除进行删除的问题是，空插槽可能会导致以后的搜索在找到表中真正存在的项之前终止。如果您维护一个计数器，给出任何插入之前的最大探测次数，并仅在此数目的探测之后终止每个失败的搜索，那么您可以通过简单地从其插槽中删除项来删除-但当然，失败的搜索将更加昂贵。

Answer 3

维基页面上的算法令人困惑且不完整:这里有一个更好的版本，带有优化的测试，用于检查k是否在范围[i, j)之外，考虑到j可能被包围：

function remove(key): boolean
    i := find_slot(key)
    if not slot[i].used
        return false // key is not in the table
    j := i
    loop
        j := (j + 1) modulo num_slots
        if not slot[j].used or j = i // if table was 100% full
            breakloop
        k := hash(slot[j].key) modulo num_slots
        if (j < i) xor (k <= i) xor (k > j)
            slot[i] := slot[j]
            i := j
    endloop
    slot[i].used := false
    num_slots := num_slots - 1
    return true