哈希删除算法

Question

我正在看《算法导论》第 3 版这本书，在涉及哈希插入和搜索的部分中，提到了哈希删除算法，但没有实际代码。它声明您不能从插槽 i 中删除密钥，因为那样可能无法检索密钥。因此，Key Deleted 的特殊值将应用于插槽。然后，Hash Insert 算法会将槽视为空槽，并在其中插入密钥。因此，我亲自为哈希删除重写了哈希插入算法，我想知道我的哈希删除算法是否可以标记删除。 T 定义为散列table，k 定义为键。 Hash Insert(T, k) (这是书上的)
我 = 0
重复
j = h(k, i)
如果 T[j] == 无
T[j] = k
returnj
否则我 = 我 + 1
直到我 == m
错误“哈希 table 溢出”

现在这是我的哈希删除算法
哈希删除 (T, k)
我 = 0
重复
如果 T[j] == NIL
我=我++
如果我 == 米
错误“哈希 table 溢出”
returnj
否则如果 T[j] == k
k =“已删除”

此伪代码是否适用于散列删除？我应该将 else if 语句进一步向上移动，还是在它所在的位置没问题？如果在数组中找不到该值，我是否应该保持散列 table 溢出？我的思考过程是我应该以防在数组中找不到特定的键。

Answer 1

您应该更新您的问题，指出这是关于 open-addressing 散列方案 的。链式哈希不会出现此问题。

您不需要修改 HASH-SEARCH 算法。它只会传递 DELETED 就好像它是其他值一样。这是基于新约定的修改后的 HASH-DELETE 算法：

r <- HASH-SEARCH(key)

if r == NIL

    return NIL

else
    
    T[r] = DELETED
    
    return T[r]

基于以上，您可以修改HASH-INSERT如下：

i <- 0

repeat j <- h(k,i)

    if T[j] == NIL or T[j] == DELETED
         
        then T[j] <- k
           
            return j

        else i <- i + 1

until i == m

error "hash table overflow"

HASH-INSERT 会将 DELETED 视为空值并使用它，但 HASH-SEARCH 和 HASH-INSERT 只会将其视为一些随机 non-target 值并传递.

哈希删除算法

Hash Delete Algorithm

algorithm

hash

pseudocode