MURAL - Maynooth University Research Archive Library



    Lock-free hopscotch hashing


    Kelly, Robert, Pearlmutter, Barak A. and Maguire, Phil (2020) Lock-free hopscotch hashing. Symposium on Algorithmic Principles of Computer Systems (APOCS).

    [thumbnail of BP_lock-free.pdf]
    Preview
    Text
    BP_lock-free.pdf

    Download (995kB) | Preview

    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: 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
    Related URLs:
    URI: https://mural.maynoothuniversity.ie/id/eprint/15097
    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
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads