Skip to Main content Skip to Navigation
Conference papers

Double Hashing Thresholds via Local Weak Convergence

Mathieu Leconte 1, 2, 3, *
* Corresponding author
2 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : A lot of interest has recently arisen in the analysis of multiple-choice "cuckoo hashing" schemes. In this context, a main performance criterion is the load threshold under which the hashing scheme is able to build a valid hashtable with high probability in the limit of large systems; various techniques have successfully been used to answer this question (differential equations, combinatorics, cavity method) for increasing levels of generality of the model. However, the hashing scheme analysed so far is quite utopic in that it requires to generate a lot of independent, fully random choices. Schemes with reduced randomness exists, such as "double hashing", which is expected to provide similar asymptotic results as the ideal scheme, yet they have been more resistant to analysis so far. In this paper, we point out that the approach via the cavity method extends quite naturally to the analysis of double hashing and allows to compute the corresponding threshold. The path followed is to show that the graph induced by the double hashing scheme has the same local weak limit as the one obtained with full randomness.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Mathieu Leconte Connect in order to contact the contributor
Submitted on : Monday, January 20, 2014 - 10:04:29 PM
Last modification on : Thursday, November 18, 2021 - 4:08:34 AM
Long-term archiving on: : Monday, April 21, 2014 - 5:40:23 PM


Files produced by the author(s)


  • HAL Id : hal-00933627, version 1


Mathieu Leconte. Double Hashing Thresholds via Local Weak Convergence. 51st Annual Allerton Conference on Communication, Control, and Computing, Oct 2013, Urbana-Champaign, United States. ⟨hal-00933627⟩



Record views


Files downloads