Chaining — linked lists in buckets, load factor, resizing

3.3.3 · Coding › Hashing

WHY chaining exist karti hai?

WHY specifically chaining? Do key strategies hain:

Open addressing — sab kuch array ke andar store karo, next free slot ke liye probe karo.
Chaining — har slot ke liye ek alag container (ek linked list) rakho.

Chaining tab choose ki jaati hai jab hum chahte hain: simple deletion, table ke crowded hone par graceful behavior, aur koi clustering ka jhanjhat nahi.

WHAT hai yeh structure?

Figure — Chaining — linked lists in buckets, load factor, resizing

HOW operations kaam karte hain (maano $n$ = stored keys ki number):

Op	Kya karta hai	Cost
`insert(k)`	$h (k)$ compute karo, list $T [h (k)]$ mein prepend karo	$O (1)$
`search(k)`	$h (k)$ compute karo, list $T [h (k)]$ scan karo	$O (list length)$
`delete(k)`	search karo, phir node ko unlink karo	$O (list length)$

Insert $O (1)$ hai kyunki hum head pe prepend karte hain (duplicates allow ho toh check ki zaroorat nahi, ya $O (len)$ agar duplicates reject karne hon).

Load Factor — sabse important number

Expected search cost derive karna (scratch se)

Resizing (Rehashing) — $α$ ko check mein rakhna

WHY double karo, constant add nahi? Doubling resizes ko exponentially rare banata hai.

Common Mistakes (Steel-manned)

Active Recall

Recall Reveal karne se pehle predict karo (Forecast-then-Verify)

Load factor define karo aur expected search cost batao.
→ $α = n / m$ ; expected $O (1 + α)$ .
$m$ mein constant add karne ki jagah double kyun karo?
→ Geometric series $O (1)$ amortized deti hai vs $O (n)$ .
Chained lookup ka worst case kya hai aur kab hota hai?
→ $O (n)$ , jab saari keys ek hi chain mein collide ho jaayein.
Kya chaining $α = 1$ pe break ho jaati hai?
→ Nahi, sirf open addressing karta hai; chaining gracefully degrade hoti hai.

Recall Feynman: ek 12-saal ke bachche ko explain karo

Socho ek diwar pe mailboxes hain jinhein 0–9 number diye gaye hain. Ek rule (hash) har letter ko batata hai ki woh kis box mein jaayega. Kabhi kabhi do letters ek hi box mein jaate hain — toh har box ke andar tum ek chhoti letters ki string clip karke rakhte ho (linked list). Koi letter dhundne ke liye, us ke box mein jao aur woh chhoti string flip karo. Agar boxes bahut crowded ho jaayein (average mein bahut zyada letters per box — yahi load factor hai), toh tum double boxes wali badi diwar khareedte ho aur saari letters phir se sort karte ho taaki har box halka ho. Halke boxes = fast dhundna.

Connections

Hash Functions — $h$ ki quality decide karti hai ki uniform-hashing assumption hold hoti hai ya nahi.
Open Addressing — alternative (linear/quadratic probing, $α = 1$ pe mar jaata hai).
Amortized Analysis — $O (1)$ inserts ko justify karta hai occasional $O (m)$ resizes ke bawajood.
Dynamic Arrays — amortized $O (1)$ append ke liye same doubling trick.
Pigeonhole Principle — kyun collisions unavoidable hain.
Linked Lists — bucket data structure khud.

Hash table ka load factor kya hota hai?

α = n / m

, per bucket average keys ki number (

n

keys,

m

buckets).

Chained hash table mein search ki expected cost?

Simple uniform hashing ke under

O (1 + α)

Chained hash table mein search ki worst-case cost aur yeh kab hoti hai?

O (n)

, jab saari keys ek hi bucket mein hash ho jaayein (ek lambi chain).

Resize pe fixed number of slots add karne ki jagah table size double kyun karo?

Doubling total rehash work ko ek geometric series

\leq 2 n

banata hai, jo

O (1)

amortized insert deta hai; constant growth

Θ (n^{2})

total deta hai →

Θ (n)

per insert.

Rehashing mein kya hota hai?

Ek bada array (e.g.

2 m

) allocate karna aur har key ke liye

h (k) mod m^{'}

recompute karna, unhe sab dobara insert karna.

Kya chaining

α = 1

pe kaam karna band kar deti hai?

Nahi — sirf open addressing

α = 1

pe fill up hoti hai; chaining kaam karti rehti hai aur sirf

α

mein linearly slow hoti hai.

Chaining mein insertion (duplicate check ke bina)

O (1)

kyun hai?

Tum hash compute karte ho aur bucket ki list ke head pe node prepend karte ho.

Expected

O (1 + α)

kaunsa assumption deta hai?

Simple Uniform Hashing: har key equally aur independently

m

slots mein se kisi pe bhi hash ho sakti hai.

Resize trigger karne ki typical threshold?

Jab

α

ek chosen max jaise

0.75

se exceed kare.

Kisi bhi single bucket ki expected length?

n \cdot \frac{1}{m} = α