Hash table — structure, open addressing vs chaining

3.3.2 · Coding › Hashing

Hash table EXISTS kyun karta hai?

Core structure KYA hai?

Figure — Hash table — structure, open addressing vs chaining

Hash function ek key ko index mein KAISE convert karta hai?

Ek classic string hash (polynomial rolling hash):

$h_{code} (s) = (\sum_{i = 0}^{L - 1} s_{i} \cdot p^{L - 1 - i}), index = h_{code} (s) mod m$

Collisions inevitable hain — KYU?

Strategy 1: Separate Chaining

Cost: average list length $= α$ , toh expected search $= O (1 + α)$ .

Strategy 2: Open Addressing

Probing	$f (i)$	Problem
Linear	$i$	primary clustering (lambi runs grow karti hain)
Quadratic	$i^{2}$	secondary clustering; kuch slots miss ho sakte hain
Double hashing	$i \cdot h_{2} (k)$	best spread; 2nd hash chahiye

Low load factor kyun matter karta hai

Chaining vs Open Addressing — 80/20 decision table

	Chaining	Open addressing
Storage	array + lists (extra pointers)	ek flat array (cache-friendly)
Load factor	1 se zyada ho sakta hai	$< 1$ rehna chahiye
Deletion	trivial (unlink)	tombstones chahiye
Worst case	$O (n)$ (sab ek list mein)	$O (n)$ (lamba probe run)
Cache	poor (pointer chasing)	excellent
Best when	bahut saare deletes, unknown $n$	speed-critical, $α$ controlled

Flashcards

Hash table ka load factor kya hota hai?

α = n / m

, stored items divided by capacity.

Collisions kyun unavoidable hain?

Pigeonhole — infinite possible keys, finite

m

slots, toh do keys ko ek slot share karna hi padega.

Separate chaining mein, har bucket kya store karta hai?

Un sabhi keys ki ek linked list (ya chhoti structure) jo us bucket mein hash hui hain.

Open addressing mein expected unsuccessful-search probes?

\frac{1}{1 - α}

Open addressing deletion mein tombstones kyun use karne padte hain?

Ek khaali slot baad ki searches ko jaldi rok dega, probe chain toot jaayegi; ek tombstone kehta hai "probing jaari rakho" lekin "reuse ke liye free hai".

Primary clustering kya hota hai?

Linear probing ke under filled slots ki lambi contiguous runs banana, jo future probes ko lambaa karti hain.

Linear vs quadratic vs double-hashing probe function

f (i)

i

i^{2}

i \cdot h_{2} (k)

Polynomial string hash mein prime

p = 31

kyun choose karte hain?

Prime > alphabet size bits spread karta hai; aur

31 x = (x ≪ 5) - x

sasta hai.

Rehash kab karte hain aur kya hota hai?

Jab

α

ek threshold se exceed kare; ek bada array (≈double) allocate karo aur saari keys reinsert karo.

Chaining mein average search cost?

O (1 + α)

Characters ka simple sum ek bura string hash kyun banta hai?

"ab"/"ba" jaise anagrams collide kar jaate hain; order ignore ho jaata hai.

Open addressing ka main hardware advantage chaining ke upar?

Cache friendliness — data contiguous hai, koi pointer chasing nahi.

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

Socho numbered lockers ki ek row hai. Apna bag dhundhne ke liye har locker check karne ki jagah, tumhare paas ek magical rule hai jo kehta hai "tumhara bag locker number 7 mein jaayega" sirf tumhara naam dekh ke. Bahut fast! Lekin kabhi kabhi do bacchon ke naam same locker point karte hain — yeh hai collision. Do fixes: (1) Chaining — locker 7 ke andar ek chhota bag-rack rakh do aur dono bags wahan hang kar do. (2) Open addressing — agar locker 7 liya hua hai, toh bas next free locker par chale jao (8, 9, ...) aur waapas aate time same tarah chalo. Agar lockers bahut zyada crowded ho jaayein, toh tum ek bada hallway rent karo aur sab ko wahan shift karo — yeh hai rehashing.

Connections

Hash functions — properties and design
Polynomial rolling hash & Rabin–Karp
Load factor and dynamic resizing / rehashing
Linked lists (chaining buckets)
Amortized analysis (resizing kyun $O (1)$ rehta hai)
Birthday paradox (collision frequency)
Sets and Maps / Dictionaries (hash tables par built)