{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:55:27Z","timestamp":1775638527156,"version":"3.50.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CNS 2118620, 1938180, 1938709, CCF 2106999, 2106827, 2118830, CSR 1763680"],"award-info":[{"award-number":["CNS 2118620, 1938180, 1938709, CCF 2106999, 2106827, 2118830, CSR 1763680"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"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"}]},{"DOI":"10.13039\/100000015","name":"DOE U.S. Department of Energy","doi-asserted-by":"publisher","award":["17-SC-20-SC"],"award-info":[{"award-number":["17-SC-20-SC"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>Modern hash table designs for DRAM and PMEM strive to minimize space while maximizing speed. The most important factor in speed is the number of cache lines accessed during updates and queries. On PMEM, there is an additional consideration, which is to minimize the number of writes, because on PMEM writes are more expensive than reads. This paper proposes two design objectives, stability and low-associativity, that enable us to build hash tables that minimize cache-line accesses for all operations. A hash table is stable if it does not move items around, and a hash table has low associativity if there are only a few locations where an item can be stored. Low associativity ensures that queries need to examine only a few memory locations, and stability ensures that insertions write to very few cache lines. Stability also simplifies concurrency and, on PMEM, crash safety. We present IcebergHT, a fast, concurrent, space-efficient, and crash-safe (for PMEM) hash table based on the design principles of stability and low associativity. IcebergHT combines in-memory metadata with a new hashing technique, iceberg hashing, that is (1) space efficient, (2) stable, and (3) supports low associativity. In contrast, existing hash-tables either modify numerous cache lines during insertions (e.g. cuckoo hashing), access numerous cache lines during queries (e.g. linear probing), or waste space (e.g. chaining). Moreover, the combination of (1)-(3) yields several emergent benefits: IcebergHT scales better than other hash tables, has excellent performance, and supports crash-safety on PMEM. Our benchmarks show that IcebergHT has excellent performance both in DRAM and PMEM. In PMEM, IcebergHT insertions are 50% to 3\u00d7 faster than state-of-the-art PMEM hash tables, such as Dash and CLHT, and queries are 20% to 2\u00d7 faster. IcebergHT space overhead is 17%, whereas Dash and CLHT have space overheads of 2\u00d7 and 3\u00d7, respectively. IcebergHT also scaled linearly throughout our experiments and is crash safe. In DRAM, IcebergHT outperforms state-of-the-art hash tables libcuckoo and CLHT by almost 2\u00d7 on insertions while offering good query throughput and much better space efficiency.<\/jats:p>","DOI":"10.1145\/3588727","type":"journal-article","created":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T22:45:09Z","timestamp":1746312309000},"page":"1-26","source":"Crossref","is-referenced-by-count":11,"title":["IcebergHT: High Performance Hash Tables Through Stability and Low Associativity"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5576-0320","authenticated-orcid":false,"given":"Prashant","family":"Pandey","sequence":"first","affiliation":[{"name":"University of Utah, Salt Lake City, UT, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7639-530X","authenticated-orcid":false,"given":"Michael A.","family":"Bender","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4890-7413","authenticated-orcid":false,"given":"Alex","family":"Conway","sequence":"additional","affiliation":[{"name":"VMware Research, Palo Alto, CA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3616-7788","authenticated-orcid":false,"given":"Martin","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, NJ, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3855-3036","authenticated-orcid":false,"given":"William","family":"Kuszmaul","sequence":"additional","affiliation":[{"name":"MIT, Boston, MA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8493-1395","authenticated-orcid":false,"given":"Guido","family":"Tagliavini","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, NJ, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0784-7410","authenticated-orcid":false,"given":"Rob","family":"Johnson","sequence":"additional","affiliation":[{"name":"VMware Research, Palo Alto, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl"},{"key":"e_1_2_2_2_1","unstructured":"Apache. [n.d.]. Cassandra. http:\/\/cassandra.apache.org."},{"key":"e_1_2_2_3_1","volume-title":"Optimal Ball Recycling","author":"Bender Michael A.","unstructured":"Michael A. Bender, Jake Christensen, Alex Conway, Martin Farach-Colton, Rob Johnson, and Meng-Tsung Tsai. 2019. Optimal Ball Recycling. In SODA. SIAM, 2527--2546."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","unstructured":"Michael A. Bender Alex Conway Mart\u00edn Farach-Colton William Kuszmaul and Guido Tagliavini. 2021. All-Purpose Hashing. https:\/\/doi.org\/10.48550\/ARXIV.2109.04548","DOI":"10.48550\/ARXIV.2109.04548"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.48"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461820"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196898"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786763.2694359"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2819001.2819002"},{"key":"e_1_2_2_11_1","unstructured":"dynamo [n.d.]. DynamoDB. https:\/\/aws.amazon.com\/dynamodb\/. Accessed: 2020--11-06."},{"key":"e_1_2_2_12_1","unstructured":"F14 [n.d.]. Facebook's F14 Hash Table. https:\/\/engineering.fb.com\/2019\/04\/25\/developer-tools\/f14\/. Accessed: 2020--11-06."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320092"},{"key":"e_1_2_2_14_1","volume-title":"10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13)","author":"Fan Bin","year":"2013","unstructured":"Bin Fan, David G. Andersen, and Michael Kaminsky. 2013. MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13). USENIX Association, Lombard, IL, 371--384. https:\/\/www.usenix.org\/conference\/nsdi13\/technical-sessions\/presentation\/fan"},{"key":"e_1_2_2_15_1","unstructured":"googlesparse [n.d.]. Google's Sparse Hash. https:\/\/github.com\/sparsehash\/sparsehash. Accessed: 2020--11-06."},{"key":"e_1_2_2_16_1","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--12.","journal-title":"J. Information Processing"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3446095.3446101"},{"key":"e_1_2_2_18_1","volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"Knuth Donald E.","unstructured":"Donald E. Knuth. 1973. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359635"},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Yossi Lev Victor Luchangco and Marek Olszewski. 2009. Scalable reader-writer locks. In SPAA. ACM 101--110.","DOI":"10.1145\/1583991.1584020"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592820"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043558"},{"key":"e_1_2_2_23_1","volume-title":"11th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 14). 429--444.","author":"Lim Hyeontaek","unstructured":"Hyeontaek Lim, Dongsu Han, David G Andersen, and Michael Kaminsky. 2014. {MICA}: A holistic approach to fast in-memory key-value storage. In 11th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 14). 429--444."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389134"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851188"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3309206"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00572-x"},{"key":"e_1_2_2_28_1","unstructured":"Memcached [n.d.]. Memcached. https:\/\/memcached.org\/. Accessed: 2020--11-06."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145874"},{"key":"e_1_2_2_30_1","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press."},{"key":"e_1_2_2_31_1","unstructured":"mongo [n.d.]. MongoDB. https:\/\/www.mongodb.com\/. Accessed: 2020--11-06."},{"key":"e_1_2_2_32_1","unstructured":"mremap [n.d.]. Linux Programmer's Manual. https:\/\/man7.org\/linux\/man-pages\/man2\/mremap.2.html. Accessed: 2021-09--14."},{"key":"e_1_2_2_33_1","volume-title":"Write-Optimized Dynamic Hashing for Persistent Memory. In 17th USENIX Conference on File and Storage Technologies (FAST 19)","author":"Nam Moohyeon","year":"2019","unstructured":"Moohyeon Nam, Hokeun Cha, Young ri Choi, Sam H. Noh, and Beomseok Nam. 2019. Write-Optimized Dynamic Hashing for Persistent Memory. In 17th USENIX Conference on File and Storage Technologies (FAST 19). USENIX Association, Boston, MA, 31--44. https:\/\/www.usenix.org\/conference\/fast19\/presentation\/nam"},{"key":"e_1_2_2_34_1","volume-title":"Rethinking File Mapping for Persistent Memory. In 19th USENIX Conference on File and Storage Technologies (FAST 21)","author":"Neal Ian","year":"2021","unstructured":"Ian Neal, Gefei Zuo, Eric Shiple, Tanvir Ahmed Khan, Youngjin Kwon, Simon Peter, and Baris Kasikci. 2021. Rethinking File Mapping for Persistent Memory. In 19th USENIX Conference on File and Storage Technologies (FAST 21). USENIX Association, 97--111. https:\/\/www.usenix.org\/conference\/fast21\/presentation\/neal"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44676-1_10"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1352079.1352134"},{"key":"e_1_2_2_38_1","unstructured":"pmdk [n.d.]. Intel. Persistent Memory Development Kit. http:\/\/pmem.io\/pmdk\/libpmem\/. Accessed August 2 2021."},{"key":"e_1_2_2_39_1","unstructured":"Redis [n.d.]. Redis. https:\/\/redis.io\/. Accessed: 2020--11-06."},{"key":"e_1_2_2_40_1","volume-title":"Hashing with Linear Probing and Referential Integrity. arXiv preprint arXiv:1808.04602","author":"Sanders Peter","year":"2018","unstructured":"Peter Sanders. 2018. Hashing with Linear Probing and Referential Integrity. arXiv preprint arXiv:1808.04602 (2018)."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2803140.2803144"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792546"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2782251"},{"key":"e_1_2_2_44_1","volume-title":"13th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 18). 461--476.","author":"Zuo Pengfei","unstructured":"Pengfei Zuo, Yu Hua, and Jie Wu. 2018. Write-optimized and high-performance hashing index scheme for persistent memory. In 13th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 18). 461--476."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3322096"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588727","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588727","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588727","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:36Z","timestamp":1750178856000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588727"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588727"],"URL":"https:\/\/doi.org\/10.1145\/3588727","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}