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?

CodePudding user response：

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.

CodePudding user response：

There's a trick that makes resizing a HashMap easy -- don't resize it. Instead, have your resize() method do this:

1. Create a second HashMap, initialized with a larger internal array than the current one (twice is large is good)
2. Iterate over the contents of your current HashMap, inserting each key-value pair from your current HashMap into the newly created HashMap using your HashMap's regular put(key,value) method (or whatever you call it). (Since the internal array of your newly created HashMap is significantly larger than your current one, this is guaranteed to fit without requiring any further resizes)
3. Swap the contents of your current HashMap and the newer/larger HashMap (if you've allocated the contents of the HashMap as a separate heap object, this can be as easy as a single pointer-swap)
4. That's it; now your original HashMap is resized larger, and you didn't have to write any additional resizing-logic to do it, because you re-used the logic you had already implemented. The second HashMap (which now contains the older/smaller internal array) can now be discarded.