Cuckoo hashing in C

Question

Does anybody have an implementation of Cuckoo hashing in C? If there was an Open Source, non GPL version it would be perfect!

Since Adam mentioned it in his comment, anyone knows why it is not much used? Is it just a matter of implementation or the good theoretical properties do not materialize in practice?

Answer 1

As other answers have pointed out, it's true that the simplest cuckoo hashtable requires that the table be half empty. However, the concept has been generalized to d-ary cuckoo hashing, in which each key has d possible places to nest, as opposed to 2 places in the simple version.

The acceptable load factor increases quickly as d is increased. For only d=3, you can already use around a 75% full table. The downside is that you need d independent hash functions. I'm a fan of Bob Jenkins' hash functions for this purpose (see http://burtleburtle.net/bob/c/lookup3.c), which you might find useful in a cuckoo hashing implementation.

Answer 2

Cuckoo hashing is relatively unused outside of academia (aside from hardware caches, which sometimes borrow ideas from, but don't really implement fully). It requires a very sparse hash table to get good time on insertions - you really need to have 51% of your table empty for good performance. So it is either fast and takes a lot of space, or slow and uses space efficiently - never both. Other algorithms are both time and space efficient, although they are worse than cuckoo when only time or space is taken into account.

Here is a code generator for cuckoo hash tables. Check the license of the generator to verify that the output is non GPL. It should be, but check anyway.

-Adam

Answer 3

http://www.mpi-inf.mpg.de/~sanders/programs/cuckoo/

HTH