开放寻址、非惰性删除的哈希表（无墓碑）

Question

是否可以在开放寻址哈希表中进行非延迟删除（没有逻辑删除），并具有冲突解决方案而不是线性探测（但仍然是开放寻址）？

对于线性探测，有一个算法这里。我想知道，当我们进行二次探测/双重哈希时，是否有一种非延迟删除的算法？

Answer 1

任何非线性探测算法都没有这样的算法有任何价值。它适用于线性探测，因为探测序列是可逆的。如果探测序列是可逆的，则所有元素都遵循相同的探测序列（尽管根据初始哈希，它们将在序列中的不同位置开始）。因此，二次哈希不会阻止探测收敛，从而导致所用节点的聚集，从而表征线性探测。

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

Answer 2

wiki 页面上的算法令人困惑且不完整：这是一个更好的版本，带有优化测试，用于检查

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

Answer 3

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

Answer 4

我会继续搜索，直到到达最后一个占用的单元格，然后我会将它与我想要删除的值交换（如果我之前遇到过它）并清除最后一个单元格。我根本不知道为什么需要墓碑。