In case of Open Addressing, when a key is deleted, a tombstone marker(delete marker) is inserted at its place.
So if the hash table contains a lot of markers then it degrades the performance to a great extent and it needs to get emptied and we have to rehash everything again.
As load factor determines the performance of hash table when we do any operation (insertion, deletion, searching etc), so when the hash table contains a lot of tombstone markers, will it increases the load factor ?
Because If a search encounters a tombstone, it should continue going until it finds an empty slot containing NIL or key itself or if it gets back to the 1st slot after a sequence of probes. So while searching tombstones are considered as keys only.
When inserting, however, to avoid duplicate values in the table, a search must still traverse the entire cluster before reusing the tombstoned slot. So insertion also takes tome stones into consideration (provided that we have to check for duplicate keys before insertion. )
So my DOUBT is -
When the hash table contains a lot of tombstone markers, will it increases the load factor?