If a hash table is using open addressing as the collision resolution strategy, then during deletion, we mark that slot as dummy.
I understand the reason behind that is because while probing, a dummy would indicate there are still used slots further down the chain to search for.
But my question is that is there any way to implement open addressing without need for a dummy, and without degrading the algorithmic complexity of the hash table operations?
I came up with and algorithm of moving the last non-Null element of the probe sequence to the place of the deleted element to make the probe sequence contiguous. But this would make it impossible to retrieve the moved element if its hash index value was greater than that of the removed element.
So is there any correct algorithm for this?
EDIT
There is a small article on Wikipedia regarding this. I'll copy the relevant text (the whole article) here:
In computer science, lazy deletion refers to a method of deleting elements from a hash table that uses open addressing. In this method, deletions are done by marking an element as deleted, rather than erasing it entirely. Deleted locations are treated as empty when inserting and as occupied during a search.
The problem with this scheme is that as the number of delete/insert operations increases, the cost of a successful search increases. To improve this, when an element is searched and found in the table, the element is relocated to the first location marked for deletion that was probed during the search. Instead of finding an element to relocate when the deletion occurs, the relocation occurs lazily during the next search.
But I dont get it. If we move another element to the deleted place, it will again leave a hole in its probe sequence. How is it logically correct?
PS: This is another question somewhat related to the first one, so I dont know if I should make it a separate question or not.
