Cuckoo hashing papers
A Cool And Practical Alternative To Traditional Hash Tables
More Robust Hashing: Cuckoo Hashing with a Stash
Recent advances in the theoretical literature have proposed interesting modifications to traditional hash tables. The authors of these papers propose hash tables which
a) have a guaranteed constant time for a lookup
b) have amortized constant time for an insertion
c) require table size only slightly larger than the space for the elements
Previous hash table technologies have offered at most two of these three.