合并哈希删除算法

Question

合并哈希删除算法

6

有人能给我展示一下针对合并链接哈希表的删除算法例子吗？

我的插入算法如下：

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

我不认为这是正确的做法，但似乎它在起作用。无论如何，我希望它能帮助未来的某个人。

- Bogdan

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mohit · Answer 1

我们可以做一件简化删除操作的事情：假设PP是节点P（要删除）的父节点。由于我们知道合并哈希是线性探测和链接的组合。因此，我们可以将P后面的所有链元素向上提取，或者只需将数据和P的下一个部分放置为NULL，并将Next[PP]填充到Next[p]。下次哈希函数将某个键映射到该位置时，它可以直接将其放在那里。算法如下：删除：

Next[PP]=Next[P];  //as simple as deletion in link list without deleting node here
D[P]=NULL;
Next[P]=NULL;

我们完成了。现在，在发生冲突的情况下，线性探测将跟随每个冲突节点中的下一个指针，而不是立即下一个空闲位置，以将其合并成链。