Space-Efficient Lock-Free Linear-Probing Hash Table
This work solves the long-standing problem of designing a space-efficient concurrent linear-probing hash table with strong liveness guarantees, benefiting systems requiring high concurrency and memory efficiency.
The paper presents a lock-free linear-probing hash table with wait-free lookups that uses minimal per-entry metadata (constant bits with LL/SC, logarithmic with CAS) while achieving linearizability and lock-freedom. The algorithm matches the expected amortized step complexity of sequential linear probing under low contention.
Linear probing is one of the simplest and most space-efficient approaches to hash table design, and is widely used in sequential settings due to its compact memory layout. However, designing a concurrent linear-probing hash table with strong liveness guarantees has proved difficult, and only a handful of such algorithms have been proposed, all of which either restrict concurrency or rely on large per-entry metadata, thereby compromising space efficiency. We present a lock-free linear-probing hash table with wait-free lookups that retains the core advantages of sequential linear probing while handling contention gracefully. Our design uses only a small amount of metadata per table entry: a constant number of additional bits when using LL/SC, or a logarithmic number of bits when using CAS. The algorithm is linearizable and lock-free, supports insert, delete, and wait-free lookup operations, and is able to safely reclaim space used by deleted elements without rebuilding the table. We analyze the amortized step complexity of our hash table assuming no concurrent insertions of the same key, and show that each operation has expected amortized step complexity matching that of sequential linear probing, up to the point contention per key.