HashingData structureaka closed hashing, linear probing, quadratic probing, double hashing

Open Addressing

Collision resolution where every entry lives in the bucket array itself and collisions are resolved by probing other slots.

▶ Visualize Pattern: Hashing Practice (2)

Progress

Definition

In open addressing the table is a flat array of slots, each holding at most one entry. If hash(k) mod m is occupied by another key, the insert follows a deterministic probe sequence to find a free slot; lookups follow the same sequence until they find the key or an empty slot.

Probe sequences: linear (i, i+1, i+2, …) — best cache behaviour but suffers primary clustering; quadratic (i + 1², i + 2², …) — reduces clustering but may fail to visit every slot unless m is prime or a power of two with a triangular sequence; double hashing (i + j · h2(k)) — near-ideal distribution at the cost of a second hash.

Deletion cannot simply empty a slot because that would terminate probe sequences early; instead a tombstone marker is written, which lookups skip over and inserts may reuse. Tables are rebuilt when tombstones accumulate.

Python dict, Go map, Rust HashMap (hashbrown / Swiss table), and most high-performance hash maps use open addressing because a single contiguous array is far friendlier to CPU caches than pointer chains.

collisionprobingtombstonecache-friendlyload factor

Intuition

A mental model before the formal terms.

Parking in a garage with assigned spots. If your spot is taken, you take the next one (linear probing). To find your car later, start at your assigned spot and walk forward until you see it — or hit an empty spot, which proves it is not there. A car that leaves must put up a "was parked here" cone (tombstone), or else people searching past that spot would stop too early.

Clustering: once a few adjacent spots fill up, any new car assigned to that stretch joins the same run, making it longer — clumps grow faster than the rest of the garage.

How it works

Slots hold EMPTY, DELETED (tombstone), or an entry.
find(k): start at i = hash(k) mod m; loop: if slot[i] is EMPTY, stop (absent); if it holds k, return i; otherwise i = next(i). Remember the first tombstone seen for reuse on insert.
put(k, v): run find; if k was found, overwrite; else write into the first tombstone or the empty slot reached, increment n.
remove(k): run find; if found, set the slot to DELETED and decrement n.
When (n + tombstones) / m > 0.5–0.7, rebuild into a larger table, dropping tombstones.

Why it works

Lookups and inserts traverse the same probe sequence, so an entry is always found if it exists; an EMPTY slot is proof that the sequence was never extended past that point.

Tombstones preserve that proof after deletion: they are "occupied for search, free for insert".

With uniform hashing and load α, expected probes for a successful linear-probing search are about (1 + 1/(1-α))/2 — 1.5 at α = 0.5, 5.5 at α = 0.9 — hence the low resize threshold.

Operations

Operation	Description	Cost
put(k, v)	Probe to the key, a tombstone, or an empty slot.	O(1/(1-α)) expected
get(k)	Probe until key or empty slot.	O(1/(1-α)) expected
remove(k)	Mark the slot as a tombstone.	O(1/(1-α)) expected
rehash	Rebuild into a larger table without tombstones.	O(m)

Recognition

How to tell a problem wants this.

A hash map must be implemented without per-entry allocation (embedded, GC-sensitive, or performance-critical code).
Keys and values are small and cache behaviour dominates.
The interviewer asks about tombstones, clustering, or why Python resizes its dict at 2/3 load.

“have you seen this before” → Hashing

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Hash Table visualization.

Commands — insert N, search N, delete N — m = 7 buckets, hash = key % 7

∅

bucket 0

∅

bucket 1

∅

bucket 2

∅

bucket 3

∅

bucket 4

∅

bucket 5

∅

bucket 6

∅

1/41Empty table with m = 7 buckets. Colliding keys share a bucket as a linked chain, so the table never "fills up" — only the chains grow.

Hashed bucketChain node comparedMatchInserted / removed

PseudocodeLearn Hash Table →

1h = key % m
2insert: scan bucket[h]; if key present: done, else append to the chain
3search: scan bucket[h] comparing each key
4delete: scan bucket[h]; unlink the matching node

Variables

size0

load0.00

Complexity

access O(1)

search O(1)

insert O(1)

delete O(1)

Speed

Pseudocode

1find(k):
2  i = hash(k) mod m; firstTomb = -1
3  loop:
4    if slot[i] == EMPTY: return (firstTomb if firstTomb != -1 else i), NOT_FOUND
5    if slot[i] == DELETED and firstTomb == -1: firstTomb = i
6    else if slot[i].key == k: return i, FOUND
7    i = (i + 1) mod m
8put(k, v): i, found = find(k); slot[i] = (k, v); if not found: n++; if n > 0.7 * m: rehash()
9remove(k): i, found = find(k); if found: slot[i] = DELETED; n--

Implementation

