Intuition The core idea (WHY this exists)A fixed hash function can always be defeated. Once an adversary knows your function h h h O ( n ) O(n) O ( n ) don't commit to one function . Pick h h h randomly from a carefully designed family H \mathcal{H} H any fixed pair of keys, the probability they collide is tiny — and the adversary can't exploit randomness they can't see.
WHAT we buy: expected O ( 1 ) O(1) O ( 1 ) for every input , not just lucky ones.
Definition Universal familyA family H \mathcal{H} H U U U { 0 , 1 , … , m − 1 } \{0,1,\dots,m-1\} { 0 , 1 , … , m − 1 } universal x ≠ y x \neq y x = y Pr h ∈ H [ h ( x ) = h ( y ) ] ≤ 1 m \Pr_{h \in \mathcal{H}}\big[\, h(x) = h(y) \,\big] \le \frac{1}{m} Pr h ∈ H [ h ( x ) = h ( y ) ] ≤ m 1 h h h uniformly at random from H \mathcal{H} H
Common mistake Steel-man: "Random hashing means each key lands uniformly."It feels right — we picture keys scattering evenly. But the universal property is not about one key's distribution; it's about pairs . We never assume the data is random. The randomness lives entirely in the choice of h h h , while the keys x , y x,y x , y fixed x , y x,y x , y random h h h
Suppose we insert n n n m m m h h h expected number of keys colliding with a given key x x x .
α = n m \alpha = \dfrac{n}{m} α = m n x x x 1 + α 1 + \alpha 1 + α + 1 +1 + 1 x x x n − 1 m \frac{n-1}{m} m n − 1 x x x
Intuition Therefore (HOW it gives O(1))Expected search time = O ( 1 + α ) = O(1 + \alpha) = O ( 1 + α ) m = Θ ( n ) m = \Theta(n) m = Θ ( n ) α = O ( 1 ) \alpha = O(1) α = O ( 1 ) every operation is expected O ( 1 ) O(1) O ( 1 ) regardless of the input keys . The guarantee is over our coin flips, not over "nice" data.
Definition The number-theoretic familyH p , m \mathcal{H}_{p,m} H p , m p > p > p > a ∈ { 1 , … , p − 1 } a \in \{1,\dots,p-1\} a ∈ { 1 , … , p − 1 } b ∈ { 0 , … , p − 1 } b \in \{0,\dots,p-1\} b ∈ { 0 , … , p − 1 } h a , b ( k ) = ( ( a k + b ) m o d p ) m o d m h_{a,b}(k) = \big((a\,k + b) \bmod p\big) \bmod m h a , b ( k ) = ( ( a k + b ) mod p ) mod m H p , m = { h a , b } \mathcal{H}_{p,m} = \{\, h_{a,b} \,\} H p , m = { h a , b } a , b a,b a , b
Common mistake Steel-man: "The final m o d m \bmod m mod m ≤ 1 / m \le 1/m ≤ 1/ m feels exact — we mapped p p p m m m 1 / m 1/m 1/ m m m m not divide p p p ⌈ p / m ⌉ \lceil p/m\rceil ⌈ p / m ⌉ ⌊ p / m ⌋ \lfloor p/m\rfloor ⌊ p / m ⌋ Pr [ h ( x ) = h ( y ) ] ≤ ⌈ p / m ⌉ − 1 p − 1 ≤ 1 m . \Pr[h(x)=h(y)] \le \frac{\lceil p/m\rceil - 1}{p-1} \le \frac{1}{m}. Pr [ h ( x ) = h ( y )] ≤ p − 1 ⌈ p / m ⌉ − 1 ≤ m 1 . ≤ ⌈ p / m ⌉ p ≤ 1 m + 1 p \le \frac{\lceil p/m\rceil}{p} \le \frac{1}{m}+\frac{1}{p} ≤ p ⌈ p / m ⌉ ≤ m 1 + p 1 truly universal (≤ 1 / m \le 1/m ≤ 1/ m m ∣ p m \mid p m ∣ p almost-universal (≤ 1 / m + 1 / p \le 1/m + 1/p ≤ 1/ m + 1/ p 1 / p 1/p 1/ p p p p Fix: quote ≤ 1 / m \le 1/m ≤ 1/ m m ∣ p m \mid p m ∣ p + 1 / p +1/p + 1/ p
Worked example Why is it (almost) universal? (sketch of the WHY)Fix x ≠ y x\neq y x = y r = ( a x + b ) m o d p r = (ax+b)\bmod p r = ( a x + b ) mod p s = ( a y + b ) m o d p s=(ay+b)\bmod p s = ( a y + b ) mod p a ≠ 0 a\neq 0 a = 0 p p p ( a , b ) ↦ ( r , s ) (a,b)\mapsto(r,s) ( a , b ) ↦ ( r , s ) bijection onto pairs with r ≠ s r \neq s r = s p p p r ≡ s ( m o d m ) r \equiv s \pmod m r ≡ s ( mod m ) r r r s ≠ r s\neq r s = r s ≡ r ( m o d m ) s\equiv r \pmod m s ≡ r ( mod m ) ⌈ p / m ⌉ − 1 \lceil p/m\rceil - 1 ⌈ p / m ⌉ − 1 p − 1 p-1 p − 1 Pr [ collision ] ≤ ⌈ p / m ⌉ − 1 p − 1 ≤ 1 m . \Pr[\text{collision}] \le \frac{\lceil p/m\rceil - 1}{p-1} \le \frac{1}{m}. Pr [ collision ] ≤ p − 1 ⌈ p / m ⌉ − 1 ≤ m 1 .
Worked example Example 1 — Expected probe countTable with m = 100 m = 100 m = 100 n = 50 n = 50 n = 50 h h h x x x
Why: x x x n m \frac{n}{m} m n E [ collisions ] ≤ 50 100 = 0.5 \mathbb{E}[\text{collisions}] \le \frac{50}{100} = 0.5 E [ collisions ] ≤ 100 50 = 0.5 = 1 + 0.5 = 1.5 = 1 + 0.5 = 1.5 = 1 + 0.5 = 1.5 Constant.
Worked example Example 2 — Computingh a , b h_{a,b} h a , b p = 17 p = 17 p = 17 m = 6 m = 6 m = 6 a = 3 , b = 4 a=3, b=4 a = 3 , b = 4 k = 10 k=10 k = 10
a k + b = 3 ⋅ 10 + 4 = 34 ak+b = 3\cdot 10 + 4 = 34 ak + b = 3 ⋅ 10 + 4 = 34 Why: apply a k + b ak+b ak + b 34 m o d 17 = 0 34 \bmod 17 = 0 34 mod 17 = 0 Why: mod p p p 0 m o d 6 = 0 0 \bmod 6 = 0 0 mod 6 = 0 Why: squeeze into table range [ 0 , m ) [0,m) [ 0 , m ) h ( 10 ) = 0 h(10) = 0 h ( 10 ) = 0
Worked example Example 3 — Probability sanity checkHere p = 17 p=17 p = 17 m = 6 m=6 m = 6 6 ∤ 17 6 \nmid 17 6 ∤ 17 ⌈ 17 / 6 ⌉ 17 = 3 17 ≈ 0.176 \frac{\lceil 17/6\rceil}{17} = \frac{3}{17}\approx 0.176 17 ⌈ 17/6 ⌉ = 17 3 ≈ 0.176 1 / m = 1 / 6 ≈ 0.167 1/m = 1/6 \approx 0.167 1/ m = 1/6 ≈ 0.167 10 10 10 15 15 15 ( a , b ) (a,b) ( a , b ) ≤ 3 / 17 \le 3/17 ≤ 3/17
Recall Feynman: explain to a 12-year-oldImagine a bully who always picks the locker that's already full so you can't fit your stuff. If your locker-picking rule is fixed , he always wins. So instead, before class you secretly roll dice to decide the rule. Now the bully doesn't know which lockers things go to, so on average everyone gets their own locker and nobody waits long. The dice (random choice of h h h your secret, and that's what beats him — not that the kids are "random".
"RANDOM the FUNCTION, never the DATA."
And the bound: "Pair collides at most 1-in-m." (Pr ≤ 1 / m \Pr \le 1/m Pr ≤ 1/ m m ∣ p m \mid p m ∣ p + 1 / p +1/p + 1/ p
When is a family H \mathcal{H} H For every distinct
x ≠ y x \neq y x = y ,
Pr h ∈ H [ h ( x ) = h ( y ) ] ≤ 1 / m \Pr_{h\in\mathcal{H}}[h(x)=h(y)] \le 1/m Pr h ∈ H [ h ( x ) = h ( y )] ≤ 1/ m , with
h h h chosen uniformly at random.
Where does the randomness live in universal hashing? In the choice of the hash function from the family — NOT in the keys, which may be adversarial.
Why use linearity of expectation in the analysis? It lets us sum
E [ X x y ] \mathbb{E}[X_{xy}] E [ X x y ] without assuming independence, and collisions are dependent.
Expected number of keys colliding with x x x ≤ n / m = α \le n/m = \alpha ≤ n / m = α (the load factor).
Expected cost of a search with universal hashing? O ( 1 + α ) O(1 + \alpha) O ( 1 + α ) ; with
m = Θ ( n ) m=\Theta(n) m = Θ ( n ) it is
O ( 1 ) O(1) O ( 1 ) .
State the classic universal family h a , b h_{a,b} h a , b h a , b ( k ) = ( ( a k + b ) m o d p ) m o d m h_{a,b}(k)=((ak+b)\bmod p)\bmod m h a , b ( k ) = (( ak + b ) mod p ) mod m , with prime
p > p> p > max key,
a ∈ { 1.. p − 1 } a\in\{1..p-1\} a ∈ { 1.. p − 1 } ,
b ∈ { 0.. p − 1 } b\in\{0..p-1\} b ∈ { 0.. p − 1 } .
Is h a , b h_{a,b} h a , b Only when
m ∣ p m \mid p m ∣ p (
Pr ≤ 1 / m \Pr \le 1/m Pr ≤ 1/ m ). In general it is
almost -universal with
Pr ≤ 1 / m + 1 / p \Pr \le 1/m + 1/p Pr ≤ 1/ m + 1/ p .
Why must a ≠ 0 a \neq 0 a = 0 h a , b h_{a,b} h a , b So the map
k ↦ a k + b m o d p k\mapsto ak+b \bmod p k ↦ ak + b mod p is a bijection, ensuring distinct keys give distinct residues mod
p p p .
What does universal hashing protect against that fixed hashing cannot? An adversary who chooses worst-case keys to force all collisions.
E [ X x y ] \mathbb{E}[X_{xy}] E [ X x y ] Pr [ h ( x ) = h ( y ) ] \Pr[h(x)=h(y)] Pr [ h ( x ) = h ( y )] , since
X x y X_{xy} X x y is a 0/1 indicator.
Adversary forces collisions
Pick h randomly from family H
Pr collision at most 1 over m
E of X at most n-1 over m
Expected O of 1 per operation
Intuition Hinglish mein samjhoDekho, idea simple hai: agar tum ek fixed hash function use karoge, to koi smart banda (adversary) tumhare function ko dekh kar aise keys de dega jo sab ek hi slot me ja gire — phir har operation O ( n ) O(n) O ( n ) pehle se fix mat karo . Ek poora family H \mathcal{H} H h h h randomly uthao. Ab randomness tumhare paas hai, adversary ke paas nahi.
"Universal" ka matlab: kisi bhi do alag keys x ≠ y x \neq y x = y h h h ≤ 1 / m \le 1/m ≤ 1/ m keys me nahi, function ke selection me hai. Keys chahe adversary de, fark nahi padta.
Guarantee derive karna easy hai: har dusri key ke liye ek indicator X x y X_{xy} X x y E [ X x y ] = Pr [ collision ] ≤ 1 / m \mathbb{E}[X_{xy}] = \Pr[\text{collision}] \le 1/m E [ X x y ] = Pr [ collision ] ≤ 1/ m linearity of expectation lagao (independence ki zaroorat hi nahi) — sabko jodo, mil jata hai expected collisions ≤ n / m = α \le n/m = \alpha ≤ n / m = α O ( 1 + α ) O(1+\alpha) O ( 1 + α ) m ≈ n m \approx n m ≈ n O ( 1 ) O(1) O ( 1 )
Concrete family: h a , b ( k ) = ( ( a k + b ) m o d p ) m o d m h_{a,b}(k) = ((ak+b)\bmod p)\bmod m h a , b ( k ) = (( ak + b ) mod p ) mod m p p p a , b a,b a , b exactly universal (≤ 1 / m \le 1/m ≤ 1/ m m m m p p p m ∤ p m \nmid p m ∤ p ≤ 1 / m + 1 / p \le 1/m + 1/p ≤ 1/ m + 1/ p p p p 1 / p 1/p 1/ p
