Pith. sign in

REVIEW 2 cited by

Hashing with Linear Probing and Referential Integrity

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1808.04602 v1 pith:7C3VD5HQ submitted 2018-08-14 cs.DS

Peter Sanders This is my paper · ORCID
classification cs.DS
keywords integritylinearprobingreferentialtombstoneselementshashnumber
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original abstract

We describe a variant of linear probing hash tables that never moves elements and thus supports referential integrity, i.e., pointers to elements remain valid while this element is in the hash table. This is achieved by the folklore method of marking some table entries as formerly occupied (tombstones). The innovation is that the number of tombstones is minimized. Experiments indicate that this allows an unbounded number of operations with bounded overhead compared to linear probing without tombstones (and without referential integrity).

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Optimal Bounds for Open Addressing Without Reordering

    cs.DS 2025-01 accept novelty 8.0 of 10

    Open-addressed hash tables without reordering can achieve O(1) amortized and O(log 1/delta) worst-case expected probe complexity, and greedy schemes achieve O(log^2 1/delta), disproving Yao's conjecture.

  2. Linear Probing with Non-Greedy Insertions

    cs.DS 2026-07 conditional novelty 7.0 of 10

    At load factor 1−1/x, a layered non-greedy insertion strategy cuts worst-case expected insertion time for stable linear probing from Θ(x^2) to O(x log x).

Pith tools