{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:02:04Z","timestamp":1775282524474,"version":"3.50.1"},"reference-count":29,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2012,5,12]],"date-time":"2012-05-12T00:00:00Z","timestamp":1336780800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2012,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The paradigm of many choices has influenced significantly the design of efficient data structures and, most notably, hash tables. Cuckoo hashing is a technique that extends this concept. There, we are given a table with<jats:italic>n<\/jats:italic>locations, and we assume that each location can hold one item. Each item to be inserted chooses randomly<jats:italic>k<\/jats:italic>\u2265 2 locations and has to be placed in any one of them. How much load can cuckoo hashing handle before collisions prevent the successful assignment of the available items to the chosen locations? Practical evaluations and theoretical analysis of this method have shown that one can allocate a number of elements that is a large proportion of the size of the table, being very close to 1 even for small values of<jats:italic>k<\/jats:italic>such as 4 or 5.<\/jats:p><jats:p>In this paper we show that there is a critical value for this proportion: with high probability, when the amount of available items is below this value, then these can be allocated successfully, but when it exceeds this value, the allocation becomes impossible. We give explicitly for each<jats:italic>k<\/jats:italic>\u2265 3 this critical value. This answers an open question posed by Mitzenmacher (<jats:italic>ESA '09<\/jats:italic>) and underpins theoretically the experimental results. Our proofs are based on the translation of the question into a hypergraph setting, and the study of the related typical properties of random<jats:italic>k<\/jats:italic>\u2010uniform hypergraphs.\u00a9 2012 Wiley Periodicals, Inc. Random Struct., 2012<\/jats:p>","DOI":"10.1002\/rsa.20426","type":"journal-article","created":{"date-parts":[[2012,5,12]],"date-time":"2012-05-12T06:53:34Z","timestamp":1336805614000},"page":"306-333","source":"Crossref","is-referenced-by-count":23,"title":["Sharp load thresholds for cuckoo hashing"],"prefix":"10.1002","volume":"41","author":[{"given":"Nikolaos","family":"Fountoulakis","sequence":"first","affiliation":[]},{"given":"Konstantinos","family":"Panagiotou","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2012,5,12]]},"reference":[{"key":"e_1_2_6_2_2","doi-asserted-by":"crossref","unstructured":"Y.Arbitman M.Naor G.Segev De\u2010amortized cuckoo hashing: Provable worst\u2010case performance and experimental results In Proceedings of the 36th International Colloquium on Automata Languages and Programming (ICALP '09) 2009 pp.107\u2013118.","DOI":"10.1007\/978-3-642-02927-1_11"},{"key":"e_1_2_6_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288490"},{"key":"e_1_2_6_4_2","volume-title":"Balanced allocations: Balls\u2010into\u2010bins revisited and chains\u2010into\u2010bins","author":"Batu T.","year":"2007"},{"key":"e_1_2_6_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90059-6"},{"key":"e_1_2_6_6_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20085"},{"key":"e_1_2_6_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"e_1_2_6_8_2","unstructured":"J. A.Cain P.Sanders N.Wormald The random graph threshold fork\u2010orientiability and a fast algorithm for optimal multiple\u2010choice allocation In Proceedings of the 18th Annual ACM\u2010SIAM Symposium on Discrete Algorithms (SODA '07) New Orleans Louisiana USA 2007 pp.469\u2013476."},{"key":"e_1_2_6_9_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20040"},{"key":"e_1_2_6_10_2","volume-title":"Applications of mathematics (New York)","author":"Dembo A.","year":"1998"},{"key":"e_1_2_6_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00500-8"},{"key":"e_1_2_6_12_2","doi-asserted-by":"crossref","unstructured":"M.Dietzfelbinger A.Goerdt M.Mitzenmacher A.Montanari R.Pagh M.Rink Tight thresholds for cuckoo hashing via xorsat In Proceedings of the 37th International Colloquium on Automata Languages and Programming (ICALP '10) 2010 pp.213\u2013225.","DOI":"10.1007\/978-3-642-14165-2_19"},{"key":"e_1_2_6_13_2","doi-asserted-by":"crossref","unstructured":"M.Dietzfelbinger R.Pagh Succinct data structures for retrieval and approximate membership In Proceedings of the 35th International Colloquium on Automata Languages and Programming (ICALP '08) 2008 pp.385\u2013396.","DOI":"10.1007\/978-3-540-70575-8_32"},{"key":"e_1_2_6_14_2","doi-asserted-by":"crossref","unstructured":"M.Dietzfelbinger U.Schellbach On risks of using cuckoo hashing with simple universal hash classes In Proceedings of the 19th Annual ACM\u2010SIAM Symposium on Discrete Algorithms (SODA '09) New York NY USA 2009 pp.795\u2013804.","DOI":"10.1137\/1.9781611973068.87"},{"key":"e_1_2_6_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.054"},{"key":"e_1_2_6_16_2","doi-asserted-by":"crossref","DOI":"10.1145\/2151171.2151174","volume-title":"A precise analysis of cuckoo hashing","author":"Drmota M.","year":"2012"},{"key":"e_1_2_6_17_2","volume-title":"Classics in Mathematics","author":"Ellis R. S.","year":"2006"},{"key":"e_1_2_6_18_2","unstructured":"D.Fernholz V.Ramachandran The k\u2010orientability thresholds forGn p In Proceedings of the 18th Annual ACM\u2010SIAM Symposium on Discrete Algorithms (SODA '07) New Orleans Louisiana USA 2007 pp.459\u2013468."},{"key":"e_1_2_6_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1195-x"},{"key":"e_1_2_6_20_2","doi-asserted-by":"crossref","unstructured":"N.Fountoulakis K.Panagiotou Orientability of random hypergraphs and the power of multiple choices In Proceedings of the 37th International Colloquium on Automata Languages and Programming (ICALP '10) 2010 pp.348\u2013359.","DOI":"10.1007\/978-3-642-14165-2_30"},{"key":"e_1_2_6_21_2","article-title":"Maximum matchings in random bipartite graphs and the space utilization of cuckoo hashtables","author":"Frieze A. M.","year":"2009","journal-title":"Random Struct Algorithms"},{"key":"e_1_2_6_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/090770928"},{"key":"e_1_2_6_23_2","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718.scard","volume-title":"Wiley\u2010Interscience Series in Discrete Mathematics and Optimization","author":"Janson S.","year":"2000"},{"key":"e_1_2_6_24_2","doi-asserted-by":"crossref","unstructured":"J. H.Kim Poisson cloning model for random graphs In Proceedings of the International Congress of Mathematicians 2006 pp.873\u2013897.","DOI":"10.4171\/022-3\/43"},{"key":"e_1_2_6_25_2","unstructured":"A.Kirsch M.Mitzenmacher Using a queue to de\u2010amortize cuckoo hashing in hardware In Proceedings of the 45th Annual Allerton Conference on Communication Control and Computing Monticello Illinois USA 2007 pp.751\u2013758."},{"key":"e_1_2_6_26_2","doi-asserted-by":"crossref","unstructured":"M.Mitzenmacher Some open questions related to cuckoo hashing In Proceedings of the ESA 2009 Volume 5757 of Lecture Notes in Computer Science 2009 pp.1\u201310.","DOI":"10.1007\/978-3-642-04128-0_1"},{"key":"e_1_2_6_27_2","doi-asserted-by":"crossref","unstructured":"M.Mitzenmacher S.Vadhan Why simple hash functions work: exploiting the entropy in a data stream Proceedings of the 19th Annual ACM\u2010SIAM Symposium on Discrete Algorithms (SODA '08) San Francisco California USA 2008 pp.746\u2013755.","DOI":"10.1137\/1.9780898716474"},{"key":"e_1_2_6_28_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20061"},{"key":"e_1_2_6_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_2_6_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792546"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20426","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20426","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.20426","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,24]],"date-time":"2024-04-24T13:53:48Z","timestamp":1713966828000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.20426"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,12]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["10.1002\/rsa.20426"],"URL":"https:\/\/doi.org\/10.1002\/rsa.20426","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,5,12]]}}}