Open addressing
mediumEverything lives in the table, which is far friendlier to the cache than following chain pointers. Watch linear probing form clusters, then switch to double hashing and watch them scatter.
O(1) below α ≈ 0.7Worst O(n)Space O(m)Saved in this browser - no sign-up, nothing sent anywhere.
How open addressing works
Open addressing refuses to allocate lists: every key lives directly in one of the m slots. When slot h(k) is taken, a probe sequence dictates where to look next - linear tries i, i + 1, i + 2; quadratic tries offsets 0, 1, 4, 9; double hashing steps by a second hash, h2(k) = 1 + (k mod (m - 1)). Lookup replays the identical sequence until it finds the key or a never-used slot.
The payoff is locality. Probing three adjacent slots usually stays inside one cache line, while following a chain pointer almost never does - so at moderate load an open-addressed table beats a chained one on real hardware even at equal comparison counts. The cost is clustering: with linear probing, a run of occupied slots catches every key hashing into it, so long runs grow longer.
Reach for it when memory and cache misses matter and you can resize early - performance collapses as α approaches 1, so real implementations rebuild around α = 0.5 to 0.7. CPython's dict and Rust's HashMap are both open-addressed. This module lets you switch the probe rule live: linear i + s, quadratic i + s², or double hashing i + s times h2(k).
Step by step
- Start with m = 11 empty slots and linear probing. Insert 5: h(5) = 5 mod 11 = 5, slot 5 is free - placed on the first probe.
- Insert 16: 16 mod 11 = 5 as well, but slot 5 holds 5. Probe the next slot: 6 is free, so 16 settles there after two probes.
- Insert 27: again home slot 5. The probe walks 5, then 6, then 7 - three probes - and slots 5 through 7 are now a solid run.
- Look up 27: replay the same walk. Slot 5 holds 5, slot 6 holds 16, slot 7 matches - the sequence retraces the insertion exactly.
- Delete 16: slot 6 becomes a tombstone, not an empty slot. Blanking it would stop every future probe at slot 6 and strand 27.
- Look up 27 once more: slot 5 misses, slot 6 is a tombstone so the probe continues, slot 7 hits. The tombstone kept the chain intact.
Complexity
| Average time | O(1) below α ≈ 0.7 |
|---|---|
| Worst case time | O(n) |
| Space | O(m) |
Load factor cannot exceed 1, and performance collapses well before it.
Reference implementation
Python
class OpenAddressed:
TOMBSTONE = object()
def __init__(self, m=11):
self.slots = [None] * m
def _probe(self, key, step):
m = len(self.slots)
return (key + step) % m # linear probing
# quadratic: (key + step * step) % m
# double: (key + step * (1 + key % (m - 1))) % m
def put(self, key):
for step in range(len(self.slots)):
j = self._probe(key, step)
if self.slots[j] is None or self.slots[j] is self.TOMBSTONE:
self.slots[j] = key
return
if self.slots[j] == key:
return
raise RuntimeError("table full")
def delete(self, key):
for step in range(len(self.slots)):
j = self._probe(key, step)
if self.slots[j] is None:
return False # a real gap: key absent
if self.slots[j] == key:
self.slots[j] = self.TOMBSTONE # NOT None - see insights
return True
return FalseJavaScript
const TOMBSTONE = Symbol("deleted");
class OpenAddressed {
constructor(m = 11) { this.slots = new Array(m).fill(null); }
#probe(key, step) {
const m = this.slots.length;
return (key + step) % m; // linear probing
}
put(key) {
for (let s = 0; s < this.slots.length; s++) {
const j = this.#probe(key, s);
const cur = this.slots[j];
if (cur === null || cur === TOMBSTONE) { this.slots[j] = key; return true; }
if (cur === key) return true;
}
return false; // table full
}
}Worth noticing
Everything lives in the table itself
No chains, no per-entry allocation. That makes open addressing dramatically more cache-friendly than chaining - probing a few adjacent slots usually stays inside one cache line, where following a chain pointer almost never does.
Linear probing creates clusters, and clusters grow
Insert several colliding keys with linear probing and watch a run of occupied slots form. Any key hashing anywhere into that run extends it, so long runs get longer - primary clustering, and it is why quadratic and double hashing exist.
Deletion needs a tombstone, not an empty slot
A probe stops at the first empty slot. Blank out a deleted entry in the middle of a probe chain and every key beyond it becomes unreachable. Marking it 'deleted but keep probing' is the fix - and the reason heavily-churned open-addressed tables must eventually be rebuilt.
The table can genuinely fill up
Load factor cannot exceed 1, and performance collapses well before that. Most implementations resize at around α = 0.5 to 0.7 - much lower than chaining, which tolerates α > 1 comfortably.
Common pitfalls
- Deleting by clearing the slot. A lookup stops at the first never-used slot, so emptying one mid-chain makes every key inserted past it silently unreachable - the classic open-addressing bug.
- Letting tombstones pile up. Probes must walk through them, so a table with heavy churn slows down even when nearly empty - periodically rebuild to purge them.
- Running near full. At α = 0.9 linear probing degenerates into long scans; open-addressed tables should resize around α = 0.5 to 0.7, far earlier than chained ones.
- Quadratic probing on a non-prime m. The s² offsets revisit slots and can miss free ones entirely - the guarantee that early probes are all distinct requires a prime table size.
- A secondary hash that can return 0. In double hashing a zero step never advances; this module uses h2(k) = 1 + (k mod (m - 1)) so the step is always at least 1.
Where it is used
- CPython's dict - every attribute lookup and keyword argument in Python goes through an open-addressed table.
- Swiss tables - Abseil's flat_hash_map and Rust's HashMap - use open addressing with SIMD probing for cache speed.
- An interview follow-up favourite: implement delete correctly, which is really a question about tombstones.
- Embedded and high-performance code where one heap allocation per entry is unacceptable.
Frequently asked questions
What is the time and space complexity of open addressing?
Average O(1) while the load factor stays below about 0.7, degrading to O(n) in the worst case as the table approaches full. Space is O(m) - a single flat array of slots with no per-entry pointers, which is exactly why it is so cache-friendly.
What is primary clustering in linear probing?
Occupied slots form contiguous runs, and any key hashing anywhere inside a run must walk to its end - which extends it. Long runs therefore grow faster than short ones. Quadratic probing and double hashing spread colliding keys apart precisely to stop runs from forming.
What is a tombstone in a hash table?
A marker for a deleted slot that probes treat as occupied but reusable. Lookups probe past it, because the key they want may have been inserted beyond it before the deletion; inserts may claim it. Without tombstones, deletion would cut probe chains and strand keys.
Which probe sequence should I use - linear, quadratic, or double hashing?
Linear is simplest and most cache-friendly but clusters; quadratic breaks up primary clustering with little extra work; double hashing gives the best spread at the cost of a second hash per probe. Modern tables mostly pick linear and control clustering by resizing early.