4 ms·

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

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

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