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

       Yuriy Arbitman      Moni Naor      Gil Segev     


The performance of a dynamic dictionary is measured mainly by its update time, lookup time, and space 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. In this paper we settle two fundamental open problems: