Universal Is Not Perfect

The universal family from 6.006 is

$h_{a,b}(k) = \big(\left(a k + b\right) \bmod p\big) \bmod m$

with $p$ a prime larger than the key universe, and $a \in {1, \dots, p-1}$ , $b \in {0, \dots, p-1}$ chosen at random when the table is built. Take $p = 101$ , $m = 8$ , and suppose this run drew $a = 37$ , $b = 19$ .

Compute $h(45)$ and $h(78)$ , and pick the statement about the guarantee that is also correct.

$h(45) = 68$ , $h(78) = 77$ ; the outer $\bmod\ m$ applies only when the inner result is at least $p$

$h(45) = 4$ , $h(78) = 5$ ; for any two distinct keys, the probability over the random choice of $a$ and $b$ that they collide is at most $1/8$

$h(45) = 4$ , $h(78) = 5$ ; the family guarantees that no two distinct keys in ${0, \dots, 100}$ ever collide

$h(45) = 4$ , $h(78) = 5$ ; the $1/8$ bound holds only when the keys themselves are drawn uniformly at random