{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,3]],"date-time":"2026-11-03T22:48:57Z","timestamp":1793746137117,"version":"4.6.1"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540424932","type":"print"},{"value":"9783540446767","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44676-1_10","type":"book-chapter","created":{"date-parts":[[2007,5,18]],"date-time":"2007-05-18T12:43:15Z","timestamp":1179492195000},"page":"121-133","source":"Crossref","is-referenced-by-count":153,"title":["Cuckoo Hashing"],"prefix":"10.1007","author":[{"given":"Rasmus","family":"Pagh","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Flemming Friche","family":"Rodler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2001,8,17]]},"reference":[{"issue":"1","key":"10_CR1","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/S0097539795288490","volume":"29","author":"Y. Azar","year":"1999","unstructured":"Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal. Balanced allocations. SIAM J. Comput., 29(1):180\u2013200 (electronic), 1999.","journal-title":"SIAM J. Comput."},{"key":"10_CR2","unstructured":"Andrei Broder and Michael Mitzenmacher. Using multiple hash functions to improve IP lookups. To appear in INFOCOM 2001."},{"issue":"5","key":"10_CR3","doi-asserted-by":"publisher","first-page":"1627","DOI":"10.1137\/S0097539795294165","volume":"28","author":"A. Brodnik","year":"1999","unstructured":"Andrej Brodnik and J. Ian Munro. Membership in constant time and almost-minimum space. SIAM J. Comput., 28(5):1627\u20131640 (electronic), 1999.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10_CR4","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J. L. Carter","year":"1979","unstructured":"J. Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. J. Comput. System Sci., 18(2):143\u2013154, 1979.","journal-title":"J. Comput. System Sci."},{"key":"10_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/3-540-55719-9_77","volume-title":"Proceedings of the 19th International Colloquium on Automata, Languages and Programming (ICALP\u2019 92)","author":"M. Dietzfelbinger","year":"1992","unstructured":"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\u2019 92), volume 623 of Lecture Notes in Computer Science, pages 235\u2013246. Springer-Verlag, Berlin, 1992."},{"issue":"1","key":"10_CR6","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1006\/jagm.1997.0873","volume":"25","author":"M. Dietzfelbinger","year":"1997","unstructured":"Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen. A reliable randomized algorithm for the closest-pair problem. Journal of Algorithms, 25(1):19\u201351, 1997. doi:10.1006\/jagm.1997.0873.","journal-title":"Journal of Algorithms"},{"issue":"4","key":"10_CR7","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1137\/S0097539791194094","volume":"23","author":"M. Dietzfelbinger","year":"1994","unstructured":"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\u2013761, 1994.","journal-title":"SIAM J. Comput."},{"key":"10_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/BFb0032018","volume-title":"Proceedings of the 17th International Colloquium on Automata, Languages and Programming (ICALP\u2019 90)","author":"M. Dietzfelbinger","year":"1990","unstructured":"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\u2019 90), volume 443 of Lecture Notes in Computer Science, pages 6\u201319. Springer-Verlag, Berlin, 1990."},{"issue":"12","key":"10_CR9","first-page":"6","volume":"5","author":"A. I. Dumey","year":"1956","unstructured":"Arnold I. Dumey. Indexing for rapid random access memory systems. Computers and Automation, 5(12):6\u20139, 1956.","journal-title":"Computers and Automation"},{"issue":"3","key":"10_CR10","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M. L. Fredman","year":"1984","unstructured":"Michael L. Fredman, J\u00e1nos Koml\u00f3s, and Endre Szemer\u00e9di. Storing a sparse table with O(1) worst case access time. J. Assoc. Comput. Mach., 31(3):538\u2013544, 1984.","journal-title":"J. Assoc. Comput. Mach."},{"key":"10_CR11","volume-title":"Handbook of Algorithms and Data Structures","author":"G. Gonnet","year":"1984","unstructured":"Gaston Gonnet. Handbook of Algorithms and Data Structures. Addison-Wesley Publishing Co., London, 1984."},{"issue":"4\u20135","key":"10_CR12","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/BF01940878","volume":"16","author":"R. M. Karp","year":"1996","unstructured":"Richard M. Karp, Michael Luby, and Friedhelm Meyer auf der Heide. Efficient PRAM simulation on a distributed memory machine. Algorithmica, 16(4\u20135):517\u2013542, 1996.","journal-title":"Algorithmica"},{"key":"10_CR13","unstructured":"Jyrki Katajainen and Michael Lykke. Experiments with universal hashing. Technical Report DIKU Report 96\/8, University of Copenhagen, 1996."},{"key":"10_CR14","series-title":"The Art of Computer Programming","volume-title":"Sorting and Searching","author":"D. E. Knuth","year":"1998","unstructured":"Donald E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley Publishing Co., Reading, Mass., second edition, 1998.","edition":"second edition"},{"key":"10_CR15","unstructured":"George Marsaglia. The Marsaglia random number CD ROM including the diehard battery of tests of randomness. \n                    http:\/\/stat.fsu.edu\/pub\/diehard\/\n                    \n                  ."},{"key":"10_CR16","unstructured":"Catherine C. McGeoch. The fifth DIMACS challenge dictionaries. \n                    http:\/\/cs.amherst.edu\/~ccm\/challenge5\/dicto\/\n                    \n                  ."},{"key":"10_CR17","volume-title":"LEDA. A platform for combinatorial and geometric computing","author":"K. Mehlhorn","year":"1999","unstructured":"Kurt Mehlhorn and Stefan N\u00e4her. LEDA. A platform for combinatorial and geometric computing. Cambridge University Press, Cambridge, 1999."},{"key":"10_CR18","volume-title":"Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC\u2019 01)","author":"R. Pagh","year":"2001","unstructured":"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\u2019 01). ACM Press, New York, 2001. To appear."},{"key":"10_CR19","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1109\/SFCS.1989.63450","volume-title":"Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS\u2019 89)","author":"A. Siegel","year":"1989","unstructured":"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\u2019 89), pages 20\u201325. IEEE Comput. Soc. Press, Los Alamitos, CA, 1989."},{"key":"10_CR20","unstructured":"Craig Silverstein. A practical perfect hashing algorithm. Manuscript, 1998."},{"key":"10_CR21","unstructured":"M. Wenzel. W\u00f6rterb\u00fccher f\u00fcr ein beschr\u00e4nktes universum. Diplomarbeit, Fachbereich Informatik, Universit\u00e4t des Saarlandes, 1992."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44676-1_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T14:19:16Z","timestamp":1550326756000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44676-1_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424932","9783540446767"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-44676-1_10","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]}}}