{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T06:29:03Z","timestamp":1778048943167,"version":"3.51.4"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2023,11,30]],"date-time":"2023-11-30T00:00:00Z","timestamp":1701302400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CSR-1938180, CCF-2106999, CCF-2118620, CCF-2118832, CCF-2106827, CCF-1725543, CSR-1763680, CCF-1716252 and CNS-1938709"],"award-info":[{"award-number":["CSR-1938180, CCF-2106999, CCF-2118620, CCF-2118832, CCF-2106827, CCF-1725543, CSR-1763680, CCF-1716252 and CNS-1938709"]}]},{"name":"NSF GRFP fellowship and a Fannie and John Hertz Fellowship"},{"DOI":"10.13039\/100006602","name":"United States Air Force Research Laboratory","doi-asserted-by":"crossref","award":["FA8750-19-2-1000"],"award-info":[{"award-number":["FA8750-19-2-1000"]}],"id":[{"id":"10.13039\/100006602","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>Despite being one of the oldest data structures in computer science, hash tables continue to be the focus of a great deal of both theoretical and empirical research. A central reason for this is that many of the fundamental properties that one desires from a hash table are difficult to achieve simultaneously; thus many variants offering different trade-offs have been proposed.<\/jats:p>\n          <jats:p>\n            This article introduces Iceberg hashing, a hash table that simultaneously offers the strongest known guarantees on a large number of core properties. Iceberg hashing supports constant-time operations while improving on the state of the art for space efficiency, cache efficiency, and low failure probability. Iceberg hashing is also the first hash table to support a load factor of up to\n            <jats:italic>1 - o(1)<\/jats:italic>\n            while being stable, meaning that the position where an element is stored only ever changes when resizes occur. In fact, in the setting where keys are \u0398 (log\n            <jats:italic>n<\/jats:italic>\n            ) bits, the space guarantees that Iceberg hashing offers, namely that it uses at most\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\log \\binom{|U|}{n} + O(n \\log \\ \\text{log} n)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            bits to store\n            <jats:italic>n<\/jats:italic>\n            items from a universe\n            <jats:italic>U<\/jats:italic>\n            , matches a lower bound by Demaine et\u00a0al. that applies to any stable hash table.\n          <\/jats:p>\n          <jats:p>Iceberg hashing introduces new general-purpose techniques for some of the most basic aspects of hash-table design. Notably, our indirection-free technique for dynamic resizing, which we call waterfall addressing, and our techniques for achieving stability and very-high probability guarantees, can be applied to any hash table that makes use of the front-yard\/backyard paradigm for hash table design.<\/jats:p>","DOI":"10.1145\/3625817","type":"journal-article","created":{"date-parts":[[2023,10,2]],"date-time":"2023-10-02T08:24:42Z","timestamp":1696235082000},"page":"1-51","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Iceberg Hashing: Optimizing Many Hash-Table\u00a0Criteria at Once"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7639-530X","authenticated-orcid":false,"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4890-7413","authenticated-orcid":false,"given":"Alex","family":"Conway","sequence":"additional","affiliation":[{"name":"Cornell Tech, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3616-7788","authenticated-orcid":false,"given":"Mart\u00edn","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"Rutgers University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3855-3036","authenticated-orcid":false,"given":"William","family":"Kuszmaul","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8493-1395","authenticated-orcid":false,"given":"Guido","family":"Tagliavini","sequence":"additional","affiliation":[{"name":"Snowflake Inc., USA"}]}],"member":"320","published-online":{"date-parts":[[2023,11,30]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"abseil[2020.]. Google\u2019s Abseil C++ Library. Retrieved June 11 2020 from https:\/\/abseil.io\/. Accessed: 2020-11-06."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_11"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.80"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch21"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461814"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch21"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00026"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00115"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SWAT.2020.11"},{"key":"e_1_3_3_12_2","unstructured":"Ioana Oriana Bercea and Guy Even. 2020. A Space-Efficient Dynamic Dictionary for Multisets with Constant Time Operations. arXiv:2005.02143. Retrieved from https:\/\/arxiv.org\/abs\/2005.02143"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.39"},{"key":"e_1_3_3_14_2","unstructured":"cplusplus1 [2020.]. cpppreference std::unordered_map. Retrieved June 11 2020 from https:\/\/en.cppreference.com\/w\/cpp\/container\/unordered_map"},{"key":"e_1_3_3_15_2","unstructured":"cplusplus2 [2020.]. gcc-mirror\/gcc libstdc++-v3 unordered_map.h. Retrieved June 11 2020 from https:\/\/github.com\/gcc-mirror\/gcc\/blob\/master\/libstdc%2B%2B-v3\/include\/bits\/unordered_map.h"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/11682462_34"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0032018"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21968"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.054"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780634"},{"key":"e_1_3_3_21_2","unstructured":"F14 [2020.]. Facebook\u2019s F14 Hash Table. Retrieved June 11 2020 from https:\/\/engineering.fb.com\/2019\/04\/25\/developer-tools\/f14\/. Accessed: 2020-11-06."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36494-3_25"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/1382436.1382752"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100217"},{"key":"e_1_3_3_25_2","unstructured":"Michael T. Goodrich Daniel S Hirschberg Michael Mitzenmacher and Justin Thaler. 2011. Fully de-amortized cuckoo hashing for cache-oblivious dictionaries and multimaps. arXiv:1107.4378. Retrieved from https:\/\/arxiv.org\/abs\/1107.4378"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34862-4_15"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3582016.3582021"},{"issue":"1","key":"e_1_3_3_28_2","first-page":"1","article-title":"Studies on hashing part-1: A comparison of hashing algorithms with key deletion","volume":"3","author":"Gunji Takao","year":"1980","unstructured":"Takao Gunji and Eiichi Goto. 1980. Studies on hashing part-1: A comparison of hashing algorithms with key deletion. J. Information Processing 3, 1 (1980), 1\u201312.","journal-title":"J. Information Processing"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1171"},{"key":"e_1_3_3_30_2","first-page":"570","volume-title":"Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Iacono John","year":"2012","unstructured":"John Iacono and Mihai P\u0103tra\u015fcu. 2012. Using hashing to solve the dictionary problem. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms. 570\u2013582."},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.5555\/3118790.3119279"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9267-y"},{"key":"e_1_3_3_33_2","volume-title":"The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition","author":"Knuth Donald E.","year":"1973","unstructured":"Donald E. Knuth. 1973. The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley. Retrieved from https:\/\/www.worldcat.org\/oclc\/310903895"},{"key":"e_1_3_3_34_2","volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"Knuth Donald E.","year":"1973","unstructured":"Donald E. Knuth. 1973. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley."},{"key":"e_1_3_3_35_2","volume-title":"The art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1","author":"Knuth Donald E.","year":"2011","unstructured":"Donald E. Knuth. 2011. The art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Pearson Education India."},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00097"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2157.322407"},{"key":"e_1_3_3_38_2","first-page":"224","volume-title":"Proceedings of the VLDB","author":"Larson Per-\u00c5ke","year":"1980","unstructured":"Per-\u00c5ke Larson. 1980. Linear hashing with partial expansions. In Proceedings of the VLDB. 224\u2013232."},{"key":"e_1_3_3_39_2","first-page":"1","volume-title":"Proceedings of the VLDB","volume":"80","author":"Litwin Witold","year":"1980","unstructured":"Witold Litwin. 1980. Linear Hashing: A new tool for file and table addressing. In Proceedings of the VLDB, Vol. 80. 1\u20133."},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.79"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217022"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00572-x"},{"issue":"1","key":"e_1_3_3_43_2","first-page":"148","article-title":"On the method of bounded differences","volume":"141","author":"McDiarmid Colin","year":"1989","unstructured":"Colin McDiarmid. 1989. On the method of bounded differences. Surveys in Combinatorics 141, 1 (1989), 148\u2013188.","journal-title":"Surveys in Combinatorics"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00003817"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1137\/060658400"},{"key":"e_1_3_3_46_2","first-page":"487","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Pagh Rasmus","year":"2000","unstructured":"Rasmus Pagh. 2000. Faster deterministic dictionaries. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms. 487\u2013493."},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9763-6"},{"key":"e_1_3_3_49_2","volume-title":"Proceedings of the 2023 ACM International Conference on Management of Data","author":"Pandey Prashant","year":"2023","unstructured":"Prashant Pandey, Michael A. Bender, Alex Conway, Martin Farach-Colton, William Kuszmaul, Guido Tagliavini, and Rob Johnson. 2023. IcebergHT: High performance PMEM hash tables through stability and low associativity. In Proceedings of the 2023 ACM International Conference on Management of Data."},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.26"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1147\/rd.12.0130"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/2220357.2220361"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45061-0_30"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/1328911.1328912"},{"key":"e_1_3_3_55_2","unstructured":"Peter Sanders. 2018. Hashing with linear probing and referential integrity. arXiv:1808.04602. Retrieved from https:\/\/arxiv.org\/abs\/1808.04602"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701386216"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185427"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1137\/110842211"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.5555\/26953"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3625817","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3625817","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:12Z","timestamp":1750182552000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3625817"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,30]]},"references-count":58,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1145\/3625817"],"URL":"https:\/\/doi.org\/10.1145\/3625817","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,30]]},"assertion":[{"value":"2021-09-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-08-27","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}