Search papers, labs, and topics across Lattice.
This paper introduces a lock-free linear-probing hash table that achieves wait-free lookups while maintaining the compact memory layout characteristic of sequential linear probing. The design cleverly minimizes per-entry metadata requirements, using either a constant or logarithmic number of bits depending on the atomic operation employed, thus preserving space efficiency. The proposed algorithm is linearizable and supports concurrent insert, delete, and lookup operations, demonstrating expected amortized step complexity equivalent to that of sequential linear probing under certain contention conditions.
A lock-free hash table design achieves wait-free lookups without sacrificing space efficiency, challenging the limitations of existing concurrent hash table implementations.
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.
