Exercises — Universal hashing — probabilistic guarantee

(b) is universal. A family must contain many functions so we can pick one by coin flip; (a) has exactly one function, so $\mathrm{Pr}[h(x)=h(y)]$ is either $0$ or $1$ — there is no randomness to average over. An adversary who reads the source code of (a) hands you colliding keys and wins. (b) ranges over $(p-1)\cdot p$ different functions; the parent note proves $\mathrm{Pr}[h(x)=h(y)]\le 1/m$ (exactly $1/m$ when $m\mid p$). ✔ universal.

False. The randomness lives entirely in the choice of $h$. The keys $x,y$ are fixed and arbitrary — even adversarial. The probability is taken over $h$, written ${\mathrm{Pr}}_{h\in \mathcal{H}}[\cdot ]$. Mantra: RANDOM the FUNCTION, never the DATA.

$\alpha =\frac{n}{m}=\frac{50}{200}=\mathrm{0.25.}$ It is the average number of keys per slot. See the bucket picture below — $\alpha$ is just "how tall, on average, is each stack".

• $ak+b=5\cdot 11+3=58.$ (WHY: apply the linear map first.)
• $58\mathrm{mod}23=58-2\cdot 23=12.$ (WHY: mod $p$ — this is the universality engine.)
• $12\mathrm{mod}7=5.$ (WHY: squeeze into $[0,m)$.) So $h(11)=5$. (Note $m=7\le p=23$, so every slot is reachable — no wasted buckets.)

Recall the collision indicator $X_{xy}$ from the top of the page: $X_{xy}=1$ exactly when the existing key $y$ lands in the same slot as $x$, else $0$. The number of keys sharing $x$'s slot is the sum $X={\sum }_y{X}_{xy}$ over the $n$ keys already present. Because $x$ is not yet inserted, all $n$ existing keys are candidates. Using $\mathbb{E}[X_{xy}]=\mathrm{Pr}[h(x)=h(y)]\le 1/m$ and Linearity of expectation: $\mathbb{E}[X]={\sum }_y\mathbb{E}[X_{xy}]\le \frac{n}{m}=\frac{48}{64}=\mathrm{0.75.}$ Expected search cost $=1+0.75=1.75$ comparisons (the $+1$ = touch $x$'s slot header). Constant, independent of which 48 keys.

Exactly $\le 1/m$ iff $m$ divides $p$ ($m\mid p$), because only then do the $p$ residues split into $m$ perfectly equal buckets. In general (with $m\le p$ but $m\nmid p$) the buckets are uneven ($\lceil p/m\rceil$ vs $\lfloor p/m\rfloor$ residues), giving the almost-universal bound $\mathrm{Pr}[h(x)=h(y)]\le \frac{\lceil p/m\rceil }{p}\le \frac{1}{m}+\frac{1}{p}.$

If $a=0$ then $h_{0,b}(k)=(b\mathrm{mod}p)\mathrm{mod}m$, which is the same constant for every key $k$. So for any distinct $x,y$: $h(x)=h(y)$ always, i.e. $\mathrm{Pr}[\text{collision}]=1\gg 1/m=1/5$. The requirement $a\in \{1,\dots ,p-1\}$ (never $0$) is exactly what keeps $k\mapsto ak+b\mathrm{mod}p$ a bijection, so distinct keys get distinct residues before the final squeeze. ✔

Collision happens iff $(a\cdot 1+b)\mathrm{mod}7$ and $(a\cdot 4+b)\mathrm{mod}7$ land in the same class mod $3$. Direct enumeration over the 42 functions gives 14 collisions, fraction $14/42=1/3\approx 0.333$. Bound: $\lceil 7/3\rceil /7=3/7\approx 0.429$ (almost-universal), and $1/m=1/3\approx 0.333$. Observe $1/3\le 3/7$, so this pair sits exactly at the truly-universal ceiling $1/m$ and comfortably under the almost-universal ceiling $3/7$ — no pair exceeds $3/7$. ✔ (verified numerically).

Collisions are correlated: if $h(x)=h(y)$ and $h(y)=h(z)$, then automatically $h(x)=h(z)$ — the events are chained, not independent. Linearity $\mathbb{E}[\sum X_{xy}]=\sum \mathbb{E}[X_{xy}]$ holds regardless of dependence, so we never need (and never have) independence. Assuming it would be false here.

Expected cost $\le 1+\alpha$. Require $1+\alpha \le 1.2\Rightarrow \alpha \le 0.2$. $\alpha =n/m\le 0.2\Rightarrow m\ge n/0.2=10000/0.2=50000.$ Minimum slots $m=50000$. $m$ need not be prime — 50000 is perfectly fine (a common choice is even a power of two for a fast final $\mathrm{mod}m$). The only primality requirement is on the modulus $p$: you must pick a prime $p>K_{\max }$ (bigger than every key), for example $p=50021$ only if that exceeds your largest key; if keys can be large, $p$ must be a much bigger prime. So: $m=50000$ slots, $p$ = any prime above the maximum key. This ties directly to Load factor and rehashing: keep $\alpha$ low by resizing.

Resize triggers when $n>0.75m$, i.e. at $n=13$ ($m:16\to 32$), $n=25$ ($32\to 64$), $n=49$ ($64\to 128$). At $m=128$, $0.75\cdot 128=96$; inserting up to $n=100$ crosses $96$, so one more: $n=97$ ($128\to 256$). That's 4 resizes ($16\to 32\to 64\to 128\to 256$). After the last resize ($n=97$, $m=256$): $\alpha =97/256\approx 0.379$. Comfortably below $0.75$, and fresh random $h$ each time preserves the per-pair $\le 1/m$ guarantee.

