合併散列刪除算法

Question

有人可以給我看一個合併鏈式散列表的刪除算法的例子嗎？

我插入算法是這樣的：

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。散列函數返回鍵％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| 

其中-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 

我不認爲這是在做正確的方式，但它似乎是工作。無論如何，我希望將來能夠幫助別人。

Answer 1

我們可以做的一件事是簡化刪除操作，如下所示： 假設PP是節點P的父節點（將被刪除）。因爲我們知道合併散列是 線性探測和鏈接的組合。所以不是在P向上後吸取所有鏈元素，我們可以簡單地將NULL放入數據和P的下一部分，然後將下一個[PP]放到下一個[p] 。當哈希函數映射的一些關鍵到這個位置它可以簡單地把它放在there.The算法因此，下一次是這樣的： 刪除：

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

而且我們正在這樣做。現在，線性探測（在發生碰撞的情況下）將跟隨每個碰撞節點中的下一個指針，而不是緊接着的下一個自由位置以將其合併成鏈。