{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T03:31:42Z","timestamp":1771471902515,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642041273","type":"print"},{"value":"9783642041280","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","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-04128-0_1","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T18:16:36Z","timestamp":1252952196000},"page":"1-10","source":"Crossref","is-referenced-by-count":19,"title":["Some Open Questions Related to Cuckoo Hashing"],"prefix":"10.1007","author":[{"given":"Michael","family":"Mitzenmacher","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Adler, M., Chakrabarti, S., Mitzenmacher, M., Rasmussen, L.: Parallel randomized load balancing. In: Proceedings of the 27th Annual ACM Symposium on the Theory of Computing, pp. 238\u2013247 (1995)","DOI":"10.1145\/225058.225131"},{"key":"1_CR2","unstructured":"Alcantara, D., Sharf, A., Abbasinejad, F., Amenta, N., Mitzenmacher, M., Owens, J., Sengupta, S.: Real-time parallel hashing on the GPU (submitted)"},{"key":"1_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/978-3-642-02927-1_11","volume-title":"ICALP 2009","author":"Y. Arbitman","year":"2009","unstructured":"Arbitman, Y., Naor, M., Segev, G.: De-amortized cuckoo hashing: provable worst-case performance and experimental results. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. Part I. LNCS, vol.\u00a05555, pp. 107\u2013118. Springer, Heidelberg (2009)"},{"issue":"1","key":"1_CR4","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 of Computing\u00a029(1), 180\u2013200 (1999)","journal-title":"SIAM Journal of Computing"},{"key":"1_CR5","unstructured":"Batu, T., Berenbrink, P., Cooper, C.: Balanced allocations: Balls-into-bins revisited and chains-into-bins. CDAM Research Report LSE-CDAM-2007-34"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"Braverman, M.: Poly-logarithmic independence fools AC0 circuits. To appear in Proceedings of the 24th Annual IEEE Conference on Computational Complexity (2009)","DOI":"10.1109\/CCC.2009.35"},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Broder, A., Mitzenmacher, M.: Using multiple hash functions to improve IP Lookups. In: Proceedings of IEEE INFOCOM, pp. 1454\u20131463 (2001)","DOI":"10.1109\/INFCOM.2001.916641"},{"key":"1_CR8","unstructured":"Cain, J., Sanders, P., Wormald, N.: The random graph threshold for k-orientability and a fast algorithm for optimal multiple-choice allocation. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 469\u2013476 (2007)"},{"issue":"2","key":"1_CR9","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J.L. Carter","year":"1979","unstructured":"Carter, J.L., Wegman, M.N.: Universal classes of hash functions. Journal of Computer and System Sciences\u00a018(2), 143\u2013154 (1979)","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/978-3-540-85363-3_29","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"K.M. Chung","year":"2008","unstructured":"Chung, K.M., Vadhan, S.: Tight bounds for hashing block sources. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 357\u2013370. Springer, Heidelberg (2008)"},{"key":"1_CR11","unstructured":"Cohen, J., Kane, D.: Bounds on the independence required for cuckoo hashing (preprint)"},{"key":"1_CR12","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1137\/S0097539704443240","volume":"35","author":"K. Dalal","year":"2006","unstructured":"Dalal, K., Devroye, L., Malalla, E., McLeish, E.: Two-way chaining with reassignment. SIAM Journal on Computing\u00a035, 327\u2013340 (2006)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"1_CR13","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1006\/inco.1993.1007","volume":"102","author":"M. Dietzfelbinger","year":"1993","unstructured":"Dietzfelbinger, M., Meyer auf der Heide, F.: An optimal parallel dictionary. Information and Computation\u00a0102(2), 196\u2013217 (1993)","journal-title":"Information and Computation"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Meyer auf der Heide, F.: Simple, efficient shared memory simulations. In: Proceedings of the Fifth Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 110\u2013119 (1993)","DOI":"10.1145\/165231.165246"},{"key":"1_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/978-3-540-70575-8_32","volume-title":"Automata, Languages and Programming","author":"M. Dietzfelbinger","year":"2008","unstructured":"Dietzfelbinger, M., Pagh, R.: Succinct data structures for retrieval and approximate membership (Extended abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 385\u2013396. Springer, Heidelberg (2008)"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Schellbach, U.: On risks of using cuckoo hashing with simple universal hash classes. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 795\u2013804 (2009)","DOI":"10.1137\/1.9781611973068.87"},{"issue":"1-2","key":"1_CR17","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"},{"key":"1_CR18","unstructured":"Fernholz, D., Ramachandran, V.: The k-orientability thresholds for G n,p . In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 459\u2013468 (2007)"},{"issue":"2","key":"1_CR19","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"},{"issue":"3","key":"1_CR20","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M. Fredman","year":"1984","unstructured":"Fredman, M., Koml\u00f3s, J., Szemer\u00e9di, E.: Stoaring a sparse table with O(1) worst case access time. Journal of the Association of Computing Machinery\u00a031(3), 538\u2013544 (1984)","journal-title":"Journal of the Association of Computing Machinery"},{"key":"1_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1007\/978-3-642-03685-9_37","volume-title":"APPROX 2009 and RANDOM 2009","author":"A. Frieze","year":"2009","unstructured":"Frieze, A., Melsted, P., Mitzenmacher, M.: An analysis of random-walk cuckoo hashing. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009 and RANDOM 2009. LNCS, vol.\u00a05687, pp. 490\u2013503. Springer, Heidelberg (2009)"},{"issue":"2","key":"1_CR22","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1145\/322248.322254","volume":"28","author":"G. Gonnet","year":"1981","unstructured":"Gonnet, G.: Expected length of the longest probe sequence in hash code searching. Journal of the Association for Computing Machinery\u00a028(2), 289\u2013304 (1981)","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"4","key":"1_CR23","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/BF01940878","volume":"16","author":"R. Karp","year":"1996","unstructured":"Karp, R., Luby, M., Meyer, F., Meyer auf der Heide, F.: Efficient PRAM simulation on a distributed memory machine. Algorithmica\u00a016(4), 517\u2013542 (1996)","journal-title":"Algorithmica"},{"key":"1_CR24","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":"1_CR25","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. 106\u2013110 (2008)","DOI":"10.1109\/INFOCOM.2008.30"},{"key":"1_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1007\/978-3-540-87744-8_51","volume-title":"Algorithms - ESA 2008","author":"A. Kirsch","year":"2008","unstructured":"Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: Cuckoo hashing with a stash. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol.\u00a05193, pp. 611\u2013622. Springer, Heidelberg (2008)"},{"key":"1_CR27","volume-title":"Preprint, to appear in Algorithms for Next Generation Networks","author":"A. Kirsch","year":"2009","unstructured":"Kirsch, A., Mitzenmacher, M., Varghese, G.: Hash-based techniques for high-speed packet processing. Preprint, to appear in Algorithms for Next Generation Networks. Springer, Heidelberg (2009)"},{"key":"1_CR28","volume-title":"The Art of Computer Programming, Sorting and Searching","author":"D. Knuth","year":"1973","unstructured":"Knuth, D.: The Art of Computer Programming, Sorting and Searching, vol.\u00a03. Addison-Wesley, Reading (1973)"},{"key":"1_CR29","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":"1_CR30","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/978-1-4615-0013-1_9","volume-title":"Handbook of Randomized Computing","author":"M. Mitzenmacher","year":"2001","unstructured":"Mitzenmacher, M., Richa, A., Sitaraman, R.: The power of two choices: a survey of techniques and results. In: Pardalos, P., Rajasekaran, S., Reif, J., Rolim, J. (eds.) Handbook of Randomized Computing, pp. 255\u2013312. Kluwer Academic Publishers, Norwell (2001)"},{"issue":"2","key":"1_CR31","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1145\/274787.274816","volume":"45","author":"P. MacKenzie","year":"1998","unstructured":"MacKenzie, P., Plaxton, C.G., Rajaraman, R.: On contention resolution protocols and associated probabilistic phenomena. Journal of the ACM\u00a045(2), 324\u2013378 (1998)","journal-title":"Journal of the ACM"},{"key":"1_CR32","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)"},{"key":"1_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1007\/978-3-540-70583-3_51","volume-title":"Automata, Languages and Programming","author":"M. Naor","year":"2008","unstructured":"Naor, M., Segev, G., Wieder, U.: History-Independent Cuckoo Hashing. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol.\u00a05126, pp. 631\u2013642. Springer, Heidelberg (2008)"},{"key":"1_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/3-540-44676-1_10","volume-title":"Algorithms - ESA 2001","author":"A. Pagh","year":"2001","unstructured":"Pagh, A., Rodler, F.: Cuckoo hashing. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 121\u2013133. Springer, Heidelberg (2001)"},{"issue":"2","key":"1_CR35","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"A. Pagh","year":"2004","unstructured":"Pagh, A., Rodler, F.: Cuckoo hashing. Journal of Algorithms\u00a051(2), 122\u2013144 (2004)","journal-title":"Journal of Algorithms"},{"key":"1_CR36","unstructured":"Porat, E.: An optimal Bloom filter replacement based on matrix solving. Technical report, arxiv:0804.1845v1 [cs.DS] (April 2008)"},{"key":"1_CR37","doi-asserted-by":"crossref","unstructured":"Siegel, A.: 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, pp. 20\u201325 (1989)","DOI":"10.1109\/SFCS.1989.63450"},{"issue":"4","key":"1_CR38","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","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,10]],"date-time":"2021-10-10T18:06:28Z","timestamp":1633889188000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}