Hash tables with O(1) worst-case lookup and space efficiency [pdf]

I've had some luck turning a cuckoo hash into a sort of LRU cache. Whenever you do an insert, replace the older item. Iirc, everything else stayed the same. Using more than 2 hashed really helped.

I'd just like to point out that the worse your hash algorithm is, the better Cuckoo Hashing compares to traditional hashing...... therefore, <i>study your hash functions</i>!<p>The ones that come with most languages or libraries by default quite simply aren't optimized for use on anything. There's hash functions that work better on strings and hash functions that work better on numbers (length bias). In the perfect world, this wouldn't be true, but in the real world, yes it is.<p>That said, may I recommend MurmurHash3: code.google.com/p/smhasher/wiki/MurmurHash3<p>Switch your hash tables to this. The performance difference is incredible.

Cuckoo hashing is not only optimal in theory, it is also very fast in practice. The only downside, though, is that the insert time has linear-time worst case. Thus it may be not the best solution if latency is an issue.

An interesting algorithm, and an engaging presentation. If only more academic writing was this accessible!

Is open-source implementation of this data structure available somewhere?

I recently did an exercise on cuckoo hashing at <a href="http://programmingpraxis.com/2011/02/01/cuckoo-hashing/" rel="nofollow">http://programmingpraxis.com/2011/02/01/cuckoo-hashing/</a>.

I coded a cuckoo hashed hashtable for a class once, and recently had a lecture on cuckoo hashing given to my class by Rasmus Pagh himself (inventor of cuckoo hashing). Its really surprising actually how complex the probability behind cuckoo hashing really is (and how tied to graph theory/bipartite matchings it is).<p>The amazing part is, not only is access O(1), the expected insertion time whenever there is no rehashing is also O(1) and rehashing occurs infrequently.

"WHY ELSE IS THIS COOL?" seems a very casual heading for an academic article.

It's been my experience that the O(1) was on average, not worst case.

Mitzenmacher, the author of Probability and Computing, has an interesting survey on cookoo hashing. In it there are a number of open research problems that, for those of you with interest, a worth looking over. The 7th is very interesting to me, regarding optimal ways to maintain a hash table in a parallel computing environment.<p><a href="http://www.eecs.harvard.edu/~michaelm/postscripts/esa2009.pdf" rel="nofollow">http://www.eecs.harvard.edu/~michaelm/postscripts/esa2009.pd...</a>

Every time I've tried comparing cuckoo hashing vs traditional hash algorithms in practice, the time taken to compute the additional hash functions outweighs any gains in performance.<p>Counter-intuitively, I've also noticed in many cases that using binary search over sorted elements in contiguous memory is actually faster than using a hash table at all.<p>Has anyone else found this?