HackerPapers

arXiv:1808.04602cs.DS

Hashing with Linear Probing and Referential Integrity

Peter Sanders

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

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).

arXiv comments
5 pages, 3 figures
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Nov 2023 to Nov 2023.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Hashmaps in Factor are faster than in Zig 1 comment

    • Here is a simple heuristic for avoiding most tombstones when the load factor isn't too high: https://arxiv.org/pdf/1808.04602.pdf

      senderistaView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.