Skip to Main content Skip to Navigation
Conference papers

Bipartite Random Graphs and Cuckoo Hashing

Abstract : The aim of this paper is to extend the analysis of Cuckoo Hashing of Devroye and Morin in 2003. In particular we make several asymptotic results much more precise. We show, that the probability that the construction of a hash table succeeds, is asymptotically $1-c(\varepsilon)/m+O(1/m^2)$ for some explicit $c(\varepsilon)$, where $m$ denotes the size of each of the two tables, $n=m(1- \varepsilon)$ is the number of keys and $\varepsilon \in (0,1)$. The analysis rests on a generating function approach to the so called Cuckoo Graph, a random bipartite graph. We apply a double saddle point method to obtain asymptotic results covering tree sizes, the number of cycles and the probability that no complex component occurs.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184689
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 17, 2015 - 2:23:21 PM
Last modification on : Thursday, May 11, 2017 - 1:02:51 AM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:06:12 PM

File

dmAG0133.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184689, version 1

Collections

Citation

Reinhard Kutzelnigg. Bipartite Random Graphs and Cuckoo Hashing. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. pp.403-406. ⟨hal-01184689⟩

Share

Metrics

Record views

311

Files downloads

911