有人能给我看一个联合链式哈希表的删除算法示例吗?
我的插入算法是这样的:
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(要删除)的父节点。既然我们知道联合散列是线性探测和链接的组合。因此,我们可以简单地在数据和P的下一部分中放入NULL,并将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;
我们完了。现在,线性探测(在碰撞的情况下)将跟随每个碰撞节点中的下一个指针,而不是立即跟随下一个自由位置将其合并为链。