Because ∣U∣≫m, collisions are unavoidable (pigeonhole). Two different keys will sometimes map to the same bucket. A good hash function doesn't avoid collisions entirely — it makes them rare and evenly distributed.
WHY this matters: Hashing works by put then find. If you insert("cat") it lands in bucket 7. Later lookup("cat") must compute bucket 7 again to find it. If h used randomness or the current time, "cat" would land somewhere else and you'd never retrieve it.
WHY this matters — derive the cost. Let n keys be inserted into m buckets. Define the load factor:
α=mn=number of bucketsnumber of keys
Derivation of expected chain length (separate chaining):
For a fixed bucket j, let indicator Xi=1 if key i lands in bucket j.
E[Xi]=P(h(ki)=j)=m1
Expected keys in bucket j = sum over all n keys (linearity of expectation):
E[∑i=1nXi]=∑i=1nm1=mn=α
So search cost ≈ O(1+α) (1 to compute the hash, α to walk the chain). If α stays a small constant (we keep m≈n), search is O(1).
WHY this matters: The whole selling point of a hash table is O(1) operations. If h itself took O(n) or did something expensive (cryptographic hashing, sorting), you'd lose the advantage. Hashing trades a tiny constant-time computation for avoiding a search.
Imagine a wall of mailboxes numbered 0 to 9. A hash function is a rule that decides which mailbox each letter goes into based on the name on it. Good rule:
(1) Same name always same box — otherwise you'd never find your letter again (deterministic).
(2) Spread letters evenly — you don't want all letters jammed in box 3 and the rest empty (uniform).
(3) The rule is quick to apply — you shouldn't spend an hour deciding the box (fast).
Sometimes two names land in the same box (a collision) — that's okay, you just keep a little stack inside that box.
Socho ek hash function ek chhota sa "rule" hai jo kisi bhi key (string, number) ko ek bucket number me convert kar deta hai. Hashing ka pura magic isi pe tika hai ki yeh rule teen cheezein follow kare. Pehli: Deterministic — same key daalo to hamesha same bucket aaye. Agar aisa nahi hua to jo cheez insert ki thi woh lookup ke time milegi hi nahi, kyunki bucket badal jaayega. Isliye random() ko function ke andar mat use karo.
Doosri: Uniform — keys saare buckets me barabar phailni chahiye. Agar saari keys ek hi bucket me jam gayi (clustering), to wahan ek lambi chain ban jaayegi aur search O(1) se O(n) ki taraf girne lagega. Yahan load factorα=n/m aata hai — average me ek bucket me itni keys hoti hain. Linearity of expectation se prove hota hai ki expected chain length exactly α hoti hai, isliye search cost O(1+α). Agar m ko n ke aas-paas rakho to α chhota constant rahega aur sab kuch O(1).
Teesri: Fast — hash compute karna sasta hona chahiye, warna hash table ka speed advantage hi khatam ho jaata. Isliye simple operations use karte hain: multiply, add, mod. String ke liye polynomial hash use hota hai — har character ko pi weight do (Horner method se), taaki "abc" aur "cab" alag-alag hash de. Aur ek tip: table size m ko prime rakho, kyunki power-of-2 ya power-of-10 sirf last few bits/digits dekhte hain aur clustering ho jaati hai. Yaad rakhne ke liye DUF — Deterministic, Uniform, Fast.
