I’ve been learning about cuckoo hashing this evening and to help with that I’ve written an implementation in Common Lisp that others might find useful: cuckoo.lisp. It provides a package cuckoo which exports make-cuckoo-hash, cuckoo-insert, cuckoo-lookup, and cuckoo-delete which perform the obvious hash-table operations. The key feature of cuckoo hashes, if you haven’t come across them before, is that they have constant worst-case lookup time. They are also quite amenable to implementation in hardware.

The keys are implicitly fixnums since it’s a prototype for a C/VHDL implementation, but it shouldn’t be too hard to extend to a generic key type. The insert function automatically rehashes in-place if the table becomes full. The hash function is the xor of three randomly selected universal hash functions, as recommended by the Pagh and Rodler paper.