1from typing import Generic, Hashable, Optional, TypeVar
2 
3K = TypeVar("K", bound=Hashable)
4V = TypeVar("V")
5 
6# Open addressing with linear probing and tombstones.
7_EMPTY = object()
8_TOMB = object()
9 
10 
11class ProbingMap(Generic[K, V]):
121 · Slot states: empty, occupied, deleted (tombstone)
13    def __init__(self, cap: int = 8) -> None:
14        self._keys: list[object] = [_EMPTY] * cap
15        self._vals: list[Optional[V]] = [None] * cap
16        self._n = 0      # occupied
17        self._used = 0   # occupied + tombstones
18 
192 · Probe for a key or the first slot it could go in
20    def _probe(self, key: K) -> tuple[bool, int]:
21        i = hash(key) % len(self._keys)
22        first_tomb = -1
23        for _ in range(len(self._keys)):
24            k = self._keys[i]
25            if k is _EMPTY:
26                return False, (first_tomb if first_tomb >= 0 else i)
27            if k is _TOMB:
28                if first_tomb < 0:
29                    first_tomb = i
30            elif k == key:
31                return True, i
32            i = (i + 1) % len(self._keys)
33        return False, first_tomb
34 
353 · Put (reuse tombstones)
36    def put(self, key: K, value: V) -> None:
37        if (self._used + 1) * 2 > len(self._keys):  # keep load <= 0.5
38            self._rehash()
39        found, i = self._probe(key)
40        if found:
41            self._vals[i] = value
42            return
43        if self._keys[i] is not _TOMB:
44            self._used += 1
45        self._keys[i] = key
46        self._vals[i] = value
47        self._n += 1
48 
494 · Get and remove (leave a tombstone)
50    def get(self, key: K) -> Optional[V]:
51        found, i = self._probe(key)
52        return self._vals[i] if found else None
53 
54    def remove(self, key: K) -> bool:
55        found, i = self._probe(key)
56        if not found:
57            return False
58        self._keys[i] = _TOMB   # tombstone keeps probe chains intact
59        self._vals[i] = None
60        self._n -= 1
61        return True
62 
63    def __len__(self) -> int:
64        return self._n
65 
665 · Rehash drops tombstones
67    def _rehash(self) -> None:
68        old_keys, old_vals = self._keys, self._vals
69        self._keys = [_EMPTY] * (len(old_keys) * 2)
70        self._vals = [None] * (len(old_keys) * 2)
71        self._n = self._used = 0
72        for k, v in zip(old_keys, old_vals):
73            if k is not _EMPTY and k is not _TOMB:
74                self.put(k, v)  # type: ignore[arg-type]

Walkthrough

_EMPTY and _TOMB are private sentinel objects compared with is, so any hashable key is safe.
_probe returns (found, index); it remembers the first tombstone for reuse.
put rehashes at load 0.5 (CPython dict uses 2/3) and reuses tombstones.
remove writes _TOMB so probe chains stay intact.
_rehash skips sentinels when reinserting, which discards tombstones.

Complexity (this implementation)

time O(1) average at load ≤ 0.5 · space O(capacity)

Language notes

CPython dict is open addressing but with perturbed probing and a compact ordered entries array, which is why dicts are insertion-ordered.
Sentinel object() instances are the idiomatic way to make "missing" distinct from None.
zip(old_keys, old_vals) iterates the parallel arrays together.

Common mistakes in this language

Comparing sentinels with == (a key with a weird __eq__ could match); use is.
Using None as the empty marker when None is a valid key.
Deleting by writing _EMPTY.

Language differences that matter here

Sentinels: C++ uses an enum state; JS/TS use Symbol; Python uses private object() instances compared with is.
Built-ins: CPython dict and V8 Map are open-addressing tables; C++ unordered_map is chained (abseil/boost offer open-addressing maps).
C++ slots need default-constructible types or manual storage; dynamic languages just store references.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(n)
Search	O(1/(1-α))	O(n)	Linear probing; ~1.5 probes at α = 0.5.
Insert	O(1/(1-α))	O(n)	Amortized with rehash.
Delete	O(1/(1-α))	O(n)	Writes a tombstone.
Update	O(1/(1-α))	O(n)
Rehash	O(m)	O(m)
Space	O(m)		m ≈ 1.5–2 × n to keep α ≤ 0.7; no per-entry pointers.

Advantages & disadvantages

Advantages

One contiguous array: no per-entry allocation, minimal pointer overhead, excellent cache locality.
Faster than chaining for small keys at moderate load (α ≤ 0.7).
Easy to serialise or place in shared memory.

Disadvantages

Performance collapses as α → 1; must keep the table at most ~70% full, wasting memory.
Deletion requires tombstones and periodic rebuilding.
Linear probing clusters; quadratic probing and double hashing need care to guarantee the sequence covers all slots.

Use cases

CPython dict and set, Go map, Rust HashMap, Abseil flat_hash_map.
Symbol tables and interning tables in compilers.
Memory-constrained or real-time systems where allocation is costly.

Use it when

Small keys/values where cache locality dominates.
Allocation-free or GC-sensitive environments.
Read-heavy workloads with few deletions.

Avoid it when

Heavy deletion churn (tombstones accumulate, forcing rebuilds) — prefer Separate Chaining.
Large entries (probing touches many bytes per slot) — store pointers or use chaining.
You cannot afford keeping the table ≤ 70% full.

Alternatives

Separate Chaining Collision Handling Binary Search Tree

Common mistakes

Deleting by writing EMPTY instead of a tombstone, breaking lookups for keys further along the probe sequence.
Counting only live entries for the resize trigger and ignoring tombstones, so probe sequences grow unbounded.
Quadratic probing with a non-prime, non-power-of-two capacity, so some slots are never probed and inserts loop forever.
Allowing the load factor to reach 1.0 — an unsuccessful search then scans the entire table.

Interview patterns

Implement put/get/remove with linear probing and tombstones, then explain when to rehash.
Explain why CPython dicts use open addressing with a pseudo-random probe (i = 5*i + 1 + perturb) rather than linear probing.
Compare primary clustering (linear) vs. secondary clustering (quadratic) vs. double hashing.

Interview questions on this

Recognizing the approach from an array and a targetIntermediate
Deciding whether O(n²) can be improvedIntermediate
Hash map or array?Beginner
Average case versus worst caseIntermediate

Mock interviews

Two SumBeginner
Longest Substring Without Repeating CharactersIntermediate
Subarray Sum Equals KIntermediate

Interview problems

Design HashMapeasy Insert Delete GetRandom O(1)medium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related