When should I rewrite the entire hash table?

Question

How can I decide when to rewrite the entire hash table?

Answer 1

It depends on how you solve the clash. If user-supplied linear sensing, performance usually begins to plummet with a load factor well above 60% or so. If you use double hashing, a load factor of 80-85% is usually pretty reasonable. If you use a collision chain, performance usually remains reasonable with load factors of up to about 150% or more.

I sometimes even created a hash table with balanced trees to resolve conflicts. In this case, you can almost forget about re-hashing - performance does not start to deteriorate noticeably until the number of elements exceeds the size of the table, at least by a couple of orders of magnitude.

Answer 2

As a rule, you have a hash table containing N elements distributed in an array of M slots.

There is a percentage value (called "growthFactor") defined by the user when creating the hash table, which is used this way:

if (growthRatio < (N/M)) Rehash(); 

rehash means that your array of M slots needs to be resized to contain more elements (a prime larger than the current size (or 2x more) is ideal) and that your elements should be distributed in a new larger array.

This value should have a value from 0.6 to 0.8.

Answer 3

The rule of thumb is to resize the table after fully loading 3/4.