Open addressing — linear probing, quadratic probing, double hashing

3.3.4 · Coding › Hashing

Open addressing exist kyun karta hai?

Core problem jo solve karni hai: agar kisi key ka home slot occupied hai, toh agla slot kaun sa try karein? Ek probe sequence un slots ki ordered list hai jo hum examine karte hain.

Teen strategies (sab ek template se derived)

General form: $h (k, i) = (h_{1} (k) + f (i)) mod m$ jahaan $h_{1} (k)$ base hash hai aur $f (i)$ probe offset hai jisme $f (0) = 0$ .

1. Linear probing

Sabse simple offset choose karo: $f (i) = i$ .

Primary clustering kyun hoti hai? Koi bhi key jiska home length $L$ ke cluster ke andar kahin bhi hota hai, woh end par land karti hai, use extend karti hai. Toh size $L$ ka cluster nayi keys ka $\propto L$ fraction capture karta hai → bade clusters aur bade hote jaate hain. Rich-get-richer.

2. Quadratic probing

Jump ko grow karo taaki immediate neighbourhood se nikal sako: $f (i) = c_{1} i + c_{2} i^{2}$ (commonly $f (i) = i^{2}$ ).

3. Double hashing

Step size ke roop mein ek doosra hash use karo, taaki poora probe sequence key par depend kare: $f (i) = i \cdot h_{2} (k)$ .

Figure — Open addressing — linear probing, quadratic probing, double hashing

Load factor aur performance (derive karo!)

Expected probes ka derivation (uniform hashing assumption). Maano ki har probe ek independent uniformly random slot par land karta hai. Probability ki slot occupied hai $\approx α$ .

Unsuccessful search ke liye, hum tab tak probe karte rehte hain jab tak khali slot nahi milti. Probes ki sankhya $X$ satisfy karti hai $P (X > i) = α^{i}$ (pehle $i$ probes sab occupied slots pe gaye). Toh $E [X] = \sum_{i = 0}^{\infty} P (X > i) = \sum_{i = 0}^{\infty} α^{i} = \frac{1}{1 - α} .$

Deletion — chhupi hui trap

Worked examples

Recall Feynman: 12-saal ke bachche ko explain karo

Ek row of lockers imagine karo aur tum apna bag locker #3 mein rakhna chahte ho. Agar #3 full hai toh tumhe ek rule chahiye ki agla locker kaun sa try karein. Linear: bilkul agla locker try karo (3,4,5...) — lekin jaldi hi full lockers ka ek lamba traffic-jam ban jaata hai. Quadratic: 1, phir 4, phir 9 lockers aage jump karo — tum jam ko cross kar lete ho. Double: har bachche ko ek personal "skip-by" number milta hai ek doosre jaadu ke formula se, isliye do bachche almost kabhi ek hi path par nahi chalte. Aur agar tum bag remove karo, toh tumhe ek chota "koi yahan tha" sticky note (tombstone) chodna hoga, warna agla dhundhne wala bachcha sochega ki trail jaldi khatam ho gayi.

Flashcards

Open addressing kya hai?

Ek collision strategy jahan har key table ke andar hi store hoti hai; collision par tum ek sequence of slots probe karte ho jab tak khali slot nahi milta (koi external lists nahi).

General probe-sequence template?

h (k, i) = (h_{1} (k) + f (i)) mod m

jisme

f (0) = 0

Linear probing offset aur main flaw?

f (i) = i

; primary clustering suffer karta hai (lambi contiguous runs jo merge aur grow hoti hain).

Quadratic probing offset aur main flaw?

f (i) = i^{2}

(ya

c_{1} i + c_{2} i^{2}

); secondary clustering suffer karta hai (same home ⇒ same path) aur free slot nahi reach kar sakta jab tak

α \leq 0.5

aur

m

prime na ho.

Double hashing formula?

h (k, i) = (h_{1} (k) + i h_{2} (k)) mod m

Double hashing ke saare slots probe karne ki condition?

h_{2} (k)

m

ke saath coprime hona chahiye (e.g.

m

prime, ya

m = 2^{p}

ke saath

h_{2}

odd).

Unsuccessful search ke liye expected probes?

1/ (1 - α)

1/ (1 - α)

derive karo.

P (X > i) = α^{i}

, isliye

E [X] = \sum_{i \geq 0} α^{i} = 1/ (1 - α)

Successful search ke liye expected probes?

\frac{1}{α} ln \frac{1}{1 - α}

Deleted slot ko EMPTY kyun mark nahi kar sakte?

Yeh probe chains tod deta hai — uske baad wali keys dhundhi nahi ja sakti. Iske bajaaye DELETED tombstone use karo.

Primary vs secondary clustering?

Primary: cluster ke andar kahin bhi hash karne wali koi bhi key use extend karti hai (linear). Secondary: sirf same home wali keys ek path share karti hain (quadratic).

Double hashing clustering ke liye best kyun hai?

Do keys ko poore path par collide karne ke liye dono

h_{1}

aur

h_{2}

par agree karna padta hai → near-uniform hashing, minimal clustering.

Open addressing maximum kitna load factor allow karta hai?

α < 1

strictly (slots se zyada nahi ho sakta); practically

α \approx 0.7

ke aaspaas resize karo.

Connections

Hashing — chaining (alternative: external lists vs in-table probing)
Hash functions — division & multiplication methods (jahaan se $h_{1}, h_{2}$ aate hain)
Load factor and rehashing (table kab grow karein)
Universal hashing (uniform hashing assumption ka theoretical backbone)
Cache locality (isliye open addressing practice mein often faster hota hai)
Prime table sizes (quadratic/double guarantees ke liye zaroori)