Closed Hash Tables

Open addressing: every key lives in the table itself, probing forward until it finds a free slot.

Also called open addressing. "Closed hashing" means keys stay inside the table array — the opposite of the "open hashing" on the chaining page, despite how the names read.

Lookup: O(1) avg

α ≤ 1 always

Cache friendly

Needs tombstones

Probe strategy

probe(k, i) = (h(k) + i) mod m — simple and cache friendly, but prone to primary clustering.

Keys to insert

Then delete

Then look up

Speed: 900ms

Step 1 of 0Phase: start

Key

—

Home

—

Probe i

0.00

Table — every key lives inside the array

∅

probingplaced / foundtombstone (✕)empty (∅)

Current Step

Click Play to begin

Complexity

Search avg:O(1/(1−α))

Search worst:O(n)

Space:O(m)

Max α:1.0

Key Concepts

No pointers: one contiguous array, cache friendly
Tombstones: a delete marks, it never clears
Clustering: linear probing merges runs of filled slots
Resize near α = 0.7 — cost explodes as α → 1

Knowledge Check

Question 1 of 3

Why can a closed hash table never hold more keys than it has slots?

Indexing

Hashing your keys…

DSAverse

Closed Hash Tables

Table — every key lives inside the array

Current Step

Complexity

Key Concepts

Knowledge Check

Closed Hash Tables

Table — every key lives inside the array

Current Step

Complexity

Key Concepts

Knowledge Check