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?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
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.
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
OWASP Proactive Controls

Learn the most important control and control categories that every architect and developer should include in their projects.

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.
JimFiveCommented:
@oleber
If you notice, my algorithm requires probing forward on the delete and moving the previously collided values back up the change.
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.
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.
oleberCommented:
In reality, I don't like the 'linear probing' because of the deletion problem, the clustering and all the remaining problems.



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
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.
Computer101Commented:
Forced accept.

Computer101
EE Admin
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Algorithms

From novice to tech pro — start learning today.