Hash Deletion

In the past few lessons, we covered how to insert new items into separate chaining and open addressing hash tables. Let's also now take a look at how to delete an item from a hash table.

Separate chaining

Deleting a key x is relatively simple in a separate chaining hash table. The algorithm is:

Compute h(x) to find the bucket where x belongs.
Use the linked list deletion algorithm to delete the node with key x.

Deletion in an open addressing hash table is a little bit more challenging, since it can leave gaps in the table that interfere with the probing process. Watch the following video to see why deletion can create gaps, and how to fix it:

To summarize:

When deleting an item, assign a special "removed" value to that slot in the table.
- For example, "empty" spaces may contain -1 and "removed" spaces may contain -2 as sentinel values
When performing lookups, we need to skip past any removed slots and continue searching
When performing insertions, we can insert into either empty or removed slots (whichever comes first), after checking to make sure the key to be inserted doesn't already exist

Check your understanding

Consider the following open addressing hash table with linear probing and removed spaces:

The hash function used is h(x) = index of first character of x, i.e., 'a' = 0, 'b' = 1, etc.

One of the keys has been incorrectly inserted. Which one?
Where would the key giraffe be inserted?

Click to reveal the answer.

Answer.

The key dog must have been incorrectly inserted. It starts with 'd', so it should have been hashed to 3. Even though another key occupies that space, with linear probing it should have been placed in index 4.
h(giraffe) = 6, so we first check there. It's a removed cell, so we need to keep looking through the hash table to confirm giraffe isn't already present. We wrap around to the beginning of the table, and check indexes 0 (occupied), 1 (removed), 2 and 3 (both occupied), until we reach index 4, which is empty. At this point, we can be assured that giraffe is not in the table, and so we insert it into index 6, since that was the first removed position we encountered.

Course Name

Hash Deletion

Separate chaining

Open addressing