When you resize a Hashmap do you keep deleted items if you're doing linear probing

Question

I understand that you keep the items and just mark them as deleted when they are removed in a HashMap using linear probing. However, when you resize the HashMap do you also add the deleted Items?

Answer 1

If you're using that kind of linear probing in a resizable hash table, you should make a few changes to the usual resizing rules.

Remember that the objectives are:

1. Maintain expected amortized O(1) cost per operation
2. Never have less than a quarter (for example) of your table slots used
3. Never have more than half (for example) of your table slots used

So, when the table fills up (1/2 slots full in this example), you resize, and:

1. The size of the new table should be 4N, where N is the number of non-deleted items in the table.
2. Only copy over the non-deleted items. This will leave exactly 1/4 of your slots full.

A resize with N non-deleted items takes O(N) time, and after each resize it takes at least N operations to get to the next one, which provides the O(1) amortized expected time per operation that we need.

If your implementation requires a power-of-two or prime-numbered table size, then it's OK if you pick the closest one to 4N, or the next bigger one.