Earlier quoted context omitted.
> Ok so never mind... Keep reading, specifically the Variations section. 50% occupancy is for constructions with a per-bucket capacity of 1. At a capacity of 2, occupancy improves to a little under 90%, and at 4 to just under 98%. The linked write-up uses 8, which does in fact achieve very high occupancy. They could've done better, though. By using windows instead of buckets (i.e. allowing the buckets to overlap), a…
Thanks, that explains what they're saying now. But I'm still skeptical. How achievable is 98% fill for 4-element buckets in the first place? Intuitively I feel like you'd frequently have to scrap the table and rehash or enlarge it... is that not the case?
There are other options for the insertion algorithm than the standard random walk, too. E.g. take a look at page 18 of "Load Thresholds for Cuckoo Hashing with Overlapping Blocks" [1] for empirical data on 2-3 hash functions for 2-3 size windows. They don't show 4- or 8-size windows, but you get the gist.
Like nullc says below, it's trivial to tune things for your requirements. Want fast insertions? Overprovision. Want more predictable insertions? Use a smarter insertion algorithm. Want small tables? Use more hash functions and/or larger buckets. Want fast queries? Keep the hash count and bucket sizes small.
Rehashing isn't really a concern beyond the case of 2 hash functions and non-overlapping buckets of size 1.