Load factor — when to resize, rehashing cost

3.3.6 · Coding › Hashing

Load factor KYA hota hai?

Load factor woh ek number hai jo control karta hai ki hash table kitna fast hai. Chhota $α$ = fast hai lekin memory waste hoti hai. Bada $α$ = memory bachti hai lekin slow ho jaata hai.

$α$ speed ko KYU control karta hai?

Chaining: har operation mein expected work

Maano simple uniform hashing (har key equally likely hai kisi bhi bucket mein jaane ke liye, independently). Jo chain tum scan karte ho uski expected length average chain length hai, jo exactly $α$ hai.

$E [cost of search] = hash + index 1 + scan chain α = O (1 + α)$

Yeh step kyun? $n$ keys mein se har ek kisi bucket mein hai. Kisi given key ke tumhare bucket mein hone ki probability $1/ m$ hai. Expected number of sharing = $(n) \cdot \frac{1}{m} = α$ . Toh jo chain tum walk karte ho uski expected length $α$ hai.

➡️ Agar hum $α = O (1)$ rakhen (ek chhota constant, jaise $\leq 0.75$ ), toh $O (1 + α) = O (1)$ . Yahi poora reason hai ki hum resize karte hain.

Open addressing: expected probes

Uniform hashing aur $α < 1$ ke saath, unsuccessful search ke liye expected probes ki number ek geometric-style argument se nikali jaati hai:

$E [probes] \leq \frac{1}{1 - α}$

Worked example Numbers plug karo — cliff feel karo

$α$	$1/ (1 - α)$ probes
0.5	2
0.75	4
0.9	10
0.99	100

Yeh kyun matter karta hai: cost ~0.7 tak theek rehti hai, phir boom ho jaati hai. Isliye open-addressing tables $α \approx 0.7$ pe resize karti hain, jabki chaining $α \approx 1$ tak tolerate kar sakti hai.

$1/ (1 - α)$ ko scratch se derive karna (open addressing)

Resizing KAISE kaam karta hai (aur pehle expensive kyun hai phir sasta kyun)

$n$ elements ka ek rehash $Θ (n)$ cost karta hai. Yeh scary lagta hai — ek insert kabhi-kabhi linear time leta hai! Toh phir table ko $O (1)$ per operation kyun maana jaata hai?

Figure — Load factor — when to resize, rehashing cost

Amortized cost — doubling trick, derived

Sab kuch milake: resize rule

Worked example Worked example — total work count karna

Size 1 se start hone wali table mein 8 keys insert karo, $α_{m a x} = 1$ pe double karo.

Insert #	size before	rehash?	elements moved
1	1	—	0
2	1→2	yes	1
3	2→4	yes	2
4	4	—	0
5	4→8	yes	4
6,7,8	8	—	0

Total moves $= 1 + 2 + 4 = 7 \approx 2 n$ . Har insert khud $O (1)$ hai. Yeh step kyun? Dikhata hai ki rehash cost ( $\leq 2 n$ total) $n$ inserts mein amortize ho jaati hai → har ek $O (1)$ .

Flashcards

Hash table ka load factor kya hota hai?

α = n / m

, stored keys

n

aur buckets

m

ka ratio.

Chained hash table mein expected search cost (uniform hashing)?

O (1 + α)

Open addressing mein unsuccessful search ke liye expected probes?

\leq \frac{1}{1 - α}

Open addressing chaining (~1.0) se pehle (~0.7) resize kyun karta hai?

Kyunki

1/ (1 - α)

sharply blow up hota hai jaise

α \to 1

, jabki chaining cost sirf linearly badhti hai

1 + α

ki tarah.

n

elements ke single rehash ki cost?

Θ (n)

— har key ko naye size ke modulo re-insert karna padta hai.

Resize ke dauran hum sirf buckets copy kyun nahi kar sakte?

Bucket index

h (k) mod m

hai;

m

change karne se index change ho jaata hai, isliye keys ko re-place karna padta hai.

Table doubling ke saath per insert amortized cost?

O (1)

;

n

inserts pe total move work

\leq 2 n

hai.

Additive growth (jaise +100) kharaab performance kyun deta hai?

Har constant interval pe rehash → total work

Θ (n^{2})

→ amortized

O (n)

per insert.

Doubling ke amortized bound ke peeche geometric series?

1 + 2 + 4 + \dots + n = 2 n - 1

Alag grow/shrink thresholds (hysteresis) kyun use karte hain?

Grow↔shrink thrashing rokne ke liye jab ops ek single boundary ke paas alternate karti hain.

Agar 1500 keys expect karo

α \leq 0.75

pe, minimum

m

m \geq 1500/0.75 = 2000

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

Socho ek coat-check room jisme hooks hain. "Load factor" yeh hai ki kitne coats har hook pe hain. Kam coats ho toh instant hai — ek hook, ek coat. Jaise-jaise bharta hai, ek hi hook pe kai coats latke rehte hain aur tumhe flip karna padta hai, slower hota jaata hai. Toh jab room teen-chauthaayi bhara hota hai, tum sab kuch double hooks wale room mein shift kar dete ho. Sabko move karna ek badi mehnat hai — lekin tum yeh kabhi-kabhi hi karte ho, aur kyunki har naya room pichhle se double hai, yeh kaam almost kabhi nahi karna padta. Saare coats jo tumne kabhi bhi latkaaye, unke upar spread karo toh yeh mehnat almost kuch nahi karti per coat. Yeh "average mein almost kuch nahi" hi hai jo hum amortized $O (1)$ kehte hain.

Connections

Hashing — parent concept; hashing fast tab hi hoti hai jab $α$ bounded rahe.
Separate Chaining — $α ≳ 1$ tolerate karta hai; cost $O (1 + α)$ .
Open Addressing — $α < 1$ chahiye; cost $1/ (1 - α)$ .
Amortized Analysis — aggregate/accounting method jo $O (1)$ inserts prove karta hai.
Dynamic Arrays — same doubling trick; ArrayList/vector identically grow karte hain.
Hash Functions — uniform hashing assumption saare $α$ formulas ko underpin karta hai.