Intuition The one-line ideaA hash table maps keys to an array index. But two different keys can land on the same index (a collision ). Chaining says: "Fine — at each index, keep a linked list of all keys that hashed there." Lookups walk that small list. As long as the lists stay short, everything is fast.
Definition The collision problemA hash function h h h U U U m m m h : U → { 0 , 1 , … , m − 1 } h: U \to \{0,1,\dots,m-1\} h : U → { 0 , 1 , … , m − 1 } ∣ U ∣ ≫ m |U| \gg m ∣ U ∣ ≫ m pigeonhole principle at least two keys must share a slot. We cannot avoid collisions; we can only handle them.
WHY chaining specifically? Two key strategies exist:
Open addressing — store everything inside the array, probe for the next free slot.Chaining — store a separate container (a linked list) per slot.
Chaining is chosen when we want: simple deletion, graceful behavior when the table gets crowded, and no clustering headaches.
Definition Separate chainingThe table is an array T[0..m-1]. Each T[i] is the head pointer of a linked list (a "chain" / "bucket") holding every stored key k k k h ( k ) = i h(k)=i h ( k ) = i
HOW the operations work (let n n n
Op
What it does
Cost
insert(k)compute h ( k ) h(k) h ( k ) T [ h ( k ) ] T[h(k)] T [ h ( k )]
O ( 1 ) O(1) O ( 1 )
search(k)compute h ( k ) h(k) h ( k ) T [ h ( k ) ] T[h(k)] T [ h ( k )]
O ( list length ) O(\text{list length}) O ( list length )
delete(k)search, then unlink the node
O ( list length ) O(\text{list length}) O ( list length )
Insert is O ( 1 ) O(1) O ( 1 ) O ( len ) O(\text{len}) O ( len )
α = n m \alpha = \frac{n}{m} α = m n n n n m m m average number of keys per bucket .
Intuition What this means in plain wordsThe "1 1 1 α \alpha α α \alpha α If you keep α \alpha α ≤ 0.75 \le 0.75 ≤ 0.75 O ( 1 ) O(1) O ( 1 ) That is the whole game.
Worked example Reading off costs
n = 100 , m = 100 ⇒ α = 1 n=100, m=100 \Rightarrow \alpha=1 n = 100 , m = 100 ⇒ α = 1 n = 1000 , m = 100 ⇒ α = 10 n=1000, m=100 \Rightarrow \alpha=10 n = 1000 , m = 100 ⇒ α = 10 n = 100 , m = 1000 ⇒ α = 0.1 n=100, m=1000 \Rightarrow \alpha=0.1 n = 100 , m = 1000 ⇒ α = 0.1
Why this step? It shows α \alpha α tunable knob trading speed (small α \alpha α memory (large α \alpha α
If we never grow m m m n n n α = n / m \alpha = n/m α = n / m O ( 1 ) O(1) O ( 1 ) O ( n ) O(n) O ( n ) keep α \alpha α m m m
Pick a threshold (e.g. α m a x = 0.75 \alpha_{max}=0.75 α ma x = 0.75 insert would push α \alpha α
Allocate a new array of size m ′ = 2 m m' = 2m m ′ = 2 m
Rehash : recompute h ′ ( k ) = ( hash ( k ) m o d m ′ ) h'(k) = (\text{hash}(k) \bmod m') h ′ ( k ) = ( hash ( k ) mod m ′ ) every key and re-insert it.Discard the old array.
WHY double, not add a constant? Doubling makes resizes exponentially rare .
Worked example A resize in actionTable m = 4 m=4 m = 4 α m a x = 0.75 ⇒ \alpha_{max}=0.75 \Rightarrow α ma x = 0.75 ⇒ n > 3 n>3 n > 3 h ( k ) = k m o d 4 h(k)=k\bmod 4 h ( k ) = k mod 4
insert 5 → slot 1; 9 → slot 1 (chain: 9→5); 13 → slot 1 (chain 13→9→5); n = 3 n=3 n = 3 α = 0.75 \alpha=0.75 α = 0.75
insert 1 → would make n = 4 n=4 n = 4 α = 1 > 0.75 \alpha=1>0.75 α = 1 > 0.75 Resize to m = 8 m=8 m = 8 Now h ( k ) = k m o d 8 h(k)=k\bmod 8 h ( k ) = k mod 8
5→5, 9→1, 13→5 (chain 13→5), 1→1 (chain 1→9).
Why this step? Notice the long chain at slot 1 got split across slots 1 and 5 — that's exactly how resizing flattens the chains.
Common mistake "Worst case isO ( 1 ) O(1) O ( 1 ) Why it feels right: marketing says "hash tables are O ( 1 ) O(1) O ( 1 ) Reality: that's average/expected under uniform hashing. If an adversary (or a bad hash) sends every key to one bucket, all n n n worst case O ( n ) O(n) O ( n ) per operation. Fix: say "expected O ( 1 + α ) O(1+\alpha) O ( 1 + α ) O ( n ) O(n) O ( n )
Common mistake "Just makem m m Why it feels right: big m m m α \alpha α Reality: you waste O ( m ) O(m) O ( m ) Fix: keep α \alpha α 0.75 0.75 0.75
Common mistake "Resizing is cheap, so do it every insert by adding 10 slots."Why it feels right: keeps α \alpha α Reality: rehashing is O ( m ) O(m) O ( m ) Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) Fix: grow multiplicatively (double), giving O ( 1 ) O(1) O ( 1 )
Common mistake "Load factor of chaining must be≤ 1 \le 1 ≤ 1 Why it feels right: open addressing dies at α = 1 \alpha=1 α = 1 Reality: chaining works fine at α > 1 \alpha>1 α > 1 Fix: the α ≤ 1 \alpha\le1 α ≤ 1 open addressing , not chaining.
Recall Predict before revealing (Forecast-then-Verify)
Define load factor and state expected search cost. α = n / m \alpha=n/m α = n / m O ( 1 + α ) O(1+\alpha) O ( 1 + α )
Why double m m m O ( 1 ) O(1) O ( 1 ) O ( n ) O(n) O ( n )
What's the worst case for a chained lookup and when? O ( n ) O(n) O ( n )
Does chaining break at α = 1 \alpha=1 α = 1
Recall Feynman: explain to a 12-year-oldImagine a wall of mailboxes numbered 0–9. A rule (the hash) tells each letter which box it belongs to. Sometimes two letters go to the same box — so inside each box you keep a little string of letters clipped together (the linked list). To find a letter, go to its box and flip through that small string. If boxes get too crowded (too many letters per box on average — that's the load factor ), you buy a bigger wall with twice as many boxes and re-sort all the letters so each box is light again. Light boxes = fast finding.
Mnemonic Remember the knobs"CALR" — C ollisions → A lpha = n/m → L ist length sets cost (1 + α 1+\alpha 1 + α R esize (double) to reset alpha. "Chains Always Like Resizing."
Hash Functions — quality of h h h Open Addressing — the alternative (linear/quadratic probing, dies at α = 1 \alpha=1 α = 1 Amortized Analysis — justifies O ( 1 ) O(1) O ( 1 ) O ( m ) O(m) O ( m ) Dynamic Arrays — same doubling trick for amortized O ( 1 ) O(1) O ( 1 ) Pigeonhole Principle — why collisions are unavoidable.Linked Lists — the bucket data structure itself.
What is the load factor of a hash table? α = n / m \alpha = n/m α = n / m , the average number of keys per bucket (
n n n keys,
m m m buckets).
Expected cost of search in a chained hash table? O ( 1 + α ) O(1+\alpha) O ( 1 + α ) under simple uniform hashing.
Worst-case cost of search in a chained hash table and when does it happen? O ( n ) O(n) O ( n ) , when every key hashes to the same bucket (one long chain).
Why double the table size on resize instead of adding a fixed number of slots? Doubling makes total rehash work a geometric series
≤ 2 n \le 2n ≤ 2 n , giving
O ( 1 ) O(1) O ( 1 ) amortized insert; constant growth gives
Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) total →
Θ ( n ) \Theta(n) Θ ( n ) per insert.
What does rehashing involve? Allocating a larger array (e.g.
2 m 2m 2 m ) and recomputing
h ( k ) m o d m ′ h(k)\bmod m' h ( k ) mod m ′ for every key, re-inserting all of them.
Does chaining stop working at α = 1 \alpha=1 α = 1 No — only open addressing fills up at
α = 1 \alpha=1 α = 1 ; chaining keeps working and just slows down linearly in
α \alpha α .
Why is insertion (without duplicate check) O ( 1 ) O(1) O ( 1 ) You compute the hash and prepend the node at the head of the bucket's list.
What assumption gives expected O ( 1 + α ) O(1+\alpha) O ( 1 + α ) Simple Uniform Hashing: each key is equally and independently likely to hash to any of the
m m m slots.
Typical resize trigger threshold? When
α \alpha α exceeds a chosen max like
0.75 0.75 0.75 .
Expected length of any single bucket? n ⋅ 1 m = α n \cdot \frac{1}{m} = \alpha n ⋅ m 1 = α .
Hash function h maps keys to slots
Load factor a equals n over m
Expected cost O of 1 plus a
Intuition Hinglish mein samjhoDekho, hash table ek array hota hai jisme ek hash function key ko ek index pe map karta hai. Problem ye hai ki do alag keys kabhi-kabhi same index pe aa jaati hain — isko collision kehte hain, aur ye unavoidable hai (pigeonhole principle). Chaining ka simple jugaad: har bucket (index) pe ek linked list rakho. Jo bhi keys us index pe hash hoti hain, sab us list me clip ho jaati hain. Search karte time bas us chhoti si list ko scan karo.
Sabse important number hai load factor α = n / m \alpha = n/m α = n / m O ( 1 + α ) O(1+\alpha) O ( 1 + α ) α \alpha α α \alpha α O ( 1 ) O(1) O ( 1 ) O ( n ) O(n) O ( n )
Jaise-jaise keys badhti hain, n n n α \alpha α resizing (rehashing) karte hain: jab α \alpha α double kar do aur saari keys naye m m m 1 + 2 + 4 + ⋯ < 2 n 1+2+4+\dots < 2n 1 + 2 + 4 + ⋯ < 2 n amortized O ( 1 ) O(1) O ( 1 ) rehta hai. Agar tum constant (jaise +10) add karte to total kaam Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) collisions → alpha → chain length → resize .
