↩ back to Hash-Based

Linear Probing

Both of this site's other open-addressing pages name this scheme without ever building it: Robin Hood Hashing's own Complexity section says its worst case is "still O(n)... just as it can for plain linear probing or chaining," and its demo's "Robin Hood swap" checkbox literally toggles this exact algorithm on and off. Linear probing is that baseline: one table, one hash function, and — unlike Robin Hood hashing's swap rule or cuckoo hashing's second table — no rule at all governing where a key ends up beyond "walk forward one slot at a time from your computed home until you find a match or an empty slot." No lists, no eviction, no second array. It's the scheme every other page in this category either builds on top of or displaces entirely.

That simplicity has a real cost besides worse probe-length variance: delete can't just null out a slot. A get that hasn't found its key yet stops the moment it hits an empty slot — that's the only signal it has that the key isn't in the table. Null out a slot that used to sit in the middle of some other key's probe path, and every key past that point becomes unreachable, even though it's still sitting right there in the array. This page's two Pitfalls are both consequences of that one fact, and its fix (a tombstone — a marker distinct from both "occupied" and "truly empty") trades the first bug for a different one.

Try it

Put a key/value pair, get one back, or delete it. The sample loads three keys — ram, pig, cat — into an 8-slot table in that order, chosen because all three hash to slot 6: ram takes slot 6 itself, pig probes one step to slot 7, and cat probes past both and wraps around to slot 0. Uncheck tombstone delete, delete ram, then try getting pig or cat — both are still sitting in the table, and both come back "not found," because the now-empty slot 6 stops the probe walk before it ever reaches them. Check the box, reload the sample, and repeat the same delete: both keys are still findable, because slot 6 now holds a tombstone instead of a true empty, and a tombstone doesn't stop the walk.

The second control, reuse tombstones on insert, targets a different bug. Click Run tombstone-fill demo with tombstone delete on: it inserts and immediately deletes eight keys that each hash to a different one of the table's eight slots, leaving every slot a tombstone and the table reporting zero live entries — then tries to insert one more key. With reuse off, that insert throws "table full" on a table that is, by its own live count, completely empty. With reuse on, it succeeds by claiming the first tombstone the new key's probe walk crosses.

Core operations

• hash(key) — the same multiply-by-31 fold-and-reduce as every other Hash-Based entry on this site. O(k) for a key of length k.
• get(key) — walk forward from hash(key), comparing keys, skipping over any tombstone without stopping. Stop and return the value on a match; stop and report "not found" the instant a truly empty (never-occupied) slot turns up. O(1) average.
• put(key, value) — walk forward from hash(key). A slot already holding that key: overwrite the value, done. A truly empty slot: place the new entry there — unless the walk already passed a tombstone, in which case place it at that first tombstone instead (when reuse is enabled), reclaiming the dead slot rather than leaving it wasted. O(1) average; resizing (doubling past a 0.75 load factor on live entries, same threshold as the site's other Hash-Based entries) amortizes to O(1) per put over a run of inserts.
• delete(key) — the same walk as get to find the slot, then mark it with the tombstone sentinel instead of clearing it to empty. The slot stays "occupied enough" to keep later keys' probe walks going, but stops counting toward the live entry total.

Reference implementation

class LinearProbingHashTable {
  static TOMBSTONE = Symbol('tombstone');
  #size;
  #table;
  #count = 0;

  constructor(size = 8) {
    this.#size = size;
    this.#table = new Array(size).fill(null);
  }

  #hash(key, size = this.#size) {
    let h = 0;
    const s = String(key);
    for (let i = 0; i < s.length; i++) h = (h * 31 + s.charCodeAt(i)) >>> 0;
    return h % size;
  }

  get(key) {
    let i = this.#hash(key);
    for (let step = 0; step < this.#size; step++) {
      const slot = this.#table[i];
      if (slot === null) return undefined;
      if (slot !== LinearProbingHashTable.TOMBSTONE && slot.key === key) return slot.value;
      i = (i + 1) % this.#size;
    }
    return undefined;
  }

  put(key, value, reuseTombstones = true) {
    let i = this.#hash(key);
    let firstTombstone = -1;
    for (let step = 0; step < this.#size; step++) {
      const slot = this.#table[i];
      if (slot === null) {
        if (reuseTombstones && firstTombstone !== -1) this.#table[firstTombstone] = { key, value };
        else this.#table[i] = { key, value };
        this.#count++;
        this.#maybeResize(reuseTombstones);
        return;
      }
      if (slot === LinearProbingHashTable.TOMBSTONE) {
        if (reuseTombstones && firstTombstone === -1) firstTombstone = i;
      } else if (slot.key === key) {
        slot.value = value;
        return;
      }
      i = (i + 1) % this.#size;
    }
    if (reuseTombstones && firstTombstone !== -1) {
      this.#table[firstTombstone] = { key, value };
      this.#count++;
      return;
    }
    throw new Error('table full');
  }

  delete(key, useTombstone = true) {
    let i = this.#hash(key);
    for (let step = 0; step < this.#size; step++) {
      const slot = this.#table[i];
      if (slot === null) return false;
      if (slot !== LinearProbingHashTable.TOMBSTONE && slot.key === key) {
        this.#table[i] = useTombstone ? LinearProbingHashTable.TOMBSTONE : null;
        this.#count--;
        return true;
      }
      i = (i + 1) % this.#size;
    }
    return false;
  }

  #maybeResize(reuseTombstones) {
    if (this.#count / this.#size <= 0.75) return;
    const old = this.#table.filter(s => s && s !== LinearProbingHashTable.TOMBSTONE);
    this.#size *= 2;
    this.#table = new Array(this.#size).fill(null);
    this.#count = 0;
    for (const slot of old) this.put(slot.key, slot.value, reuseTombstones);
  }
}

