pith. sign in

arxiv: 2606.17315 · v1 · pith:WXT6RGVBnew · submitted 2026-06-15 · 💻 cs.DC · cs.DS

Space-Efficient Lock-Free Linear-Probing Hash Table

Hagit Attiya , Rotem Oshman , Noa Schiller This is my paper

Pith reviewed 2026-06-27 02:18 UTC · model grok-4.3

classification 💻 cs.DC cs.DS
keywords linear probinghash tablelock-freewait-free lookupconcurrent data structurelinearizabilityspace reclamation
0
0 comments X

The pith

A lock-free linear-probing hash table supports wait-free lookups using only constant extra bits per entry.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents a concurrent hash table that uses linear probing for collision resolution while remaining lock-free. It adds only a constant number of extra bits per entry (or logarithmic with CAS) to support safe concurrent inserts, deletes, and wait-free lookups. The design is linearizable and allows reclamation of space from deleted items without rebuilding the entire table. Under the assumption of no concurrent same-key inserts, the amortized step complexity of each operation matches that of the sequential version up to point contention per key. This preserves the space and performance advantages of linear probing in a concurrent setting where they were previously difficult to achieve.

Core claim

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

What carries the argument

Per-entry metadata of constant bits (LL/SC) or logarithmic bits (CAS) that enables lock-free linear probing with safe deletion reclamation and wait-free lookups.

If this is right

  • Each operation achieves expected amortized step complexity matching sequential linear probing up to point contention per key.
  • The table preserves the space efficiency of sequential linear probing.
  • Deleted elements can be reclaimed without rebuilding the table.
  • Lookups are wait-free while inserts and deletes are lock-free.
  • The table satisfies linearizability for all operations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same minimal-metadata approach could extend to other probing schemes such as quadratic probing under concurrency.
  • Memory-constrained multi-threaded applications could adopt this structure to reduce per-entry overhead compared with existing concurrent hash tables.
  • Future work might relax the no-concurrent-same-key-insert assumption by adding extra synchronization only on detected conflicts.
  • The design suggests a path for bringing sequential probing techniques into other lock-free data structures that currently require heavier metadata.

Load-bearing premise

The amortized step complexity analysis assumes no concurrent insertions of the same key.

What would settle it

A concurrent workload with multiple threads inserting the same key, in which the measured amortized steps per operation exceed the sequential linear-probing bound by more than the point-contention factor.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper presents a lock-free linear-probing hash table supporting wait-free lookups, insert, delete, and safe reclamation of deleted entries without table rebuilds. It uses only constant additional bits per entry (with LL/SC) or logarithmic bits (with CAS), claims linearizability and lock-freedom, and analyzes amortized step complexity under an explicit assumption of no concurrent insertions of the same key, showing expected costs match those of sequential linear probing up to point contention per key.

Significance. If the design and analysis hold, the result would be significant as one of the few space-efficient concurrent linear-probing hash tables with strong liveness and reclamation guarantees, preserving the compact layout advantage of sequential linear probing while addressing contention. The explicit assumption in the complexity analysis is noted but limits the scope of the performance claim.

major comments (1)
  1. The amortized step complexity analysis (described in the abstract and presumably detailed in the analysis section): the bound matching sequential linear probing is derived under the explicit assumption of no concurrent insertions of the same key. This assumption is load-bearing for the performance guarantee, as concurrent duplicate-key inserts could change probing sequences and contention patterns in the lock-free design; without additional analysis or a proof that the bound holds more generally, the expected complexity result does not apply to arbitrary workloads.

Simulated Author's Rebuttal

1 responses · 1 unresolved

We thank the referee for the careful reading and for highlighting the role of the explicit assumption in our complexity analysis. We respond to the major comment below.

