Classical data structures that can outperform learned indexes (2018)
Why do cuckoo hashing advertisements always sound like snake oil sales pitches?<p>Claim: "A simple and beautiful technique that can achieve 99% occupancy and serve all lookups with just two memory accesses thanks to the power of two choices."<p>Great, so apparently I can achieve 99% occupancy?<p>Reality [1]: "Insertions succeed in expected constant time [...] as long as the number of keys is kept <i>below half</i> of the capacity of the hash table, i.e., <i>the load factor is below 50%</i>."<p>Ok so never mind...<p>[1] <a href="https://en.wikipedia.org/wiki/Cuckoo_hashing#Theory" rel="nofollow">https://en.wikipedia.org/wiki/Cuckoo_hashing#Theory</a>