Cuckoo Hashing

I found out about this data structure last night while reading programming.reddit.com, which is often a valuable resource. Cuckoo Hashing was described in the comments as a simpler implementation of a solution to the same problem Judy sparse arrays are trying to solve (O(1) lookups and inserts, minimal space usage for even large collections). I found an implementation of the Cuckoo Hash (http://www.tcllab.org/canasai/software/ckhash/ckhash-0.4.1/) and have been writing Python bindings for it, too.

You can read more about the data structure here:

We present a simple dictionary with worst case constant lookup time, equaling the theoretical performance of the classic dynamic perfect hashing scheme of Dietzfel- binger et al. (Dynamic perfect hashing: Upper and lower bounds. SIAM J. Comput., 23(4):738–761, 1994). The space usage is similar to that of binary search trees. Besides being conceptually much simpler than previous dynamic dictionaries with worst case constant lookup time, our data structure is interesting in that it does not use perfect hashing, but rather a variant of open addressing where keys can be moved back in their probe sequences. An implementation inspired by our algorithm, but using weaker hash functions, is found to be quite practical. It is competitive with the best known dictionaries having an average case (but no nontrivial worst case) guarantee on lookup time.

Source: Cuckoo Hashing, Rasmus Pagh and Flemming Friche Rodler, 2003.