What is a good growth strategy for hash tables? If the number of elements exceeds the number of buckets, I increase the number of buckets with the following formula:n = int(n * 1.618033988749895) | 1;Does that sound sensible? (The | 1 part makes sure I get an odd number.)
Hashing growth strategy
data structures;hashing
I'd keep the growth ratio somewhat less than the golden mean. Doing that means that (assuming they were contiguous) at some point, the chunks you discarded would be enough to make up the next chunk you need. In fact, for simplicity (not to mention avoiding FP math) I'd probably just use n + n/2 | 1.The next question is when you need to do the growth. This varies widely depending on how you resolve collisions. If you use linear probing, you probably want to resize when the table is somewhere around 70-80% full (at most). Toward the opposite extreme, if you use chaining, you can typically wait until the table is overfilled by a factor of around 3 or 4.One of my favorites is to use a table of balanced trees. In this case, I've yet to see a situation where resizing made much sense at all -- as you overfill the table, it slowly degrades from O(1) to O(lg N), but you'd have to be quite a few orders of magnitude off on the table size before it was worth considering resizing.