Assume simple uniform hashing (each key equally likely to land in any bucket, independently). The expected length of the chain you must scan is the average chain length, which is exactly α.
E[cost of search]=hash + index1+scan chainα=O(1+α)
Why this step? Each of the n keys is in some bucket. Probability a given key shares your bucket is 1/m. Expected number sharing = (n)⋅m1=α. So the chain you walk has expected length α.
➡️ If we keep α=O(1) (a small constant, say ≤0.75), then O(1+α)=O(1). This is the whole reason we resize.
A single rehash of n elements costs Θ(n). That feels scary — one insert occasionally takes linear time! So why is the table still considered O(1) per operation?
Expected search cost in a chained hash table (uniform hashing)?
O(1+α).
Expected probes for an unsuccessful search in open addressing?
≤1−α1.
Why does open addressing resize earlier (~0.7) than chaining (~1.0)?
Because 1/(1−α) blows up sharply as α→1, whereas chaining cost grows only linearly as 1+α.
Cost of a single rehash of n elements?
Θ(n) — every key must be re-inserted modulo the new size.
Why can't we just copy buckets during a resize?
Bucket index is h(k)modm; changing m changes the index, so keys must be re-placed.
Amortized cost per insert with table doubling?
O(1); total move work over n inserts is ≤2n.
Why does additive growth (e.g. +100) give bad performance?
Rehashes every constant interval → total work Θ(n2) → amortized O(n) per insert.
Geometric series behind doubling's amortized bound?
1+2+4+⋯+n=2n−1.
Why use separated grow/shrink thresholds (hysteresis)?
To prevent grow↔shrink thrashing when ops alternate near a single boundary.
If you expect 1500 keys at α≤0.75, minimum m?
m≥1500/0.75=2000.
Recall Feynman: explain it to a 12-year-old
Imagine a coat-check room with hooks. The "load factor" is how many coats per hook. With few coats it's instant — one hook, one coat. As it fills, several coats hang on the same hook and you must flip through them, getting slower. So when the room is about three-quarters full, you move everything to a room with twice as many hooks. Moving everyone is a big chore — but you only do it occasionally, and because each new room is double the last, you almost never do it. Spread over all the coats you ever hang, that chore costs almost nothing per coat. That "almost nothing on average" is what we call amortized O(1).
Dekho, load factorα=n/m ka matlab hai table kitna bhara hua hai — n keys aur m buckets. Jab table khaali hota hai, hashing ekdum fast hota hai, O(1). Lekin jaise-jaise keys badhti hain, collisions badhte hain aur har operation slow hone lagta hai. Chaining mein cost 1+α hoti hai (linear, gentle), par open addressing mein cost 1−α1 hoti hai — yeh α=0.9 par 10 probes, aur 0.99 par 100 probes tak chala jaata hai. Isliye open addressing wale tables jaldi (~0.7) resize karte hain, chaining wale thoda late (~1.0).
Resize / rehashing ka matlab: naya bada array banao (usually double size), aur saari purani keys ko nayi size ke modulo se phir se daalo. Bucket ka index h(k)modm hota hai, aur m badal gaya toh index bhi badal jaata hai — isliye seedha copy nahi kar sakte, har key dobara place karni padti hai. Ek rehash ka cost Θ(n) hai — sun ke darr lagta hai!
Par yahaan asli jaadu hai amortized analysis. Kyunki hum size double karte hain, rehash bahut rarely hota hai. n inserts mein total move-work 1+2+4+⋯+n≈2n hi hota hai (geometric series). Toh per insert average cost constant, yaani amortized O(1). Yaad rakho: double karo, +100 mat karo. Agar fixed amount se grow karoge toh har thodi der mein rehash hoga aur total kaam O(n2) ho jaayega — bilkul slow. Bas yeh do cheez samajh lo: α control karta hai speed, aur doubling control karta hai resize ka cost.
