{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:27:54Z","timestamp":1787340474926,"version":"build-2736575974"},"reference-count":14,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>In this paper, we provide a polylogarithmic bound that holds with high probability on the insertion time for cuckoo hashing under the random-walk insertion method. Cuckoo hashing provides a useful methodology for building practical, high-performance hash tables. The essential idea of cuckoo hashing is to combine the power of schemes that allow multiple hash locations for an item with the power to dynamically change the location of an item among its possible locations. Previous work on the case where the number of choices is larger than two has analyzed breadth-first search, which is both inefficient in practice and currently has only a polynomial upper bound on the insertion time that holds with high probability. On the other hand, it does have expected constant amortized insertion time. Here we significantly advance the state of the art by proving a polylogarithmic bound that holds with high probability on the more efficient random-walk method, where items repeatedly kick out random blocking items until a free location for an item is found.<\/jats:p>","DOI":"10.1137\/090770928","type":"journal-article","created":{"date-parts":[[2011,3,29]],"date-time":"2011-03-29T18:45:36Z","timestamp":1301424336000},"page":"291-308","source":"Crossref","is-referenced-by-count":19,"title":["An Analysis of Random-Walk Cuckoo Hashing"],"prefix":"10.1137","volume":"40","author":[{"given":"Alan","family":"Frieze","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"P\u00e1ll","family":"Melsted","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Mitzenmacher","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,3,29]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288490"},{"key":"R2","unstructured":"A. Broder and A. Karlin,\n                      Multilevel adaptive hashing\n                      , in Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA), 1990, pp. 43\u201353."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"A. Broder and M. Mitzenmacher,\n                      Using multiple hash functions to improve IP lookups\n                      , in Proceedings of the 20th IEEE International Conference on Computer Communications (INFOCOM), 2001, pp. 1454\u20131463.","DOI":"10.1109\/INFCOM.2001.916641"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00500-8"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.054"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1195-x"},{"key":"R7","unstructured":"N. Fountoulakis, K. Panagioutou, and A. Steger,\n                      On the Insertion Time of Cuckoo Hashing\n                      , arXiv:1006.1231."},{"key":"R8","unstructured":"A. Kirsch and M. Mitzenmacher,\n                      Using a queue to de-amortize cuckoo hashing in hardware\n                      , in Proceedings of the 45th Annual Allerton Conference on Communication, Control, and Computing, 2007, pp. 751\u2013758."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"A. Kirsch and M. Mitzenmacher,\n                      The power of one move: Hashing schemes for hardware\n                      , in Proceedings of the 27th IEEE International Conference on Computer Communications (INFOCOM), 2008, pp. 565\u2013573.","DOI":"10.1109\/INFOCOM.2007.30"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"A. Kirsch, M. Mitzenmacher, and U. Wieder,\n                      More robust hashing: Cuckoo hashing with a stash\n                      , in Proceedings of the 16th Annual European Symposium on Algorithms, 2008, pp. 611\u2013622.","DOI":"10.1007\/978-3-540-87744-8_51"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"R. Kutzelnigg,\n                      Bipartite random graphs and cuckoo hashing\n                      , in Proceedings of the Fourth Colloquium on Mathematics and Computer Science, 2006, pp. 403\u2013406.","DOI":"10.46298\/dmtcs.3486"},{"key":"R12","unstructured":"M. Mitzenmacher and S. Vadhan,\n                      Why simple hash functions work: Exploiting the entropy in a data stream\n                      , in Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008, pp. 746\u2013755."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792546"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090770928","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:36:11Z","timestamp":1787337371000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090770928"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/090770928"],"URL":"https:\/\/doi.org\/10.1137\/090770928","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}