edited by
571 views
0 votes
0 votes

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?

edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
2
Sanjay Sharma asked Jun 12, 2016
4,173 views
Which of the following is not collision Resolution TechniqueHash addressingChainingIndexingNone of these
0 votes
0 votes
1 answer
3
tishhaagrawal asked Dec 16, 2023
315 views
Below is my approach to solving this question, can anyone please explain if I am doing it the right way?Let X = #free slotssince, m =7 and n = 3So, $4 \leqslant x\leqsla...