Hashing | Chaining and Open Addressing | O(1) Average
Standard Undergraduate
Section 1 -- Interactive Simulation
Speed:
0
Operations
0
Comparisons
0/0
Step
16
n
n: 16
INSERT(key, value): h = hash(key) % m; table[h] = (key,val)
SEARCH(key): h = hash(key) % m; check table[h]
DELETE(key): h = hash(key) % m; mark as deleted
Division method: h(k) = k mod m
Multiplication: h(k) = floor(m * (k*A mod 1)), A~0.618
Load factor: alpha = n / m (n=keys, m=buckets)
Chaining: bucket holds linked list of colliding keys
Open addressing: probe sequence for collisions
Section 2 -- The Idea, Step by Step
Imagine a coat-check at a theatre. Instead of searching every hook for your coat, the attendant writes a number on your ticket and hangs the coat on exactly that hook. To get it back you don't hunt — you read the number and walk straight to one hook. A hash table is that trick for data: a rule turns each key into a shelf number, so you store and find things in essentially one step instead of scanning everything.
The rule that picks the shelf. The shelf number comes from a hash function $h(k)$. The simplest one is the division method, $h(k)=k \bmod m$, where $m$ is the number of buckets (shelves). Say $m=10$ buckets and you want to store the key $47$. Then $47 \bmod 10 = 7$, so $47$ lives in bucket 7. Later, to look it up, you recompute $47 \bmod 10 = 7$ and go directly to bucket 7. One arithmetic step, no searching. That is why a hash table feels instant: the key tells you where it is.
When two keys want the same shelf. With more keys than buckets, two keys eventually land on the same number — a collision (unavoidable by the pigeonhole principle once $n>m$). Two cures: chaining keeps a little linked list at each bucket so both keys hang there together; open addressing sends the second key to probe the next free slot. Either way the lookup still starts at the hashed bucket and only does a tiny bit of extra walking.
How full is too full. The single number that controls speed is the load factor $\alpha = n/m$ — keys per bucket. For chaining the average lookup costs about $1+\alpha$ comparisons; for open addressing an unsuccessful search probes about $\dfrac{1}{1-\alpha}$ times. Plug in $\alpha=0.9$ and that's $1/(1-0.9)=10$ probes; at $\alpha=0.99$ it explodes to $100$. So real tables keep $\alpha$ below about $0.7$, and when it climbs too high they resize: allocate a table twice as big and rehash everything, an $O(n)$ event that averages out to $O(1)$ per insert. Universal (randomised) hashing keeps things fast even against adversarial keys.
Try this in the sim above. Press Next repeatedly and watch the highlighted pseudocode line move through the INSERT / SEARCH steps while the Operations and Comparisons counters tick up. Drag the n slider higher: with the bucket count fixed, more keys means a larger load factor — notice the work counters grow. Then switch the preset between Random, Sorted, and Reverse and press Reset to see how the order of incoming keys changes the trace.
Section 3 -- Complexity Analysis
Symbol
Meaning
n
Input size
T(n)
Time complexity function
h
Height or depth of structure
k
Key or rank parameter
W(n)
Worst-case complexity
A(n)
Average-case complexity
Step 1 -- Hash Function. Maps key to index 0..m-1. Division method: h(k) = k mod m (avoid m=power of 2, prefer prime). Multiplication: h(k) = floor(m*(k*A mod 1)) where A~(sqrt(5)-1)/2. Universal hashing: random from a family, O(1) expected collisions.
Step 2 -- Chaining. Each slot holds a linked list. INSERT: prepend to list O(1). SEARCH: traverse list. Average search: O(1 + alpha) where alpha = n/m (load factor). Worst case: all n keys in same bucket O(n).
Step 3 -- Open Addressing. All elements stored in table itself. On collision: probe next slot. Linear probing: h(k,i)=(h(k)+i) mod m. Quadratic: h(k,i)=(h(k)+c1*i+c2*i^2) mod m. Double hashing: h(k,i)=(h1(k)+i*h2(k)) mod m. Load factor must be < 1.
Step 4 -- Load Factor and Performance. Chaining: E[search] = 1 + alpha/2. Open addressing: E[probes] = 1/(1-alpha). At alpha=0.5: 2 probes. At alpha=0.9: 10 probes. At alpha=0.99: 100 probes. Key insight: performance degrades rapidly above alpha~0.7.
Step 5 -- Dynamic Resizing. When alpha exceeds threshold (0.75 typically): allocate new table 2x size, rehash all elements. Cost: O(n) one-time. Amortized over n/2 insertions since last resize: O(1) per insert. Java HashMap default load factor: 0.75.
Step 6 -- Worst Case O(n). Worst case search O(n) when all keys hash to same bucket (adversarial keys or bad hash). Universal hashing or randomized hash functions prevent adversarial attacks. Java switched to tree buckets (red-black trees) for chains exceeding 8 elements (HashMap TREEIFY_THRESHOLD).
Section 4 -- FAQ
How does a hash function work? concept+
Hash function maps arbitrary keys to fixed-range indices 0..m-1. Good hash: uniform distribution (each index equally likely), fast to compute, deterministic. Bad hash concentrates keys in few buckets, degrading to O(n).
What is a collision and how is it resolved? concept+
Collision: two distinct keys hash to same index. Inevitable by pigeonhole principle when n>m. Chaining: store both in a linked list at that index. Open addressing: probe other indices until an empty slot is found.
Where are hash tables used in real systems? applied+
Database join operations (hash join). Compiler symbol tables. Python dict, Java HashMap, C++ unordered_map. DNS caches. Bloom filters (space-efficient hash tables). Distributed hash tables (Chord, Kademlia for peer-to-peer networks).
Why is O(1) average but O(n) worst case? complex+
With random keys and good hash: expected chain length = alpha = n/m = O(1) for m = O(n). But adversarial keys can all map to same bucket. Defense: universal hashing (random hash from a family guarantees O(1) expected regardless of input). Java's HashMap uses randomized hash since Java 8.
Why does performance degrade at high load factor? nonobv+
Open addressing with linear probing: clusters form (primary clustering). Once a cluster starts, more insertions hit the cluster, making it grow faster. At alpha=0.9, expected probes = 1/(1-0.9) = 10. At alpha=0.99: 100 probes. Keep alpha < 0.7 for open addressing.
What is a perfect hash function? deep+
Perfect hash: no collisions for a specific set of n keys. Minimal perfect hash: maps n keys to exactly n indices, no collisions, O(1) lookup, no space waste. Used for static data (compiler keywords, network protocols). FKS scheme (Fredman-Komlos-Szemeredi): O(n) space, O(1) worst-case lookup, O(n) expected construction.
Section 5 -- Common Misconceptions
Conceptual Misconceptions
X Hash tables guarantee O(1) worst case.
O Hash tables are O(1) AVERAGE, O(n) worst case. Worst case occurs with all keys in one bucket. Universal hashing makes O(1) expected regardless of input.
X Any hash function is fine for a hash table.
O Bad hash functions (e.g., h(k)=k%8 for even keys) concentrate all keys in few buckets. Use prime modulus, multiplication method, or cryptographic hash for security-sensitive applications.
X Open addressing and chaining have same performance.
O At high load (alpha > 0.7), open addressing degrades severely due to clustering. Chaining handles high load better but requires extra memory for pointers.
Implementation Errors
X Using a mutable object as a hash key.
O Mutable keys whose hash changes after insertion will not be found. Python prevents this by only allowing immutable objects as dict keys.
X Forgetting tombstone markers in open addressing delete.
O Deleting by just clearing a slot breaks probe chains -- subsequent searches stop at the empty slot and miss elements beyond it. Mark deleted slots with a tombstone sentinel.
X Assuming n/m = O(1) without enforcing load factor.
O Without dynamic resizing, as n grows, alpha grows and performance degrades. Always trigger resize at alpha threshold (typically 0.75).