2026-07-25T14:32:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10070 2024-03-06T10:45:32Z ddc:004 open_access

Concurrent Robin Hood Hashing Kelly, Robert Pearlmutter, Barak A. Maguire, Phil concurrency Robin Hood Hashing data-structures hash tables non-blocking In this paper we examine the issues involved in adding concurrency to the Robin Hood hash table algorithm. We present a non-blocking obstruction-free K-CAS Robin Hood algorithm which requires only a single word compare-and-swap primitive, thus making it highly portable. The implementation maintains the attractive properties of the original Robin Hood structure, such as a low expected probe length, capability to operate effectively under a high load factor and good cache locality, all of which are essential for high performance on modern computer architectures. We compare our data-structures to various other lock-free and concurrent algorithms, as well as a simple hardware transactional variant, and show that our implementation performs better across a number of contexts. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert Kelly and Barak A. Pearlmutter and Phil Maguire 2019 Is Part Of LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2018.10 urn:nbn:de:0030-drops-100701 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.10 eng https://creativecommons.org/licenses/by/3.0/legalcode