合并哈希删除算法

| 有人可以告诉我一个合并链式哈希表删除算法的示例吗？ 我的插入算法是这样的： 
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
 如果有人可以向我解释在拔出钥匙而又不打断锁链的情况下我应该怎么做，即使用言语表达，我也将不胜感激。 谢谢 编辑-：我想我终于明白了。我正在使用从打开的寻址哈希表删除项目时使用的相同技术。 它是这样的： 
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
我认为这不是正确的做法，但似乎可行。无论如何，我希望将来能对某人有所帮助。     
2020-02-02 2 条评论
分享

没有找到相关结果

    已邀请:

    搜洼挂时

            我们可以简化删除的一件事是这样的：  假设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;
    我们完成了。现在，线性探测（在发生碰撞的情况下）将跟随每个碰撞节点中的下一个指针，而不是紧随其后的自由位置以将其合并为链。     
    2020-02-02 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.033583879470825