A precise analysis of Cuckoo hashing

Cuckoo hashing was introduced by Pagh and Rodler in 2001. Its main feature is that it provides constant worst-case search time. The aim of this article is to present a precise average case analysis of Cuckoo hashing. In particular, we determine the probability that Cuckoo hashing produces no conflicts and give an upper bound for the construction time, that is linear in the size of the table. The analysis rests on a generating function approach to the so called Cuckoo Graph, a random bipartite graph, and an application of a double saddle point method to obtain asymptotic expansions. Furthermore, we provide some results concerning the structure of these kinds of random graphs. Our results extend the analysis of Devroye and Morin [2003]. Additionally, we provide numerical results confirming the mathematical analysis.