Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 5 down vote favorite

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.)

share|improve this question
2  
You are going to start getting collisions before you get close to the bucket limit. You may want to increase the volume x% before you reach it. (Not a hash table expert). – Loki Astari Jan 27 '11 at 23:01
2  
Great question, and it belongs on SO! – Job Jan 27 '11 at 23:48

3 Answers

up vote 3 down vote accepted

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.

share|improve this answer
Don't you just end up with a performance penalty as you get to the point where a significant number of buckets have three or so entries? I can see the attraction of the graceful degradation, but does it actually come close in performance to chaining with linked lists (and resising slightly more aggressively)? – James Youngman Feb 23 '12 at 1:39
@JamesYoungman: Yes, in my experience it stays reasonably close in performance at least when I've used it. I suppose if your size was off by more than 4 or 5 orders of magnitude, resizing might start to win by a substantial margin, but you don't have to start with a very big table to keep it competitive under virtually any reasonable circumstance. – Jerry Coffin Feb 23 '12 at 5:16
up vote 1 down vote

A good growth strategy takes into account

  • the growth rate of your data.
  • how distributed your data actually is in the hash-table
  • the requirements of the hashing algorithm. For example, do you require the number of buckets to be a prime number?
share|improve this answer
up vote 0 down vote

The two obvious problems with that growth plan are possible memory fragmentation though this also depends on how the underlying array is implemented) and of course the fact that the expression overflows: the right hand side of the expression may involve an overflow. In C, this produced undefined behaviour. In other languages, this may produce a runtime exception or a new value of n that is smaller than the previous one.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.