read point-by-point responses

  1. Referee: [—] The amortized step complexity analysis (described in the abstract and presumably detailed in the analysis section): the bound matching sequential linear probing is derived under the explicit assumption of no concurrent insertions of the same key. This assumption is load-bearing for the performance guarantee, as concurrent duplicate-key inserts could change probing sequences and contention patterns in the lock-free design; without additional analysis or a proof that the bound holds more generally, the expected complexity result does not apply to arbitrary workloads.

    Authors: We agree that the amortized step-complexity bound is derived under the explicit assumption of no concurrent insertions of the same key, as stated in the abstract and analysis section. This assumption is necessary for the current proof technique because concurrent duplicate-key insertions can alter the linearization points and contention patterns along a probe sequence. We will revise the manuscript (abstract, introduction, and analysis section) to state the assumption more prominently, to clarify that the matching bound therefore applies only to workloads satisfying the assumption, and to discuss the practical settings (e.g., set semantics where duplicate-key inserts are disallowed or serialized) in which the assumption is reasonable. We do not currently possess a proof that removes the assumption while retaining the same bound. revision: yes

standing simulated objections not resolved
  • A general amortized-complexity analysis that holds for arbitrary workloads (including concurrent duplicate-key insertions) is not available and would require substantial new technical work.

Circularity Check

0 steps flagged

No circularity; analysis is conditional on explicit external assumption

full rationale

The paper states its amortized complexity result explicitly under the assumption of no concurrent insertions of the same key and claims it matches the known behavior of sequential linear probing (an external reference point). No equations, fitted parameters, or self-citations are shown that reduce the claimed result to a quantity defined in terms of itself. The derivation chain is therefore self-contained against the stated assumption and does not exhibit any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no explicit free parameters, axioms, or invented entities; the complexity claim rests on the stated assumption of no concurrent same-key insertions.

