Pseudocode for removal from hash table

I need to have a pseudocode description for performing a removal from a hash table using linear probing to resolve collisions. Not using a special marker to represent deleted elements.
SusanFDAsked:
Who is Participating?
 
Infinity08Commented:
Take a look at these :

        linear probing : http://en.wikipedia.org/wiki/Linear_probing
        probing hash table : http://en.wikipedia.org/wiki/Open_addressing
0
 
oleberCommented:
If you need deletion, it isn't a good idea using linear probing. I would use for each key a list of values, in this way you have simple removal, since is just removing from the list.

If you insist in linear probing, you have a big problem in complexity removing elements from the clusters.
0
 
JimFiveCommented:
Hash the value
Find in hashtable
Remove value
Probe forward as if a collision occurred
If found value would hash to previous slot then move it
Repeat until table value doesn't get moved.

--
JimFive
0
Get expert help—faster!

Need expert help—fast? Use the Help Bell for personalized assistance getting answers to your important questions.

 
oleberCommented:
JimFive: isn't so ease.

If you have hash to a and to b like

a1 b1 a2 b2

After deleting a1 you would get

a2 b1 _ b2

Now try to remove b2, and since exists an empty slot between b1 and b2, you will never find b2.

This algoritm is just good for adding, removing is bad.

the only ease way that I see, is to maintain a pointer to the next element with the some hash value. Moving the second element to the first position, when deleting the first and updating the pointers for the remaining.
0
 
JimFiveCommented:
@oleber
If you notice, my algorithm requires probing forward on the delete and moving the previously collided values back up the change.
0
 
oleberCommented:
so you are moving all the value, A's and B's ...

Positions
a  b  c  d


Original

a1 b1 a2 b2 d1 a3 d2

remove a2

a1 b1 b2 d1 a3 d2

remove b1 Note the a3 d1

a1 b2 a3 d1 d2

It it is this that you are saying, you are correct. Now be very careful implementing this.
0
 
JimFiveCommented:
@oleber

I didn't say it was easy, I said that's how you would do it.  And you are somewhat correct:  My last step should be repeat until you find an empty slot.
0
 
oleberCommented:
In reality, I don't like the 'linear probing' because of the deletion problem, the clustering and all the remaining problems.



0
 
JimFiveCommented:
I much prefer the list method of collision handling as well.

I should note to the Author, the worst case delete in this scenario ends up moving every element in your hash table.

--
JimFive
0
 
roussoscCommented:
Have you considered using an overflow table or linked lists to handle collisions rather than linear probing?

Also, using a second hash table with double hashing can usually keep the overflow table small.
0
 
Computer101Commented:
Forced accept.

Computer101
EE Admin
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.