Dynamic hash tables

Wol, that breaks the "random but tending toward equally-sized" expectation for bucket content size.

When incrementing the number of buckets by 1, a "fair" bucket distribution policy would go from k buckets, each holding 1/k of the nodes (on average with a good hashing function), to k+1 buckets each with 1/(k+1).

Your policy would go from i-j buckets of 1/(log2(i)+1) nodes plus i+2j buckets of 1/(log2(i)+2) nodes, to i-j-1 of the bigger lists and i+2j+2 of the smaller lists. (where i is the largest power of 2 <- k, and j is k-i)

So, that means there are two groups of buckets, the first group containing buckets that are twice as full as the second group.

In general, adding one bucket, or removing one bucket, would only sometimes provide any benefit depending upon whether the bucket that was split, or the buckets that were merged, were actually bigger or smaller than 1/k. Sometimes, you'll add one bucket by splitting the smallest of the large buckets; or by merging the largest of the small buckets and get no significant benefit from the change. (At worst, it would be splitting (merging) an empty bucket (pair).) Other times, it'll happen that the bucket that is split or merged will be the best candidate and there will be great benefit.