---
title: "Hash Table — Linear Probing"
description: "Open addressing: probe forward on collision, tombstones for delete"
source: https://vizlearn.app/algorithms/data-structures/hash-table-probing
---

# Hash Table — Linear Probing

A hash table with linear probing is an open-addressing hash table that stores every key directly in one array and resolves collisions by scanning forward, one slot at a time, until it finds a free slot. With a low load factor, `insert`, `get`, and `delete` all run in O(1) average time; the cost is clustering as the table fills.

Think of the array as a parking lot with numbered spaces. The hash function `h(k) = k mod capacity` is the space printed on your permit. If your space is taken, you don't file a complaint — you roll forward to the next space, and the next, wrapping at the end of the lot, until you find one free. Every operation here is some version of that drive.

## How Linear Probing Works

The table is a fixed array of `capacity` slots, each in exactly one of three states: **empty** (never used), **occupied** (holds a key), or **tombstone** (a key was deleted here). The tombstone is a cone left in a vacated parking space: the space is reusable, but it tells anyone driving past that the row of cars used to continue — so keep driving.

All three operations start at `i = hash(k)` and probe forward with `i = (i + 1) mod capacity`, for at most one full lap.

`get(k)` checks each slot: an occupied slot holding `k` means found, return the index. An empty slot means stop — if `k` existed, it would have been parked along this run before any gap appeared. A tombstone or a non-matching key means keep probing. This is why delete cannot simply blank a slot: an empty cell is a *promise* that no probe sequence continues past it, and breaking that promise silently loses keys further down the run.

`delete(k)` runs the same probe and, on a match, writes a tombstone instead of empty. The key is gone; the cone stays, so later lookups still drive past.

`insert(k)` is the subtle one. It probes forward remembering `spot`, the first reusable slot it passes — the first tombstone, or failing that the empty terminator. But it does **not** stop at the first tombstone. It keeps probing until it hits an empty slot (the key is definitely absent) or finds `k` already in the table (then it returns without writing — inserts are idempotent, never a second copy). Only then does it write, into the remembered `spot`. Stop at the first tombstone and you'd happily park a duplicate of a key already sitting three spaces down. If a full lap finds neither a match nor a reusable slot, insert raises an overflow — a real property of open addressing, not a quirk of this animation: the array is the entire storage, so a full table has nowhere left to put anything.

One honest disclosure: the capacity slider runs 5 to 11 and keys are limited to 1–99 only because that's what fits legibly on the canvas. The table-full overflow, though, is the data structure's own behavior at any size.

## Linear Probing Step by Step

The default table is empty with capacity 7, so `h(k) = k mod 7`. Each operation below plays exactly as the animation emits it: a hash-computation beat, one beat per slot probed, then a commit beat.

`insert(10)`: `h(10) = 10 mod 7 = 3`. Slot 3 is empty — 10 is not present, place it at slot 3.

`insert(20)`: `h(20) = 6`. Slot 6 is empty — place 20 at slot 6.

`insert(17)`: `h(17) = 3`. Slot 3 holds 10, not 17 — probe next. Slot 4 is empty — place 17 at slot 4. Your first collision: two keys, one assigned space, and the second driver rolls forward.

`insert(24)`: `h(24) = 3`. Slot 3 holds 10 — probe next. Slot 4 holds 17 — probe next. Slot 5 is empty — place 24 at slot 5. Notice the run growing: slots 3, 4, 5 are now one contiguous cluster, and every future key hashing to 3 pays for all of it.

`get(17)`: `h(17) = 3`. Slot 3 holds 10, no match — probe next. Slot 4 holds 17 — found at index 4, after 2 probes.

`delete(10)`: `h(10) = 3`. Slot 3 holds 10 — match. Mark slot 3 as a tombstone, not empty. The cone goes down.

`get(17)` again: `h(17) = 3`. Slot 3 is a tombstone — keep probing past it. Slot 4 holds 17 — found at index 4. Had delete blanked slot 3 instead, this lookup would have stopped at the gap and wrongly reported not-found.

`insert(31)`: `h(31) = 31 mod 7 = 3`. Slot 3 is a tombstone — remember it as the reuse spot, keep probing. Slot 4 holds 17 — probe next. Slot 5 holds 24 — probe next. Slot 6 holds 20 — probe next, wrapping to slot 0. Slot 0 is empty — 31 is confirmed absent, so write it into the remembered slot 3. The tombstone is reclaimed, and the probe walked the whole run first to rule out a duplicate.

In the player, the probe cursor walks the row slot by slot from `h(k)`, the slot under inspection lights up each beat, and tombstones render in their own muted marker color so you can tell a cone from a free space at a glance — a visual layer on top of the trace above, not a replacement for it.

## Time and Space Complexity

| Operation | Average (low load factor) | Worst case |
|---|---|---|
| `insert` | O(1) | O(n) |
| `get` | O(1) | O(n) |
| `delete` | O(1) | O(n) |

Space is O(m) for a table of m slots — the array is the only allocation, with no per-entry pointers, which is open addressing's structural edge over chaining.

The time complexity story is entirely about the load factor `α = n / m`. Probe counts grow as the occupied fraction approaches 1. Successful and unsuccessful searches have different expected costs, and linear probing’s clusters make a single `1 / (1 − α)` estimate insufficient for both. The mechanism behind that curve is **primary clustering**, this lesson's real takeaway: occupied slots form contiguous runs, any key hashing *anywhere* into a run must traverse to its end, and every insert that lands in a run extends it — so big clusters grow faster than small ones. The slots-3-through-5 run in the trace above is a cluster in miniature. Production tables resize (rehashing every live key into a larger array) before `α` crosses roughly 0.7–0.75, because past that point the lot is one long traffic jam.

## Edge Cases

- **Duplicate insert.** `insert(k)` when `k` is already present finds the match during the probe and returns without writing — no overwrite, no second copy.
- **Full table.** A full probe lap with no empty slot, no tombstone, and no match raises overflow. Real implementations resize long before this.
- **Delete or get on a missing key.** The probe stops at the first empty slot and reports not-found; if no slot is empty, the one-lap cap still guarantees termination after m probes.
- **Tombstone accumulation.** Heavy insert/delete churn leaves the table mostly cones with few live keys, and probes still walk past every cone — lookups degrade even at low *live* load. Resizing doubles as the cleanup, since only real keys get rehashed.

## Common Mistakes

- **Deleting by blanking the slot.** The classic bug. Any key that probed past the deleted slot becomes unreachable, because lookups now stop at the false gap. Tombstones exist solely to prevent this.
- **Insert stopping at the first tombstone.** Write there immediately and you can duplicate a key sitting further down the run. Remember the spot, finish the probe, then write — exactly as the displayed code does.
- **Forgetting the modular wrap.** Probing is `i = (i + 1) mod capacity`. Without the modulo, a key hashing near the end of the array walks off it instead of wrapping to slot 0, as `insert(31)` does above.
- **Skipping tombstones on insert.** Lookups probe past tombstones; inserts *reuse* them. Treating a cone as occupied leaks slots forever.
- **Never resizing.** Above roughly 75% load, clusters merge and average probe length climbs steeply toward O(n). Monitoring the load factor and doubling the table is part of the data structure, not an optimization.