Question

PYTHON--- regarding a hash table, why would it be bad to delete an item to successive searches or insertions that uses open addressing

Answer 1

Open addressing is one of the collision resolution method. In open addressing, all the keys are stored within the table itself. Whenever a collision occurs, the next location will be probed using several methods like linear probing, quadratic probing etc.

So the main problem in open addressing is that when the location from the hash function is "k" the actual value may not be present in the exact location "k". It may be moved to other locations based on probe technique used.

Consider a hash of 3 nodes of which first 2 are already occupied. Now assume new key also hashed to slot 1, and due to some resolution technique it is placed in slot 3.

Now if we want to delete slot 2 and we directly delete it, a huge problem will occur. Assume we deleted slot 2 directly. So later when the search for slot 3 is asked, it will point to slot1 (as assumed above). As the value in slot 1 is not the required value, the probe goes to slot2.

But as we deleted it, it will be empty and probe thinks that the value requested is not present in the hash table.

So when a key is deleted, we should explicitly mark it as deleted so that the search will go past the deleted node.

So in the above case when we mark slot 2 as deleted, the probe now goes to slot3 instead of stopping at slot 2, and finally gets the value in slot 3.

So in case of deletion we should be extra careful than consecutive searches and insertions in case of open addressing.