pith-pipeline@v0.9.1-grok · 5728 in / 1144 out tokens · 17730 ms · 2026-06-27T02:18:23.150598+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 13 canonical work pages

  1. [1]

    Anderson and Mark Moir

    James H. Anderson and Mark Moir. Universal constructions for multi-object operations. In Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Com- puting, PODC ’95, pages 184––193, New York, NY, USA, 1995. Association for Computing Machinery.doi:10.1145/224964.224985

    work page doi:10.1145/224964.224985 1995

  2. [2]

    Arm Ltd., 2026

    Arm Ltd.Arm Architecture Reference Manual for A-profile architecture. Arm Ltd., 2026. Document ID: DDI 0487, Issue M.b. URL:https://developer.arm.com/documentation/ ddi0487/

    2026

  3. [3]

    2025 , isbn =

    Hagit Attiya, Michael A. Bender, Mart´ ın Farach-Colton, Rotem Oshman, and Noa Schiller. History-independent concurrent hash tables. InProceedings of the 57th Annual ACM Sym- posium on Theory of Computing (STOC), pages 1283––1294, New York, NY, USA, 2025. Association for Computing Machinery.doi:10.1145/3717823.3718283

    work page doi:10.1145/3717823.3718283 2025

  4. [4]

    Bender, Mart´ ın Farach-Colton, John Kuszmaul, William Kuszmaul, and Mingmou Liu

    Michael A. Bender, Mart´ ın Farach-Colton, John Kuszmaul, William Kuszmaul, and Mingmou Liu. On the optimal time/space tradeoff for hash tables. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1284–1297, New York, NY, USA, 2022. Association for Computing Machinery.doi:10.1145/3519935.3519969

    work page doi:10.1145/3519935.3519969 2022

  5. [5]

    Blelloch and Yuanhao Wei

    Guy E. Blelloch and Yuanhao Wei. LL/SC and Atomic Copy: Constant Time, Space Efficient Implementations Using Only Pointer-Width CAS. In Hagit Attiya, editor,34th International Symposium on Distributed Computing (DISC 2020), volume 179 ofLeibniz International Pro- ceedings in Informatics (LIPIcs), pages 5:1–5:17, Dagstuhl, Germany, 2020. Schloss Dagstuhl –...

    work page doi:10.4230/lipics.disc.2020.5 2020

  6. [6]

    A lock-free wait-free hash table, 2007

    Cliff Click. A lock-free wait-free hash table, 2007. Accessed on 2024-07-04. URL:http: //www.stanford.edu/class/ee380/Abstracts/070221

    2007

  7. [7]

    Hesselink

    Hui Gao, Jan Friso Groote, and Wim H. Hesselink. Lock-free dynamic hash tables with open addressing.Distrib. Comput., 18(1):21––42, July 2005.doi:10.1007/s00446-004-0115-2. 31

    work page doi:10.1007/s00446-004-0115-2 2005

  8. [8]

    Elsevier, 2020.doi:10.1016/C2011-0-06993-4

    Maurice Herlihy, Nir Shavit, Victor Luchangco, and Michael Spear.The Art of Multiprocessor Programming, Second Edition. Elsevier, 2020.doi:10.1016/C2011-0-06993-4

    work page doi:10.1016/c2011-0-06993-4 2020

  9. [9]

    Hopscotch hashing

    Maurice Herlihy, Nir Shavit, and Moran Tzafrir. Hopscotch hashing. InProceedings of the 22nd International Symposium on Distributed Computing (DISC), pages 350––364, Berlin, Heidelberg, 2008. Springer-Verlag.doi:10.1007/978-3-540-87779-0_24

    work page doi:10.1007/978-3-540-87779-0_24 2008

  10. [10]

    Disjoint-access-parallel implementations of strong shared memory primitives

    Amos Israeli and Lihu Rappoport. Disjoint-access-parallel implementations of strong shared memory primitives. InProceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’94, pages 151—-160, New York, NY, USA, 1994. Association for Computing Machinery.doi:10.1145/197917.198079

    work page doi:10.1145/197917.198079 1994

  11. [11]

    Efficient and practical constructions of ll/sc variables

    Prasad Jayanti and Srdjan Petrovic. Efficient and practical constructions of ll/sc variables. In Proceedings of the Twenty-Second Annual Symposium on Principles of Distributed Computing, PODC ’03, pages 285––294, New York, NY, USA, 2003. Association for Computing Machinery. doi:10.1145/872035.872078

    work page doi:10.1145/872035.872078 2003

  12. [12]

    Donald E. Knuth. Notes on “open” addressing. Unpublished memorandum, July 1963

    1963

  13. [13]

    Folklore sampling is optimal for exact hopsets: Confirming the √n barrier

    Tianxiao Li, Jingxun Liang, Huacheng Yu, and Renfei Zhou. Tight cell-probe lower bounds for dynamic succinct dictionaries. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1842–1862, 2023.doi:10.1109/FOCS57990.2023.00112

    work page doi:10.1109/focs57990.2023.00112 2023

  14. [14]

    Concurrent hash tables: Fast and general(?)!ACM Trans

    Tobias Maier, Peter Sanders, and Roman Dementiev. Concurrent hash tables: Fast and general(?)!ACM Trans. Parallel Comput., 5(4), February 2019.doi:10.1145/3309206

    work page doi:10.1145/3309206 2019

  15. [15]

    Maged M. Michael. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architec- tures (SPAA), pages 73–82. ACM, 2002

    2002

  16. [16]

    Practical implementations of non-blocking synchronization primitives

    Mark Moir. Practical implementations of non-blocking synchronization primitives. InPro- ceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’97, pages 219––228, New York, NY, USA, 1997. Association for Computing Machin- ery.doi:10.1145/259380.259442

    work page doi:10.1145/259380.259442 1997

  17. [17]

    Lock-free cuckoo hashing

    Nhan Nguyen and Philippas Tsigas. Lock-free cuckoo hashing. In2014 IEEE 34th International Conference on Distributed Computing Systems, pages 627–636, 2014

    2014

  18. [18]

    Non-blocking hashtables with open addressing

    Chris Purcell and Tim Harris. Non-blocking hashtables with open addressing. InProceedings of the 19th International Conference on Distributed Computing (DISC), pages 108—-121, Berlin, Heidelberg, 2005. Springer-Verlag.doi:10.1007/11561927_10

    work page doi:10.1007/11561927_10 2005

  19. [19]

    Split-ordered lists: Lock-free extensible hash tables.Journal of the ACM, 53(3):379–405, 2006

    Ori Shalev and Nir Shavit. Split-ordered lists: Lock-free extensible hash tables.Journal of the ACM, 53(3):379–405, 2006

    2006

  20. [20]

    Blelloch

    Julian Shun and Guy E. Blelloch. Phase-concurrent hash tables for determinism. InProceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 96––107, New York, NY, USA, 2014. Association for Computing Machinery.doi:10.1145/ 2612669.2612687. 32

    arXiv 2014