Contamination
In the previous lesson, we learned about the use of tombstone when hash table is implemented with open addressing collision resolution. The use of tombstone prevents search to terminate prematurely, and it can be reused by the insert operation.
Is it safe for insert to write over tombstone?
You cannot simply replace a tombstone with a new item because it is necessary to follow the probe sequence to ensure that the new item is not already present in the table.
So, you either must never write over tombstones, or perform search prior to insertion to verify that a duplicate is not in the table. Only then the new item can safely be inserted into the slot of the first tombstone encountered through the probe sequence.
Tombstones waste space and reduce search efficiency.
In the worst-case, if the table is (almost) full with tombstones as most of the items were deleted, you will have $O(n)$ performance when searching although there are truly only a few items remaining in the table. This phenomenon is called contamination, and the only way to recover from it is to rehash.