HNGlance

Top Best New Show

Cuckoo hashing improves SIMD hash tables (and other hash table tradeoffs)

https://reiner.org/cuckoo-hashing

by ibraheemdev • 10 months ago

79 1 10 months ago

RE

Related Stories

Loading related stories...

Comments

1

DeepSeaTortoise• 10 months ago

I experimented with Cuckoo tables a lot, but sadly never managed to beat quadratic probing. It's honestly quite depressing just how hard beating "having your data right next to each other" is.

The one thing Cuckoo tables can do much better than anything else I've tried is load factor. Insertions get slow well above 90%, but as long as your buckets are large enough or you got enough inner tables, it'll do fast lookups even at a perfect 100%.

But you'll have a hard time beating getting all the data you'll need for 99% of your lookups within a single cache line.

Source preview

reiner.org

HNGlance

© 2024-2026 HN Glance. Story content belongs to its original sources.

Privacy
Terms