A further analysis of Cuckoo Hashing with a Stash and Random Graphs of Excess r

Abstract : Cuckoo hashing is a hash table data structure offering constant access time, even in the worst case. As a drawback, the construction fails with small, but practically significant probability. However, Kirsch et al. (2008) showed that a constant-sized additional memory, the so called stash, is sufficient to reduce the failure rate drastically. But so far, using a modified insertion procedure that demands additional running time to look for an admissible key is required. As a major contribution of this paper, we show that the same bounds on the failure probability hold even without this search process and thus, the performance increases. Second, we extend the analysis to simplified cuckoo hashing, a variant of the original algorithm offering increased performance. Further, we derive some explicit asymptotic approximations concerning the number of usual resp. bipartite graphs related to the data structures. Using these results, we obtain much more precise asymptotic expansions of the success rate. These calculations are based on a generating function approach and applying the saddle point method. Finally, we provide numerical results to support the theoretical analysis.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (3), pp.81-101
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990450
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:37:24
Dernière modification le : mercredi 29 novembre 2017 - 10:26:19
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:18:08

Fichier

1345-5517-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990450, version 1

Collections

Citation

Reinhard Kutzelnigg. A further analysis of Cuckoo Hashing with a Stash and Random Graphs of Excess r. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (3), pp.81-101. 〈hal-00990450〉

Partager

Métriques

Consultations de la notice

86

Téléchargements de fichiers

548