Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representations  

The performance of a dynamic dictionary is measured mainly by its update time, lookup time, and memory consumption. In terms of update time and lookup time there are known constructions that guarantee constant-time operations in the worst case with high probability, and in terms of space consumption there are known constructions that use essentially optimal space. However, although the first analysis of a dynamic dictionary dates back more than 45 years ago, when Don Knuth analyzed linear probing, the trade-off between these aspects of performance is still not completely understood.

This work provides the construction of the first dynamic dictionary that enjoys the best of both worlds: it stores n elements using  only (1 + o(1))B bits, where B is the information-theoretic lower bound for representing a set of size n taken from a universe of size u, and guarantees constant-time operations in the worst case with high probability. This problem was open even in the amortized setting. One of the main ingredients of our construction is a permutation-based variant of cuckoo hashing.

An application of the above result is an approximate set membership data structure (AKA Bloom Filter) that is within 1+o(1) of optimal size and works in worst case O(1) time for updates and lookups.