11.5 Deleting entries from open addressing hash tables

In a separate chaining hash table, deletion is simple. Just perform a lookup, and delete an entry from a linked list. For open addressing, things are more complicated.

Recall that the invariant of a linear probing hash table is that there are no null values between the ideal position of a key (h(\mathit{key})\bmod N)) and its actual position. Introducing a null value in the middle of a cluster might cause lookups to fail for the keys in the remainder of the cluster.

Look at the table in Figure 11.3. Depending on what the hash value of E is, replacing D with a blank cell might cause a lookup of E to fail, since lookups terminate when reaching an empty cell. Moving E to cell 4 would solve the problem if h(E)\bmod 13 = 4, but break the hash table if h(E)\bmod 13 = 5. We will look at two ways of handling deletion in open addressing:

• Re-hashing the rest of the cluster. If we are removing A in Figure 11.3, we would delete and re-add B and C to the hash table to ensure the invariant holds.
• Lazy deletion.

Lazy deletion means replacing the deleted value with a special token, sometimes called a tombstone, that indicates a value was deleted. Tombstones are not considered empty when performing lookups, so lookups succeed without any modifications.

When inserting a new value, the tombstones can either be ignored or replaced. Replacing the tombstone requires some care. Consider what happens in Figure 11.3 if B is replaced by a tombstone, and then we try to add C. Because C is already in the set, the operation should do nothing. This means that even if we decide to replace the tombstone, we need to search the whole cluster first.

You may be concerned about the tombstones cluttering up the hash table, and wonder how we get rid of them. The key is that during resizing, the tombstones are never copied to the new table.

Lazy deletion is simple in theory, but there are a plenty of technicalities to it, such as how to represent the tombstones. In most programming languages you would use null values to represent an empty table cell, but then we need a distinct non-value to represent a tombstone.