Best way to remove an entry from a hash table

Question

What is the best way to remove an entry from a hashtable that uses linear probing? One way to do this would be to use a flag to indicate deleted elements? Are there any ways better than this?

Answer 1

An easy technique is to:

1. Find and remove the desired element
2. Go to the next bucket
3. If the bucket is empty, quit
4. If the bucket is full, delete the element in that bucket and re-add it to the hash table using the normal means. The item must be removed before re-adding, because it is likely that the item could be added back into its original spot.
5. Repeat step 2.

This technique keeps your table tidy at the expense of slightly slower deletions.