Hash function — properties - deterministic, uniform, fast

3.3.1 · Coding › Hashing

Hash function KYA hai?

Kyunki $∣ U ∣ ≫ m$ hai, collisions unavoidable hain (pigeonhole). Do alag keys kabhi kabhi same bucket mein map ho jaayengi. Ek acchi hash function collisions ko poori tarah avoid nahi karti — woh unhe rare aur evenly distributed banati hai.

Teen core properties

1. Deterministic

YEH KYU MATTER KARTA HAI: Hashing put then find se kaam karti hai. Agar aap insert("cat") karte ho toh woh bucket 7 mein jaata hai. Baad mein lookup("cat") ko bucket 7 dobara compute karna hoga taaki woh mile. Agar $h$ randomness ya current time use karta, toh "cat" kahin aur land hota aur aap usse kabhi retrieve nahi kar paate.

2. Uniform (acchi distribution)

YEH KYU MATTER KARTA HAI — cost derive karo. Maan lo $n$ keys $m$ buckets mein insert ki gayi hain. Load factor define karo: $α = \frac{n}{m} = \frac{number of keys}{number of buckets}$

Expected chain length ka derivation (separate chaining): Ek fixed bucket $j$ ke liye, indicator $X_{i} = 1$ agar key $i$ bucket $j$ mein land karti hai. $E [X_{i}] = P (h (k_{i}) = j) = \frac{1}{m}$ Bucket $j$ mein expected keys = sabhi $n$ keys ka sum (linearity of expectation): $E [\sum_{i = 1}^{n} X_{i}] = \sum_{i = 1}^{n} \frac{1}{m} = \frac{n}{m} = α$

Toh search cost ≈ $O (1 + α)$ hai (1 hash compute karne ke liye, $α$ chain walk karne ke liye). Agar $α$ ek chhota constant rehta hai (hum $m \approx n$ rakhte hain), toh search $O (1)$ hai.

Figure — Hash function — properties - deterministic, uniform, fast

3. Fast (compute karne mein efficient)

YEH KYU MATTER KARTA HAI: Hash table ka poora selling point $O (1)$ operations hai. Agar $h$ khud $O (n)$ leta ya kuch expensive karta (cryptographic hashing, sorting), toh aap advantage kho dete. Hashing ek tiny constant-time computation ke badle search avoid karna trade karta hai.

Worked examples

Recall Feynman: ek 12-saal ke bacche ko samjhao

Ek deewar par numbered mailboxes 0 se 9 tak imagine karo. Ek hash function ek rule hai jo decide karta hai ki har letter kis mailbox mein jaayega uske naam ke basis par. Accha rule: (1) Same naam hamesha same box — warna aapko apna letter dobara nahi milta (deterministic). (2) Letters evenly spread karo — aap nahi chahte ki saare letters box 3 mein jam jaayein aur baaki khaali rahein (uniform). (3) Rule jaldi apply ho — aapko box decide karne mein ek ghanta nahi lagana chahiye (fast). Kabhi kabhi do naam same box mein aa jaate hain (ek collision) — koi baat nahi, aap bas us box ke andar ek chhota stack rakhte ho.

Flashcards

Ek acchi hash function ki teen properties kya hain?

Deterministic (same key → same bucket), Uniform (keys ko evenly spread karta hai), Fast (compute karna sasta,

O (1)

O (L)

Hash function deterministic kyun honi chahiye?

Taaki lookup wahi SAME bucket recompute kare jahan insert ne key rakhi thi; warna retrieval impossible hai.

Load factor

α

define karo.

α = n / m

= keys ki sankhya ÷ buckets ki sankhya; uniform hashing ke under expected chain length.

Separate chaining ke saath expected search cost kya hai?

O (1 + α)

— linearity of expectation se derive kiya, har bucket average mein

α

keys rakhta hai.

Division method mein prime table size

m

kyun prefer karte hain?

Prime mod key ke saare bits/digits mix karta hai; 2 ya 10 ki powers sirf low-order bits use karti hain → clustering.

Collisions unavoidable kyun hain?

Pigeonhole:

∣ U ∣ ≫ m

, toh possible keys se zyada buckets nahi hain — kuch share karni hi padegi.

String hash mein ASCII sum karne ki jagah weights

p^{i}

kyun use karte hain?

Summing anagrams ko collide karaata hai ("abc"="cab"); positional weights character order ko alag karte hain.

Simple Uniform Hashing kya assume karta hai?

Har key equally likely (

1/ m

) hai kisi bhi bucket mein land hone ke liye, dusri keys se independent.

Hash table ko resize/rehash kab karna chahiye?

Jab

α

ek threshold (~0.75) se zyada ho jaaye taaki chains chhoti rahein aur operations

O (1)

rahein.

Hash function ek fresh random number per call kyun use nahi kar sakti?

Yeh determinism tod dega — same key har baar alag hash karti, lookups break ho jaate.

Connections

Hash Table — woh data structure jo yeh functions power karte hain.
Collision Resolution — Separate Chaining — jo unavoidable collisions handle karta hai.
Collision Resolution — Open Addressing — alternative jo especially uniform hashes maangta hai.
Load Factor and Rehashing — $α$ ko chhota rakhta hai taaki $O (1)$ preserve ho.
Modular Arithmetic — division method ki basis.
Pigeonhole Principle — kyun collisions exist karni chahiye.
Cryptographic Hash Functions — contrast: strong & slow vs. hamari cheap & fast.

$k$	$k mod 7$
50	1
700	0
76	6
85	1
92	1
73	3
101	3