The resize check in #maybeResize only ever looks at #count — live entries — never at how many slots are tombstoned. That's deliberate, not an oversight: it matches the site's other Hash-Based entries' identical 0.75-on-live-count policy, and it's also exactly what makes the second Pitfall below possible. Verified against a plain-Map reference model over 4,000 randomized trials (300-800 interleaved put/get/delete calls each, key spaces from 5 to 20 across table sizes that force both frequent collisions and repeated resizes), checking every get/delete result against the model after every call — see /tmp/lp/verify.js, scratch, not committed. Separately confirmed the page's own three-key wraparound walkthrough and the eight-key tombstone-fill sequence by hand against this exact class, both described in the sections below.

Pitfalls

Deleting without a tombstone strands every key further along the same probe run, not just the one deleted. Loading ram, pig, cat into an empty 8-slot table (in that order) lands them at slots 6, 7, and 0 — cat wraps all the way around because slots 6 and 7 are already taken by the time it arrives. Delete ram by simply nulling slot 6 and leaving everything else in place: get("pig") starts at slot 6 (pig's own home too), finds it empty, and reports "not found" immediately — never even reaching slot 7, where pig still sits. get("cat") fails the same way, for the same reason. Both keys are still in the table; the walk just never gets far enough to see them. Marking the deleted slot with a tombstone instead fixes both at once, because a tombstone lets the walk continue instead of stopping — confirmed by running the exact shipped delete/get pair with useTombstone forced to false and then to true against the identical three-key table: two real false negatives with tombstones off, zero with them on.

An insert that doesn't reuse tombstones can report "table full" on a table with zero live entries. Eight keys — hog, hen, doe, cow, dog, koi, gnu, fox — were chosen because each hashes to a different one of an 8-slot table's eight homes. Insert and immediately delete each one in turn (tombstone delete on): every delete brings the live count back down to 0, so it never gets anywhere near the 0.75 resize threshold, but each cycle leaves one more slot permanently tombstoned. After all eight, the live count is 0 and every one of the eight slots holds a tombstone — no slot is truly empty anywhere in the table. Inserting a ninth key, cod (home slot 0, already a tombstone), walks the entire table without ever finding a null slot to stop at. An insert that only places new entries into a truly empty slot has nowhere to go and throws "table full," even though #count reports 0. Confirmed against the exact shipped put: with reuseTombstones forced to false, the ninth insert throws every time this exact sequence runs; forcing it back to true lets the walk claim the first tombstone it crosses (slot 0 itself, in this case) and the insert succeeds instead. The bug isn't the tombstone count going unwatched by the resize check — it's specifically that put never considered a tombstoned slot as available space to begin with.

Where linear probing shows up

• It's the shared starting point for this site's other two open-addressing pages. Robin Hood Hashing's own demo reproduces this exact algorithm the instant its "Robin Hood swap" checkbox is unchecked — same hash function, same forward probe walk, same lack of any rule about who gets evicted. This page exists to give that baseline its own reference implementation and its own pitfalls (tombstone deletion, tombstone-fill) rather than leaving it as an unbuilt comparison point.
• Its raw cache behavior is the one property every fancier open-addressing scheme keeps. A linear probe walk touches consecutive array slots — the exact access pattern a CPU cache line rewards — instead of chasing pointers around memory the way the site's chaining hash table does once a bucket's list grows past one node. Robin Hood hashing and cuckoo hashing both keep that same sequential-scan property (a bounded one for cuckoo, since it only ever checks two fixed slots); they add a rule on top specifically to fix this scheme's two real weaknesses — probe-length variance and the deletion pitfall above — without giving up the cache-friendly access pattern that motivated open addressing in the first place.
• Teaching. Because it has no rule beyond "walk forward," it's the standard first example used to introduce primary clustering — the tendency of open addressing to build long runs of occupied slots that merge into even longer ones — before showing a fix like Robin Hood hashing's swap rule or double hashing's staggered probe sequence.

Complexity

Time: get, put, and delete are all O(1) average, the same headline every Hash-Based entry on this site shares. Worst case is O(n), same as the chaining hash table — but unlike Robin Hood hashing, nothing here bounds how unevenly that cost falls across keys; the three-key demo above already puts one key (cat) two full slots further from home than another (ram) with nothing but insertion order to blame. Space: O(n), one table, same 0.75-live-load-factor-then-double policy as the site's other single-table entries — with the caveat the second Pitfall demonstrates directly: a table's physical fullness (live entries plus tombstones) can run well ahead of what its own live-count-based resize check ever sees.

There is no scenario, for the exact put/get/delete contract this page and Robin Hood Hashing both implement, where plain linear probing is the better choice: Robin Hood hashing's own Pitfalls section already showed that its swap rule doesn't change the total probe-step cost across a batch of inserts, only how that cost is distributed — so adding the rule never makes any single key worse off, for the same one table, one hash function, and the same load factor. That's why Choosing a Hash Table Collision Strategy sets this page aside from its three-way comparison rather than adding it as a fourth branch: the honest answer to "when should I use plain linear probing over Robin Hood hashing" is never, for this particular contract. Its value is in being the thing the other two either measure themselves against or are built directly on top of.