Combination Algorithm Destruction Algorithm

Question

Can someone show me an example of a delete algorithm for a combined chained hash table?

My insertion algorithm is as follows:

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 the key% 13.

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

After pasting them into this order, my table will 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 do when I remove the keys without breaking the chains, even if it were in words, I would really appreciate it.

thanks

EDIT: I think I finally understood. I use the same technique that I used when removing an item from an open address hash table.

Here's how to do it:

 Search for key position and it 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 

I don't think this is the right way to do this, but it seems to work. Anyway, I hope this helps someone in the future.

Answer 1

One thing we can do to simplify the deletion is something like this: suppose PP is the parent of node P (for deletion). Because we know that combined hashing is a combination of linear probing and chaining. Therefore, instead of sucking all the elements of the chain after P up, we can simply put NULL in the data and the next section of P and ppopulate Next [PP] to Next [p]. So the next time the hash function maps some key to this location, it can just put it there. The algorithms look like this: Removal:

 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 sensing (in the event of a collision) will follow the next pointer in each colliding node, rather than the next next free position, to chain it.