The universal guarantee is "for fixed keys, over the random draw of $h$". If we reuse $h$, an adversary who has watched the table (timing, which keys collided) gains information that correlates future keys with the now-known $h$ — exactly the fixed-function weakness returning. A fresh independent draw restores the secret, so the $\le 1/m$ bound applies anew to all pairs. See Adversarial inputs and randomized algorithms.

Fix distinct $x\ne y$. Set $r=(ax+b)\mathrm{mod}p$, $s=(ay+b)\mathrm{mod}p$. Bijection step (WHY): since $p$ is prime and $a\ne 0$, the map $(a,b)\mapsto (r,s)$ is a bijection onto all ordered pairs $(r,s)$ with $r\ne s$ (subtracting the two equations, $a(x-y)\equiv r-s$, and $x-y\not\equiv 0$ is invertible mod $p$). So choosing $(a,b)$ uniformly is the same as choosing an ordered pair $(r,s)$, $r\ne s$, uniformly. Collision condition: $h(x)=h(y)$ iff $r\equiv s(\mathrm{mod}m)$. Fix $r$; among the other $p-1$ residues $s\ne r$, how many satisfy $s\equiv r(\mathrm{mod}m)$? Each residue class mod $m$ holds at most $\lceil p/m\rceil$ of the $p$ residues, so excluding $r$ itself leaves at most $\lceil p/m\rceil -1$ valid $s$. Count: $\mathrm{Pr}=\frac{\#\{(r,s):r\ne s,r\equiv s(\mathrm{mod}m)\}}{\#\{(r,s):r\ne s\}}\le \frac{p(\lceil p/m\rceil -1)}{p(p-1)}=\frac{\lceil p/m\rceil -1}{p-1}.$ Final step $\le 1/m$ (WHY each piece): we claim $\frac{\lceil p/m\rceil -1}{p-1}\le \frac{1}{m}$. Start from the ceiling fact that for any integers, $\lceil p/m\rceil <\frac{p}{m}+1$ (a ceiling never rounds up by a whole unit or more), so $\lceil p/m\rceil -1<\frac{p}{m}$. Multiplying the ceiling of $p/m$ counts at most $\frac{p}{m}$ rounded up; subtracting $1$ therefore gives at most $\frac{p-m}{m}=\frac{p}{m}-1$. Concretely, $\lceil p/m\rceil -1\le \frac{p-1}{m}$ because $m\lceil p/m\rceil \le p-1+m$ (the smallest multiple of $m$ that is $\ge p$ is at most $p-1+m$). Dividing both sides of $m(\lceil p/m\rceil -1)\le p-1$ by $m(p-1)$ gives exactly $\frac{\lceil p/m\rceil -1}{p-1}\le \frac{1}{m}$. ∎ (This is the engine behind Perfect hashing (FKS) — uses universal hashing as a building block.)

Number of unordered pairs among $c$ keys is $\left(\genfrac{}{}{0ex}{}{c}{2}\right)=\frac{c(c-1)}{2}$. Each collides with prob $\le 1/m^{\prime }=1/c^2$. By linearity: $\mathbb{E}[\text{collisions}]\le \left(\genfrac{}{}{0ex}{}{c}{2}\right)\cdot \frac{1}{c^2}=\frac{c(c-1)}{2c^2}=\frac{c-1}{2c}<\frac{1}{2}<1.$ So with $m^{\prime }=c^2$ we expect fewer than $\frac{1}{2}$ collisions; by Markov, a collision-free second-level table exists with probability $>\frac{1}{2}$, so a few random draws find one. That's the heart of FKS's two-level $O(n)$-space, $O(1)$-worst-case scheme.

Step 1 — split the square (WHY: separate the diagonal). For each bucket use the identity $c_i^2=c_i+2\left(\genfrac{}{}{0ex}{}{c_i}{2}\right)$, where $\left(\genfrac{}{}{0ex}{}{c_i}{2}\right)=\frac{c_i(c_i-1)}{2}$ counts unordered distinct pairs inside bucket $i$. Summing over all buckets: ${\sum }_i{c}_i^2={\sum }_i{c}_i+2{\sum }_i\left(\genfrac{}{}{0ex}{}{c_i}{2}\right)=n+2\underset{\text{total same-bucket pairs}}{\underbrace{\sum _i\left(\genfrac{}{}{0ex}{}{c_i}{2}\right)}}.$ (Used ${\sum }_i{c}_i=n$.) Step 2 — count colliding pairs in expectation (WHY: this is where universality enters). ${\sum }_i\left(\genfrac{}{}{0ex}{}{c_i}{2}\right)$ is exactly the number of unordered pairs of keys that landed in the same bucket. For one fixed pair $\{x,y\}$, the probability they share a bucket is $\le 1/m$. There are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs total, so by Linearity of expectation: $\mathbb{E}\left[{\sum }_i\right(\genfrac{}{}{0ex}{}{c_i}{2}\left)\right]={\sum }_{\{x,y\}}\mathrm{Pr}[\text{same bucket}]\le \left(\genfrac{}{}{0ex}{}{n}{2}\right)\cdot \frac{1}{m}.$ Step 3 — plug in $m=n$. Then $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\cdot \frac{1}{n}=\frac{n(n-1)}{2}\cdot \frac{1}{n}=\frac{n-1}{2}$. Step 4 — combine. $\mathbb{E}\left[{\sum }_i{c}_i^2\right]\le n+2\cdot \frac{n-1}{2}=n+(n-1)=2n-1=O(n).$ So the whole two-level structure uses linear expected space while giving worst-case $O(1)$ lookups — exactly the FKS guarantee. ∎