A scalable lock-free hash table with open addressing

Jesper Puge Nielsen, Sven Karlsson

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


Concurrent data structures synchronized with locks do not scale well with the number of threads. As more scalable alternatives, concurrent data structures and algorithms based on widely available, however advanced, atomic operations have been proposed. These data structures allow for correct and concurrent operations without any locks. In this paper, we present a new fully lock-free open addressed hash table with a simpler design than prior published work. We split hash table insertions into two atomic phases: first inserting a value ignoring other concurrent operations, then in the second phase resolve any duplicate or conflicting values.
Our hash table has a constant and low memory usage that is less than existing lock-free hash tables at a fill level of 33% and above. The hash table exhibits good cache locality. Compared to prior art, our hash table results in 16% and 15% fewer L1 and L2 cache misses respectively, leading to 21% fewer memory stall cycles. Our experiments show that our hash table scales close to linearly with the number of threads and outperforms, in throughput, other lock-free hash tables by 19%
Original languageEnglish
Title of host publicationProceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
Number of pages2
PublisherAssociation for Computing Machinery
Publication date2016
Article number33
ISBN (Print)978-1-4503-4092-2
Publication statusPublished - 2016
EventACM SIGPLAN Symposium on Principles and Practice of Parallel Programming - Barcelona, Spain
Duration: 12 Mar 201616 Mar 2016


ConferenceACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
SeriesACM SIGPLAN Notices


Dive into the research topics of 'A scalable lock-free hash table with open addressing'. Together they form a unique fingerprint.

Cite this