Noesis
3.3.4Hashing

Open addressing — linear probing, quadratic probing, double hashing

2,028 words9 min readdifficulty · medium5 backlinks
🇮🇳 Yeh note Hinglish mein padho →

WHY does open addressing exist?

The core problem to solve: given a key whose home slot is occupied, which slot do we try next? A probe sequence is the ordered list of slots we examine.

The three strategies (all derived from one template)

General form: h(k,i)=( h1(k)+f(i) ) mod mh(k,i) = \big(\,h_1(k) + f(i)\,\big) \bmod m where h1(k)h_1(k) is the base hash and f(i)f(i) is the probe offset with f(0)=0f(0)=0.

1. Linear probing

Choose the simplest offset: f(i)=if(i)=i.

Why does primary clustering happen? Any key whose home falls anywhere inside a cluster of length LL lands at the end, extending it. So a cluster of size LL captures a fraction ∝L\propto L of new keys → big clusters get bigger. Rich-get-richer.

2. Quadratic probing

Make the jump grow so we escape the immediate neighbourhood: f(i)=c1i+c2i2f(i)=c_1 i + c_2 i^2 (commonly f(i)=i2f(i)=i^2).

3. Double hashing

Use a second hash as the step size, so the whole probe sequence depends on the key: f(i)=i⋅h2(k)f(i)=i\cdot h_2(k).

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

Load factor & performance (derive it!)

Derivation of expected probes (uniform hashing assumption). Assume each probe lands on an independent uniformly random slot. Probability a slot is occupied ≈α\approx \alpha.

For an unsuccessful search, we keep probing until we hit an empty slot. The number of probes XX satisfies P(X>i)=αiP(X>i)=\alpha^i (first ii probes all hit occupied slots). So E[X]=∑i=0∞P(X>i)=∑i=0∞αi=11−α.E[X]=\sum_{i=0}^{\infty}P(X>i)=\sum_{i=0}^{\infty}\alpha^i=\frac{1}{1-\alpha}.

Deletion — the hidden trap

Worked examples

Recall Feynman: explain to a 12-year-old

Imagine a row of lockers and you want to drop your bag in locker #3. If #3 is full you need a rule for which locker to try next. Linear: try the very next locker (3,4,5...) — but soon a long traffic-jam of full lockers forms. Quadratic: jump 1, then 4, then 9 lockers ahead — you skip past the jam. Double: every kid gets a personal "skip-by" number from a second magic formula, so two kids almost never walk the same path. And if you remove a bag, you must leave a little "someone was here" sticky note (tombstone), or the next kid searching will think the trail ended too early.

Flashcards

