Dynamic hash tables

Yes, but the thing is, it works. Statistically, the split bucket is likely to have a longer-than-average chain. And, on average, at *no* time does *any* bucket have a chain :-) So it's quite possible for me that a "split the largest bucket" would fail because it wouldn't find a "largest" bucket to split!

And in my use case (multiple items per allocation block) it doesn't seem to matter. If the average block is 80% full, I'll find the item I'm looking for in the first block I try 19 times out of 20. That's pretty good ...

It's all a tradeoff. I trade uneven clumping for a simple algorithm and a perfect modulo. I also trade multiple items per allocation block to reduce chains.

You're trading unrestricted access most of the time, and accepting that you have an imperfect modulo and every now and then you're going to get a bit of a hit as the table resizes.

I'm trading the cost of scanning a bucket, and the occasional stall as I hit a locked bucket, for the fact that most of the time I have no chains, and it's damn bad luck if a read hits a bucket that's splitting.

Both trades are appropriate for our use circumstances - a chain causes me an unwanted disk i/o stall, you're not worried about memory usage but need to prevent chains getting too long.

Cheers,
Wol