Does it make sense to resize an Hash Table down? And When?

Question

My Hash Table implementation has a function to resize the table when the load reaches about 70%. My Hash Table is implemented with separate chaining for collisions.

Does it make sense that I should resize the hash table down at any point or should I just leave it like it is? Otherwise, if I increase the size (by almost double, actually I follow this: Link) when the load is 70%, should I resize it down when the load gets 30% or below?

Answer 1

Hash tables don't have to have prime-number lengths if you have a good quality hash function (see here). You can make them powers of two, which substantially speeds up index computations.

Why is this relevant to the question? Because when you shrink a power-of-two hashtable, you can leave all entries in the bottom half where they are and simply append the linked list in slot i (from the upper half) onto the linked list in slot i - n/2.

Answer 2

If memory is cheap, leave it alone. If memory is expensive, resize with hysterisis as you have suggested. When done, profile the result to make sure it performs well and haven't done something silly.