Cuckoo Hashing Improves Simd Hash Tables (and Other Hash Table Tradeoffs)

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.