是否可以在具有线性探测以外的冲突解决方案(但仍然是开放寻址(的开放寻址哈希表中进行非延迟删除(无逻辑删除(？
对于线性探测，这里有一个算法。我想知道，当我们进行二次探测/双重哈希时，是否有一种非延迟删除的算法？
对于任何具有任何值的非线性探测算法，都没有这样的算法。它适用于线性探测，因为探测序列是可逆的。如果探测序列是可逆的，那么所有元素都遵循相同的探测序列(尽管它们将根据初始哈希在序列的不同位置开始(。因此，二次哈希不会阻止探测收敛，从而导致所用节点的聚类，这是线性探测的特征。
换言之，通过沿着探测序列向后移动未删除的元素来允许删除的任何探测算法将具有与线性探测相同的对负载因子的灵敏度，而没有由线性探测提供的参考位置的优点。
纯删除的问题在于，空槽可能会导致以后的搜索在找到真正在表中的项之前终止。如果您维护一个计数器，给出在任何插入之前进行的最大探测数量，并仅在探测数量之后终止每次失败的搜索，那么您可以通过简单地从插槽中删除项目来删除，但失败的搜索当然会更贵。
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