What is open addressing?
A collision strategy where every key is stored inside the table itself; on collision you probe a sequence of slots until finding an empty one (no external lists).
General probe-sequence template?
h(k,i)=(h1(k)+f(i)) mod mh(k,i)=(h_1(k)+f(i))\bmod m with f(0)=0f(0)=0.
Linear probing offset and main flaw?
f(i)=if(i)=i; suffers primary clustering (long contiguous runs that merge and grow).
Quadratic probing offset and main flaw?
f(i)=i2f(i)=i^2 (or c1i+c2i2c_1i+c_2i^2); suffers secondary clustering (same home ⇒ same path) and may not reach a free slot unless α≤0.5\alpha\le0.5 and mm prime.
Double hashing formula?
h(k,i)=(h1(k)+i h2(k)) mod mh(k,i)=(h_1(k)+i\,h_2(k))\bmod m.
Condition for double hashing to probe all slots?
h2(k)h_2(k) must be coprime to mm (e.g. mm prime, or m=2pm=2^p with h2h_2 odd).
Expected probes for an unsuccessful search?
1/(1−α)1/(1-\alpha).
Derive 1/(1−α)1/(1-\alpha).
P(X>i)=αiP(X>i)=\alpha^i, so E[X]=∑i≥0αi=1/(1−α)E[X]=\sum_{i\ge0}\alpha^i=1/(1-\alpha).
Expected probes for a successful search?
1αln⁡11−α\frac{1}{\alpha}\ln\frac{1}{1-\alpha}.
Why can't we just mark a deleted slot EMPTY?
It breaks probe chains — later keys past it become unfindable. Use a DELETED tombstone instead.
Primary vs secondary clustering?
Primary: any key hashing into a cluster extends it (linear). Secondary: only keys with the same home share a path (quadratic).
Why is double hashing the best for clustering?
Two keys must agree on both h1h_1 and h2h_2 to collide on a whole path → near-uniform hashing, minimal clustering.
Max load factor open addressing allows?
α<1\alpha<1 strictly (can't exceed slots); practically resize around α≈0.7\alpha\approx0.7.

Connections

  • Hashing — chaining (the alternative: external lists vs in-table probing)
  • Hash functions — division & multiplication methods (where h1,h2h_1,h_2 come from)
  • Load factor and rehashing (when to grow the table)
  • Universal hashing (theoretical backbone of "uniform hashing assumption")
  • Cache locality (why open addressing is often faster in practice)
  • Prime table sizes (needed for quadratic/double guarantees)

Concept Map

option A

option B

needs

ideal is

general form

f of i equals i

f of i equals i squared

f of i equals i h2

suffers

kills

still has

avoids both

Collision at home slot

Chaining

Open addressing

Probe sequence

Template h1 plus f of i

Linear probing f equals i

Quadratic probing f equals i squared

Double hashing f equals i times h2

Primary clustering

Secondary clustering

Permutation of all m slots

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, hashing me jab do keys ek hi slot maangti hain to collision ho jaata hai. Chaining me hum us slot pe ek linked list laga dete hain, par open addressing bolta hai — "yeh seat full hai? koi baat nahi, agli khaali seat dhoondo, wahi array ke andar." Matlab saara data ek hi contiguous array me rehta hai, koi extra pointer nahi — isliye CPU cache ko bahut pasand aata hai aur fast chalta hai.

Ab "agli seat kaun si?" — yeh decide karne ke teen tareeke hain. Linear probing me seedha agle slot pe jao (+1, +1...), simple hai par primary clustering ho jaata hai — full slots ka lamba jam ban jaata hai aur woh badhta hi rehta hai. Quadratic probing me jump bada karte jao (+1, +4, +9...), isse jam se aage nikal jaate ho, par jin keys ka home same hai woh phir bhi same path follow karti hain (secondary clustering), aur table aadhe se zyada bhar gaya to khaali slot milne ki guarantee nahi (isliye mm prime aur α≤0.5\alpha\le0.5 rakho). Double hashing sabse best — ek doosra hash h2(k)h_2(k) step-size deta hai, to har key ka apna unique raasta hota hai, clustering almost khatam.

Performance ka funda: load factor α=n/m\alpha=n/m. Unsuccessful search me average probes =11−α=\frac{1}{1-\alpha}. Yaad rakho — α=0.9\alpha=0.9 pe 10 probes lagte hain, α=0.5\alpha=0.5 pe sirf 2! Isliye table bharne se pehle hi resize/rehash kar do. Aur ek important trap: delete karte time slot ko seedha EMPTY mat karo, warna probe chain toot jaata hai aur aage wali keys "kho" jaati hain — uski jagah tombstone (DELETED marker) lagao. Bas yeh teen formulas aur deletion ka funda pakka kar lo, exam aur interview dono me chalega.

Go deeper — visual, from zero

D1FoundationsEvery symbol from zero · 2,021 wordsD2Visual walkthroughThe derivation in pictures · 2,023 wordsD3Worked examplesEvery scenario covered · 3,705 wordsD4ExercisesGraded, full solutions · 3,643 wordsD5Question bankConcept traps, quick reveals · 2,383 words

Test yourself — Hashing

L1 RecognitionL2 RecallL3 ProductionL4 ApplicationL5 Mastery

Connections

Load factor — when to resize, rehashing costCoding · 3.3.6Universal hashing — probabilistic guaranteeCoding · 3.3.8Hash function — properties - deterministic, uniform, fastCoding · 3.3.1Chaining — linked lists in buckets, load factor, resizingCoding · 3.3.3Deletion in open addressing — tombstone markersCoding · 3.3.5Load factor — when to resize, rehashing costCoding · 3.3.6Universal hashing — probabilistic guaranteeCoding · 3.3.8