algorithm - 哈希删除算法

Question

我正在阅读这本书，算法介绍，第 3 版，在涉及哈希插入和搜索的部分中，提到了哈希删除算法，但没有实际的代码。它指出您不能从插槽 i 中删除密钥，因为这样可能无法检索密钥。因此，将 Key Deleted 的特殊值应用于插槽。然后，哈希插入算法会将插槽视为空，并将密钥插入其中。所以，我自己为哈希删除重写了哈希插入算法，我想知道我的哈希删除算法是否可以用来标记删除。T定义为哈希表，k定义为key。Hash Insert(T, k) （这是来自书）
i = 0
重复
j = h(k, i)
if T[j] == nil
T[j] = k
返回 j
else i = i + 1
直到 i == m
错误“哈希表溢出”

现在这是我的哈希删除算法
Hash Delete (T, k)
i = 0
repeat
if T[j] == NIL
i = i++
if i == m
error "hash table overflow"
return j
else if T[j] == k
k = "已删除"

这个伪代码是否适用于哈希删除？我应该将 else if 语句进一步向上移动，还是它在哪里可以？如果在数组中找不到值，我应该保持哈希表溢出吗？我的想法是，如果在数组中找不到特定的键，我应该这样做。

标签： algorithmhashpseudocode

Answer 1

您应该更新您的问题，指出这是关于open-addressing hashing scheme。在链式散列中不会出现此问题。

你不需要修改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将其视为一些随机的非目标值并通过。