Coalesced Hashing Deletion Algorithm

Can someone show me an example of deletion algorithm for a coalesced chained hash table?

My insertion algorithm is like this:

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

Let's say the number of slots in the table is 13. The hash function returns Key%13.

    Keys | 5 | 18 | 16 | 15 | 13 | 31 | 26 |      
Hash(key)| 5 |  5 |  3 |  2 |  0 |  5 |  0 |

After inserting them in this order my table would look something like this:

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

If someone could explain to me what I should be trying to do when removing keys without breaking the chains even if it's in words I would really appreciate it.

Thanks

---

EDIT -: I think I finally got it.. I'm using the same technique I used when deleting an item from a open addressed hash table.

This is how it goes:

Search for key position and it's predecessor 开发者_Go百科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

I don't think this is the right way to be doing it, but it seems to be working. Anyway, I hope will help someone in the future.

---

One thing we can do to simplify the deletion is something like this: suppose PP is the parent of node P(to be deleted ). Since we know that coalesced hashing is combination of linear probing and chaining.So instead of sucking all the chain elements after P upwards ,we can simply put NULL in data and next section of P and ppopulate Next[PP] to Next[p]. So next time when hash function maps some key to this location it can simply put it in there.The algorithms looks like this: Deletion:

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

And we are done. Now linear probing (in case of collision) will follow the next pointer in each colliding node , and not the immediately next free position to coalesce it into chain.