Hi,
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: http://planetmath.org/encyclopedia/GoodHashTablePrimes.html) when the load is 70%, should I resize it down when the load gets 30% or below?
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.
Are you writing the hash table for general purpose use, or is there a specific purpose for it? I suggest not resizing smaller for a general implementation. This will keep your table simple and keep it from memory thrashing under conditions where the table is filled and emptied often. If you end up running into a condition where the hash table needs to be reduced in size, extend it at that point in time.
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.