Abstract
We present a simple and efficient dictionary with worst case constant lookup time, equaling the theoretical performance of the classic dynamic perfect hashing scheme of Dietzfelbinger et al. The space usage is similar to that of binary search trees, i.e., three words per key on average. The practicality of the scheme is backed by extensive experiments and comparisons with known methods, showing it to be quite competitive also in the average case.
Partially supported by the IST Programme of the EU under contract number IST-1999-14186 (ALCOM-FT). Work initiated while visiting Stanford University.
Basic Research in Computer Science (http://www.brics.dk), funded by the Danish National Research Foundation.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal. Balanced allocations. SIAM J. Comput., 29(1):180–200 (electronic), 1999.
Andrei Broder and Michael Mitzenmacher. Using multiple hash functions to improve IP lookups. To appear in INFOCOM 2001.
Andrej Brodnik and J. Ian Munro. Membership in constant time and almost-minimum space. SIAM J. Comput., 28(5):1627–1640 (electronic), 1999.
J. Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. J. Comput. System Sci., 18(2):143–154, 1979.
Martin Dietzfelbinger, Joseph Gil, Yossi Matias, and Nicholas Pippenger. Polynomial hash functions are reliable (extended abstract). In Proceedings of the 19th International Colloquium on Automata, Languages and Programming (ICALP’ 92), volume 623 of Lecture Notes in Computer Science, pages 235–246. Springer-Verlag, Berlin, 1992.
Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen. A reliable randomized algorithm for the closest-pair problem. Journal of Algorithms, 25(1):19–51, 1997. doi:10.1006/jagm.1997.0873.
Martin Dietzfelbinger, Anna Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, and Robert E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. SIAM J. Comput., 23(4):738–761, 1994.
Martin Dietzfelbinger and Friedhelm Meyer auf der Heide. A new universal class of hash functions and dynamic hashing in real time. In Proceedings of the 17th International Colloquium on Automata, Languages and Programming (ICALP’ 90), volume 443 of Lecture Notes in Computer Science, pages 6–19. Springer-Verlag, Berlin, 1990.
Arnold I. Dumey. Indexing for rapid random access memory systems. Computers and Automation, 5(12):6–9, 1956.
Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a sparse table with O(1) worst case access time. J. Assoc. Comput. Mach., 31(3):538–544, 1984.
Gaston Gonnet. Handbook of Algorithms and Data Structures. Addison-Wesley Publishing Co., London, 1984.
Richard M. Karp, Michael Luby, and Friedhelm Meyer auf der Heide. Efficient PRAM simulation on a distributed memory machine. Algorithmica, 16(4–5):517–542, 1996.
Jyrki Katajainen and Michael Lykke. Experiments with universal hashing. Technical Report DIKU Report 96/8, University of Copenhagen, 1996.
Donald E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley Publishing Co., Reading, Mass., second edition, 1998.
George Marsaglia. The Marsaglia random number CD ROM including the diehard battery of tests of randomness. http://stat.fsu.edu/pub/diehard/.
Catherine C. McGeoch. The fifth DIMACS challenge dictionaries. http://cs.amherst.edu/~ccm/challenge5/dicto/.
Kurt Mehlhorn and Stefan Näher. LEDA. A platform for combinatorial and geometric computing. Cambridge University Press, Cambridge, 1999.
Rasmus Pagh. On the Cell Probe Complexity of Membership and Perfect Hashing. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC’ 01). ACM Press, New York, 2001. To appear.
Alan Siegel. On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS’ 89), pages 20–25. IEEE Comput. Soc. Press, Los Alamitos, CA, 1989.
Craig Silverstein. A practical perfect hashing algorithm. Manuscript, 1998.
M. Wenzel. Wörterbücher für ein beschränktes universum. Diplomarbeit, Fachbereich Informatik, Universität des Saarlandes, 1992.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pagh, R., Rodler, F.F. (2001). Cuckoo Hashing. In: auf der Heide, F.M. (eds) Algorithms — ESA 2001. ESA 2001. Lecture Notes in Computer Science, vol 2161. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44676-1_10
Download citation
DOI: https://doi.org/10.1007/3-540-44676-1_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42493-2
Online ISBN: 978-3-540-44676-7
eBook Packages: Springer Book Archive