有人可以告诉我一个合并的链式哈希表删除算法的示例吗?
我的插入算法是这样的:
Insert (key)
int p = hash(key)
if d[p] = NIL then
d[p] = key
next[p] = NIL
else
while next[p] != NIL
p = next[p]
endwhile
td[firstEmpty] = key
next[p] = firstEmpty
next[firstEmpty] = NIL
endif
UpdateFirstEmpty(); //sets firstEmpty to first empty slot with lowest index
endInsert
假设表中的插槽数为13。哈希函数返回Key%13
。
Keys | 5 | 18 | 16 | 15 | 13 | 31 | 26 |
Hash(key)| 5 | 5 | 3 | 2 | 0 | 5 | 0 |
按此顺序插入它们后,我的表将如下所示:
index| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| 11| 12|
d| 18| 13| 15| 16| 31| 5| 26| -1| -1| -1| -1| -1| -1|
next| 1| 4| -1| -1| 6| 0| -1| -1| -1| -1| -1| -1| -1|
where -1 = NIL
[如果有人可以向我解释在拔出钥匙时不打断锁链时我应该做的事情,即使用言语表达,我也将非常感激。
谢谢
EDIT-:我想我终于明白了。我使用的是从打开的已寻址哈希表中删除项目时使用的相同技术。
这是怎么回事:
Search for key position and it's predecessor pp
if key is found at position p
if pp != NIL then
next[pp] = NIL
d[p] = NIL //deletes the key
p = next[p] //move position to next value in the chain
UpdateFirstEmpty()
while d[p] != NIL do
temp = d[p] //save value
d[p] = NIL //delete value
p = next[p] //move position to next value in chain
UpdateFirstEmpty()
Insert(temp) //insert the value in the list again
endwhile
endif
endalg
index| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| 11| 12|
d| 18| 13| 15| 16| 31| 5| 26| -1| -1| -1| -1| -1| -1|
next| 1| 4| -1| -1| 6| 0| -1| -1| -1| -1| -1| -1| -1|
firstFree: 7
delete 18
index| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| 11| 12|
d| 13| 31| 15| 16| 26| 5| -1| -1| -1| -1| -1| -1| -1|
next| 4| -1| -1| -1| -1| 1| -1| -1| -1| -1| -1| -1| -1|
firstFree: 6
delete 13
index| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| 11| 12|
d| 26| 31| 15| 16| -1| 5| -1| -1| -1| -1| -1| -1| -1|
next| -1| -1| -1| -1| -1| 1| -1| -1| -1| -1| -1| -1| -1|
firstFree: 4
delete 26
index| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| 11| 12|
d| -1| 31| 15| 16| -1| 5| -1| -1| -1| -1| -1| -1| -1|
next| -1| -1| -1| -1| -1| 1| -1| -1| -1| -1| -1| -1| -1|
firstFree: 0
我认为这样做不是正确的方法,但似乎可行。无论如何,我希望将来能对某人有所帮助。
我们可以简化删除的一件事是这样的:假设PP是节点P(将被删除)的父节点。因为我们知道合并哈希是因此,我们可以简单地将NULL放入数据和P的下一部分中,并将Next [PP]填充到Next [p]中,而不是将P向上吸附之后的所有链元素。所以下一次当哈希函数将某个键映射到该位置时,只需将其放在该位置即可。算法如下所示:删除:
Next[PP]=Next[P]; //as simple as deletion in link list without deleting node here
D[P]=NULL;
Next[P]=NULL;
我们完成了。现在,线性探测(在发生碰撞的情况下)将跟随每个碰撞节点中的下一个指针,而不是紧随其后的自由位置以将其合并为链。