I have no clue how this expression gets derived.
Say I'm given a hash table. Now I decided to double the hash table and rehash everything. How does the total number of hashes for a table with m+1 elements become
1 + 2*m/2 + 3*m/4 + 4*m/8 + 5*m/16 + 6*m/32 +....
Okay, I'm glad that I actually sat down and thought about it at work since on one seems to know.
Okay, I have a hash table with one 1 element and is size one. I add another element, but double the size of the hash. This becomes a hash with 2 elements and a size of 2. Now I ad one more element and double the hash again, this becomes a hash with 3 elements and size of 4. Each time I double the hash key, I add to the previous element. I'm assuming the reason why that we multiply by a factor of m each time we add an element is because the average linked list length on a hash key is tends to be 2 to 3.
Ie for 2 elements, there could be 4 to 6 entries, for 3 elements 6 to 8.
So with that, the expression becomes
1 + 2*m/2 + 3*m/4 + 4*m/8 + 5*m/16 + 6*m/32 +....
or 3m+1. Ie, the hash increases in linear time everytime the hash gets doubled.
Okay, so I guess Mr. Theo de raadt from the OpenBSD project was correct in his assertion that having an algorithm that doubles the hash table (vs geometric increases) is generally a bad idea.
