{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T03:34:04Z","timestamp":1771472044780,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642036842","type":"print"},{"value":"9783642036859","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03685-9_37","type":"book-chapter","created":{"date-parts":[[2009,8,21]],"date-time":"2009-08-21T02:39:51Z","timestamp":1250822391000},"page":"490-503","source":"Crossref","is-referenced-by-count":24,"title":["An Analysis of Random-Walk Cuckoo Hashing"],"prefix":"10.1007","author":[{"given":"Alan","family":"Frieze","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P\u00e1ll","family":"Melsted","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Mitzenmacher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"37_CR1","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/S0097539795288490","volume":"29","author":"Y. Azar","year":"1999","unstructured":"Azar, Y., Broder, A., Karlin, A., Upfal, E.: Balanced Allocations. SIAM Journal on Computing\u00a029(1), 180\u2013200 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"37_CR2","unstructured":"Broder, A., Karlin, A.: Multilevel Adaptive Hashing. In: Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 43\u201353 (1990)"},{"key":"37_CR3","doi-asserted-by":"crossref","unstructured":"Broder, A., Mitzenmacher, M.: Using Multiple Hash Functions to Improve IP Lookups. In: Proceedings of the 20th IEEE International Conference on Computer Communications (INFOCOM), pp. 1454\u20131463 (2001)","DOI":"10.1109\/INFCOM.2001.916641"},{"issue":"4","key":"37_CR4","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0020-0190(02)00500-8","volume":"86","author":"L. Devroye","year":"2003","unstructured":"Devroye, L., Morin, P.: Cuckoo Hashing: Further Analysis. Information Processing Letters\u00a086(4), 215\u2013219 (2003)","journal-title":"Information Processing Letters"},{"issue":"1-2","key":"37_CR5","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.tcs.2007.02.054","volume":"380","author":"M. Dietzfelbinger","year":"2007","unstructured":"Dietzfelbinger, M., Weidling, C.: Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins. Theoretical Computer Science\u00a0380(1-2), 47\u201368 (2007)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"37_CR6","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s00224-004-1195-x","volume":"38","author":"D. Fotakis","year":"2005","unstructured":"Fotakis, D., Pagh, R., Sanders, P., Spirakis, P.: Space Efficient Hash Tables With Worst Case Constant Access Time. Theory of Computing Systems\u00a038(2), 229\u2013248 (2005)","journal-title":"Theory of Computing Systems"},{"key":"37_CR7","unstructured":"Kirsch, A., Mitzenmacher, M.: Using a Queue to De-amortize Cuckoo Hashing in Hardware. In: Proceedings of the Forty-Fifth Annual Allerton Conference on Communication, Control, and Computing (2007)"},{"key":"37_CR8","doi-asserted-by":"crossref","unstructured":"Kirsch, A., Mitzenmacher, M., Wieder, U.: More Robust Hashing: Cuckoo Hashing with a Stash. In: Proceedings of the 16th Annual European Symposium on Algorithms, pp. 611\u2013622 (2008)","DOI":"10.1007\/978-3-540-87744-8_51"},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"Kirsch, A., Mitzenmacher, M.: The Power of One Move: Hashing Schemes for Hardware. In: Proceedings of the 27th IEEE International Conference on Computer Communications (INFOCOM), pp. 565\u2013573 (2008)","DOI":"10.1109\/INFOCOM.2008.30"},{"key":"37_CR10","doi-asserted-by":"crossref","unstructured":"Kutzelnigg, R.: Bipartite Random Graphs and Cuckoo Hashing. In: Proceedings of the Fourth Colloquium on Mathematics and Computer Science (2006)","DOI":"10.46298\/dmtcs.3486"},{"key":"37_CR11","unstructured":"Mitzenmacher, M., Vadhan, S.: Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 746\u2013755 (2008)"},{"issue":"2","key":"37_CR12","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R. Pagh","year":"2004","unstructured":"Pagh, R., Rodler, F.: Cuckoo Hashing. Journal of Algorithms\u00a051(2), 122\u2013144 (2004)","journal-title":"Journal of Algorithms"},{"issue":"4","key":"37_CR13","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1145\/792538.792546","volume":"50","author":"B. V\u00f6cking","year":"2003","unstructured":"V\u00f6cking, B.: How Asymmetry Helps Load Balancing. Journal of the ACM\u00a050(4), 568\u2013589 (2003)","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03685-9_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T20:24:15Z","timestamp":1739305455000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03685-9_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642036842","9783642036859"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03685-9_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}