{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T02:19:57Z","timestamp":1773886797672,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,12,31]],"date-time":"2018-12-31T00:00:00Z","timestamp":1546214400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"<jats:p>Concurrent hash tables are one of the most important concurrent data structures, which are used in numerous applications. For some applications, it is common that hash table accesses dominate the execution time. To efficiently solve these problems in parallel, we need implementations that achieve speedups in highly concurrent scenarios. Unfortunately, currently available concurrent hashing libraries are far away from this requirement, in particular, when adaptively sized tables are necessary or contention on some elements occurs.<\/jats:p>\n          <jats:p>Our starting point for better performing data structures is a fast and simple lock-free concurrent hash table based on linear probing that is, however, limited to word-sized key-value types and does not support dynamic size adaptation. We explain how to lift these limitations in a provably scalable way and demonstrate that dynamic growing has a performance overhead comparable to the same generalization in sequential hash tables.<\/jats:p>\n          <jats:p>We perform extensive experiments comparing the performance of our implementations with six of the most widely used concurrent hash tables. Ours are considerably faster than the best algorithms with similar restrictions and an order of magnitude faster than the best more general tables. In some extreme cases, the difference even approaches four orders of magnitude.<\/jats:p>\n          <jats:p>All our implementations discussed in this publication can be found on github [17].<\/jats:p>","DOI":"10.1145\/3309206","type":"journal-article","created":{"date-parts":[[2019,2,22]],"date-time":"2019-02-22T22:19:21Z","timestamp":1550873961000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Concurrent Hash Tables"],"prefix":"10.1145","volume":"5","author":[{"given":"Tobias","family":"Maier","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}]},{"given":"Roman","family":"Dementiev","sequence":"additional","affiliation":[{"name":"Intel Deutschland GmbH, Neubiberg, Germany"}]}],"member":"320","published-online":{"date-parts":[[2019,2,22]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"143","article-title":"Zipf\u2019s law and the Internet","volume":"3","author":"Adamic Lada A.","year":"2002","unstructured":"Lada A. Adamic and Bernardo A. Huberman . 2002 . Zipf\u2019s law and the Internet . Glottometrics 3 , 1 (2002), 143 -- 150 . Lada A. Adamic and Bernardo A. Huberman. 2002. Zipf\u2019s law and the Internet. Glottometrics 3, 1 (2002), 143--150.","journal-title":"Glottometrics"},{"key":"e_1_2_1_2_1","volume-title":"Zipf distribution of U.S. firm sizes. Science 293, 5536","author":"Axtell Robert L.","year":"2001","unstructured":"Robert L. Axtell . 2001. Zipf distribution of U.S. firm sizes. Science 293, 5536 ( 2001 ), 1818--1820. Robert L. Axtell. 2001. Zipf distribution of U.S. firm sizes. Science 293, 5536 (2001), 1818--1820."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2791188.2791193"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.1999.749260"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272747"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 6th Workshop on Algorithm Engineering 8 Experiments (ALENEX\u201904)","author":"Dementiev Roman","year":"2004","unstructured":"Roman Dementiev , Lutz Kettner , Jens Mehnert , and Peter Sanders . 2004 . Engineering a sorted list data structure for 32 bit keys . In Proceedings of the 6th Workshop on Algorithm Engineering 8 Experiments (ALENEX\u201904) . 142--151. Roman Dementiev, Lutz Kettner, Jens Mehnert, and Peter Sanders. 2004. Engineering a sorted list data structure for 32 bit keys. In Proceedings of the 6th Workshop on Algorithm Engineering 8 Experiments (ALENEX\u201904). 142--151."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0873"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.054"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-004-0115-2"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90138-5"},{"key":"e_1_2_1_11_1","volume-title":"The Art of Multiprocessor Programming","author":"Herlihy Maurice","unstructured":"Maurice Herlihy and Nir Shavit . 2012. The Art of Multiprocessor Programming . Elsevier . Maurice Herlihy and Nir Shavit. 2012. The Art of Multiprocessor Programming. Elsevier."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_24"},{"key":"e_1_2_1_13_1","article-title":"Performance analysis of cache-conscious hashing techniques for multi-core CPUs","volume":"6","author":"Kim Euihyeok","year":"2013","unstructured":"Euihyeok Kim and Min-Soo Kim . 2013 . Performance analysis of cache-conscious hashing techniques for multi-core CPUs . Int. J. Control Autom. 6 , 2 (2013). Euihyeok Kim and Min-Soo Kim. 2013. Performance analysis of cache-conscious hashing techniques for multi-core CPUs. Int. J. Control Autom. 6, 2 (2013).","journal-title":"Int. J. Control Autom."},{"key":"e_1_2_1_14_1","volume-title":"The Art of Computer Programming\u2014Sorting and Searching","author":"Knuth Donald E.","unstructured":"Donald E. Knuth . 1998. The Art of Computer Programming\u2014Sorting and Searching ( 2 nd ed.). Vol. 3 . Addison Wesley . Donald E. Knuth. 1998. The Art of Computer Programming\u2014Sorting and Searching (2nd ed.). Vol. 3. Addison Wesley.","edition":"2"},{"key":"e_1_2_1_15_1","unstructured":"Doug Lea. 2003. Hash table util. concurrent. ConcurrentHashMap revision 1.3. JSR-166 the Proposed Java Concurrency Package. Retrieved from http:\/\/gee.cs.oswego.edu\/cgi-bin\/viewcvs.cgi\/jsr166\/src\/main\/java\/util\/concurrent.  Doug Lea. 2003. Hash table util. concurrent. ConcurrentHashMap revision 1.3. JSR-166 the Proposed Java Concurrency Package. Retrieved from http:\/\/gee.cs.oswego.edu\/cgi-bin\/viewcvs.cgi\/jsr166\/src\/main\/java\/util\/concurrent."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592820"},{"key":"e_1_2_1_17_1","unstructured":"Tobias Maier. 2018. GrowT. Retrieved from https:\/\/github.com\/TooBiased\/growt.  Tobias Maier. 2018. GrowT. Retrieved from https:\/\/github.com\/TooBiased\/growt."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the European Symposium on Algorithms (ESA\u201917)","volume":"87","author":"Maier Tobias","year":"2017","unstructured":"Tobias Maier and Peter Sanders . 2017 . Dynamic space efficient hashing . In Proceedings of the European Symposium on Algorithms (ESA\u201917) , Vol. 87 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Tobias Maier and Peter Sanders. 2017. Dynamic space efficient hashing. In Proceedings of the European Symposium on Algorithms (ESA\u201917), Vol. 87. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_19_1","volume-title":"Concurrent hash tables: Fast and general?(&excl;). CoRR abs\/1601.04017","author":"Maier Tobias","year":"2016","unstructured":"Tobias Maier , Peter Sanders , and Roman Dementiev . 2016. Concurrent hash tables: Fast and general?(&excl;). CoRR abs\/1601.04017 ( 2016 ). Retrieved from http:\/\/arxiv.org\/abs\/1601.04017. Tobias Maier, Peter Sanders, and Roman Dementiev. 2016. Concurrent hash tables: Fast and general?(&excl;). CoRR abs\/1601.04017 (2016). Retrieved from http:\/\/arxiv.org\/abs\/1601.04017."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851188"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/272991.272995"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"e_1_2_1_23_1","volume-title":"Slingwine","author":"McKenney Paul E.","year":"1998","unstructured":"Paul E. McKenney and John D . Slingwine . 1998 . Read-copy update: Using execution history to solve concurrency problems. Parallel Distrib. Comput. Syst . (1998), 509--518. Paul E. McKenney and John D. Slingwine. 1998. Read-copy update: Using execution history to solve concurrency problems. Parallel Distrib. Comput. Syst. (1998), 509--518."},{"key":"e_1_2_1_24_1","volume-title":"Algorithms and Data Structures\u2014The Basic Toolbox","author":"Mehlhorn Kurt","unstructured":"Kurt Mehlhorn and Peter Sanders . 2008. Algorithms and Data Structures\u2014The Basic Toolbox . Springer . Kurt Mehlhorn and Peter Sanders. 2008. Algorithms and Data Structures\u2014The Basic Toolbox. Springer."},{"key":"e_1_2_1_25_1","unstructured":"Scott Meyers. 2005. Effective C++: 55 Specific Ways to Improve Your Programs and Designs. Pearson Education.   Scott Meyers. 2005. Effective C++: 55 Specific Ways to Improve Your Programs and Designs. Pearson Education."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2747644"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI)","volume":"13","author":"Nishtala Rajesh","unstructured":"Rajesh Nishtala , Hans Fugal , Steven Grimm , Marc Kwiatkowski , Herman Lee , Harry C. Li , Ryan McElroy , Mike Paleczny , Daniel Peek , Paul Saab et al. 2013. Scaling memcache at facebook . In Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI) , Vol. 13 . 385--398. Rajesh Nishtala, Hans Fugal, Steven Grimm, Marc Kwiatkowski, Herman Lee, Harry C. Li, Ryan McElroy, Mike Paleczny, Daniel Peek, Paul Saab et al. 2013. Scaling memcache at facebook. In Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI), Vol. 13. 385--398."},{"key":"e_1_2_1_28_1","unstructured":"Rajesh Nishtala Hans Fugal Steven Grimm Marc Kwiatkowski Herman Lee Harry C. Li Ryan Mcelroy Mike Paleczny Daniel Peek Paul Saab David Stafford Tony Tung Venkateshwaran Venkataramani and Facebook Inc. 2018. folly version 57:0. Retrieved from https:\/\/github.com\/facebook\/folly.  Rajesh Nishtala Hans Fugal Steven Grimm Marc Kwiatkowski Herman Lee Harry C. Li Ryan Mcelroy Mike Paleczny Daniel Peek Paul Saab David Stafford Tony Tung Venkateshwaran Venkataramani and Facebook Inc. 2018. folly version 57:0. Retrieved from https:\/\/github.com\/facebook\/folly."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201913)","author":"Nishtala Rajesh","year":"2013","unstructured":"Rajesh Nishtala , Hans Fugal , Steven Grimm , Marc Kwiatkowski , Herman Lee , Harry C. Li , Ryan Mcelroy , Mike Paleczny , Daniel Peek , Paul Saab , David Stafford , Tony Tung , Venkateshwaran Venkataramani , and Facebook Inc. 2013 . Scaling memcached at facebook . In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201913) . Rajesh Nishtala, Hans Fugal, Steven Grimm, Marc Kwiatkowski, Herman Lee, Harry C. Li, Ryan Mcelroy, Mike Paleczny, Daniel Peek, Paul Saab, David Stafford, Tony Tung, Venkateshwaran Venkataramani, and Facebook Inc. 2013. Scaling memcached at facebook. In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201913)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45146-4_36"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223813"},{"key":"e_1_2_1_32_1","volume-title":"McKenney and Lai Jiangshan","author":"Mathieu Desnoyers","year":"2013","unstructured":"Mathieu Desnoyers Paul E. McKenney and Lai Jiangshan . 2013 . LWN : URCU-protected hash tables. Retrieved from http:\/\/lwn.net\/Articles\/573431\/. Mathieu Desnoyers Paul E. McKenney and Lai Jiangshan. 2013. LWN: URCU-protected hash tables. Retrieved from http:\/\/lwn.net\/Articles\/573431\/."},{"key":"e_1_2_1_33_1","first-page":"4","article-title":"Intel; threading building blocks","volume":"23","author":"Pheatt Chuck","year":"2008","unstructured":"Chuck Pheatt . 2008 . Intel; threading building blocks . J. Comput. Sci. Coll. 23 , 4 (April 2008), 298--298. Chuck Pheatt. 2008. Intel; threading building blocks. J. Comput. Sci. Coll. 23, 4 (April 2008), 298--298.","journal-title":"J. Comput. Sci. Coll."},{"key":"e_1_2_1_34_1","unstructured":"Jeff Preshing. 2016. Junction. Retrieved from https:\/\/github.com\/preshing\/junction.  Jeff Preshing. 2016. Junction. Retrieved from https:\/\/github.com\/preshing\/junction."},{"key":"e_1_2_1_35_1","unstructured":"Jeff Preshing. 2016. New Concurrent Hash Maps for C++. Retrieved from http:\/\/preshing.com\/20160201\/new-concurrent-hash-maps-for-cpp\/.  Jeff Preshing. 2016. New Concurrent Hash Maps for C++. Retrieved from http:\/\/preshing.com\/20160201\/new-concurrent-hash-maps-for-cpp\/."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147958"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612687"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312018"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2010.01.004"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/240518.240639"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309206","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3309206","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:22Z","timestamp":1750268962000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309206"}},"subtitle":["Fast and General(?)!"],"short-title":[],"issued":{"date-parts":[[2018,12,31]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3309206"],"URL":"https:\/\/doi.org\/10.1145\/3309206","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,31]]},"assertion":[{"value":"2016-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}