4 ms·

> 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

> 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 capacity of 2 already yields > 96% occupancy, and 4 reaches 99.9%, so smaller and faster (lookups examine fewer keys on average). This approach is detailed in "3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit".

dataflow 5y ago
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?
- phkahler 5y ago
  Seems like a good point. If you're at 90+ percent occupancy you're going to run into trouble adding more data.
- jasonwatkinspdx 5y ago
  So, for the complete formal answer get Mitzenmacher's book: https://www.amazon.com/Probability-Computing-Randomized-Algorithms-Probabilistic/dp/0521835402 https://www.amazon.com/Probability-Computing-Randomized-Algo... There are incrementally resizing versions, generally under the name Levelized Hashing. The most state of the art versions of these are lock free. (example: https://www.usenix.org/conference/atc20/presentation/chen https://www.usenix.org/conference/atc20/presentation/chen)
- FreakLegion 5y ago
  Like with Bloom filters (which also draw their power from hashing items into multiple buckets), the statistical guarantees are quite strong, and things work well in practice. 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. 1. https://arxiv.org/pdf/1707.06855.pdf https://arxiv.org/pdf/1707.06855.pdf

dataflow 5y ago

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?

phkahler 5y ago
Seems like a good point. If you're at 90+ percent occupancy you're going to run into trouble adding more data.
jasonwatkinspdx 5y ago
So, for the complete formal answer get Mitzenmacher's book: https://www.amazon.com/Probability-Computing-Randomized-Algorithms-Probabilistic/dp/0521835402 https://www.amazon.com/Probability-Computing-Randomized-Algo... There are incrementally resizing versions, generally under the name Levelized Hashing. The most state of the art versions of these are lock free. (example: https://www.usenix.org/conference/atc20/presentation/chen https://www.usenix.org/conference/atc20/presentation/chen)
FreakLegion 5y ago
Like with Bloom filters (which also draw their power from hashing items into multiple buckets), the statistical guarantees are quite strong, and things work well in practice. 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. 1. https://arxiv.org/pdf/1707.06855.pdf https://arxiv.org/pdf/1707.06855.pdf