Kelly, Robert and Pearlmutter, Barak A. and Maguire, Phil
(2020)
Lock-free hopscotch hashing.
Symposium on Algorithmic Principles of Computer Systems (APOCS).
Abstract
In this paper we present a lock-free version of Hopscotch
Hashing. Hopscotch Hashing is an open addressing algorithm originally proposed by Herlihy, Shavit, and Tzafrir
[10], which is known for fast performance and excellent cache
locality. The algorithm allows users of the table to skip or
jump over irrelevant entries, allowing quick search, insertion, and removal of entries. Unlike traditional linear probing, Hopscotch Hashing is capable of operating under a high
load factor, as probe counts remain small. Our lock-free
version improves on both speed, cache locality, and progress
guarantees of the original, being a chimera of two concurrent hash tables. We compare our data structure to various
other lock-free and blocking hashing algorithms and show
that its performance is in many cases superior to existing
strategies. The proposed lock-free version overcomes some of
the drawbacks associated with the original blocking version,
leading to a substantial boost in scalability while maintaining attractive features like physical deletion or probe-chain
compression.
| Item Type: |
Article
|
| Additional Information: |
The first meeting of the Symposium on Algorithmic Principles of Computer Systems (APOCS20) was held in Salt Lake City, Utah, on January 8, 2020. The symposium was supported by SIAM, the Society for Industrial and Applied Mathematics, and by SIGACT, the ACM Special Interest Group on Algorithms and Computation Theory. |
| Keywords: |
Lock-free; hopscotch; hashing; |
| Academic Unit: |
Faculty of Science and Engineering > Computer Science |
| Item ID: |
15097 |
| Identification Number: |
https://doi.org/10.1137/1.9781611976021.4 |
| Depositing User: |
Barak Pearlmutter
|
| Date Deposited: |
07 Dec 2021 15:23 |
| Journal or Publication Title: |
Symposium on Algorithmic Principles of Computer Systems (APOCS) |
| Publisher: |
SIAM - Society for Industrial and Applied Mathematics |
| Refereed: |
Yes |
| URI: |
|
| Use Licence: |
This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available
here |
Repository Staff Only(login required)
 |
Item control page |
Downloads per month over past year
Origin of downloads
Altmetric
Altmetric