Technion researchers unveil lock-free linear-probing hash table with wait-free lookups

Linear probing is the go-to for sequential hash tables due to its compact memory layout and speed, but concurrent versions have struggled with liveness guarantees or required large per-entry metadata, hurting space efficiency. Attiya, Oshman, and Schiller now propose a lock-free linear-probing hash table that retains the classic design's space efficiency while adding robust concurrency. Their key insight: using only a constant number of extra bits per entry (when LL/SC is available) or a logarithmic number (with CAS) to coordinate concurrent inserts, deletes, and wait-free lookups. The algorithm is linearizable, lock-free, and can reclaim space from deleted elements without rebuilding the table, a first for this class of data structures.

Under the hood, the design carefully sequences operations to avoid deadlocks and livelocks while keeping step complexity low. The authors prove that each operation has expected amortized step complexity matching that of sequential linear probing, up to the point of contention per key. This means in practice, the hash table performs as fast as the sequential version when contention is low, and degrades gracefully under high contention. The work is especially relevant for in-memory databases, key-value stores, and real-time systems where both responsiveness and memory footprint matter. While still a paper (arXiv:2606.17315), the theoretical guarantees suggest it could become a practical building block for future concurrent systems.