0
$\begingroup$

With regards to hash tables using open addressing as collision resolution mechanism,

Introduction to Algorithms, Chapter 11, page 294 (4th edition, 2022 printing) states the following

Deletion from an open-address hash table is tricky. When you delete a key from slot q, it would be a mistake to mark that slot as empty by simply storing NIL in it. If you did, you might be unable to retrieve any key k for which slot q was probed and found occupied when k was inserted. One way to solve this problem is by marking the slot, storing in it the special value DELETED instead of NIL. The HASH-INSERT procedure then has to treat such a slot as empty so that it can insert a new key there. The HASH-SEARCH procedure passes over DELETED values while searching, since slots containing DELETED were filled when the key being searched for was inserted. Using the special value DELETED, however, means that search times no longer depend on the load factor $\alpha$, and for this reason chaining is frequently selected as a collision resolution technique when keys must be deleted.

What does special value DELETED got to do with search times no longer being dependent on load factor?

Would search times be dependent on load factor if we didn't use DELETED flag? Sure, without DELETED flag our search doesn't work as it could terminate prematurely. But what does DELETED have specifically to do with search times?

$\endgroup$
1
  • $\begingroup$ Consider this statement: Using the special value DELETED, however, means that search times no longer depend on the load factor $\alpha$, but rather on the sequence of the elements entered and deleted. Does this help? $\endgroup$
    – codeR
    Commented Apr 26 at 10:27

2 Answers 2

1
$\begingroup$

If you have a table with space for 20,000 entries, and you store 19,990 keys then the load factor gets high. You’d expect it to go lower if you remove 15,000 keys, but because of your “deleted” markers this doesn’t happen.

Now an implementation MUST reallocate the table with a bigger size if you try to add more entries than available space. It WILL reallocate earlier when the load factor gets too high. And obviously it MAY reallocate if the number of elements becomes small while the load factor is unchanged, to save space and remove the load factor, because you won’t have “deleted” markers in the copied table.

But anyway, an implementation can skip over ten “deleted” markers very quickly. When it runs into a used entry, that costs time. So say you had to visit 10 slots to find your key X, that is nine unsuccessful and one successful comparisons. If eight of these entries are “deleted”, there are eight entries that are skipped very quickly, one failed comparison, and one successful, so much less bad. (Some implementations store the hash value in the table, so skipping keys with the wrong hash value is also very fast. You'd have to measure if it is worth it).

$\endgroup$
0
$\begingroup$

It's because the load factor is defined by the number of "active" elements, but the "real load factor" on which the performance depends, is defined by the number of "active" elements plus number of DELETED marks.

If you inserted just one item and then deleted it, you will have a load factor of 0, but the "real load factor" > 0.

So, it's just matter of definitions.

Also, it's possible that with DELETED elements, an average sequence length will be larger than in an average hash table having the same "real load factor", but having no DELETED elements, but my Math is too weak to analyze that.

Anyway, I think that the author means what I said in the first part.

$\endgroup$
1
  • $\begingroup$ this is also valid observation. $\endgroup$
    – jam
    Commented Apr 30 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.