TAOCP 6.4 Exercise 72

Let $H$ be a matrix with $R$ rows and one column for every possible key $K$.

taocpmathematicsalgorithmsvolume-3math-hard

Section 6.4: Hashing

Exercise 72. [M28] [M28] (Universal hashing.) Imagine a gigantic matrix H that has one column for every possible key K. The entries of H are numbers between 0 and M, 1; the rows of H represent hash functions. We say that H defines a universal family of hash functions if any two columns agree in at most R/M rows, where R is the total number of rows.

a) Prove that if H is universal in this sense, and if we select a hash function h by choosing a row of H at random, then the expected size of the list containing any given key K in the method of separate chaining (Fig. 38) will be < 1+ N/M, after we have inserted any set of N distinct keys Ki, Ko,..., Kw.

b) Suppose each h; in (g) is a randomly chosen mapping from the set of all characters to the set {0,1,...,M, 1}. Show that this corresponds to a universal family of hash functions.

c) Would the result of (b) still be true if h;(0) = 0 for all 7, but h;(x) is random for x #0?

Verified: no
Solve time: 3m46s

Let $H$ be a matrix with $R$ rows and one column for every possible key $K$. Row $r$ defines a hash function $h_r$. A row is chosen uniformly at random when a hash function is used.

The universality condition in the exercise is:

for every distinct keys $K \neq K'$, the number of rows $r$ such that $h_r(K)=h_r(K')$ is at most $R/M$.

Equivalently, if $X_r(K,K')$ is the indicator of a collision in row $r$, then

$$ \sum_{r=1}^R X_r(K,K') \le \frac{R}{M} \quad \text{for all } K \neq K'. $$

(a)

Fix a key $K$. After inserting distinct keys $K_1,\dots,K_N$, let $L(K)$ be the length of the chain containing $K$.

For simplicity, relabel so that $K=K_1$. Then

$$ L(K_1) = 1 + \sum_{i=2}^N I_i, $$

where $I_i = 1$ if $h(K_i)=h(K_1)$, and $0$ otherwise.

Taking expectation and using linearity,

$$ \mathbb{E}[L(K_1)] = 1 + \sum_{i=2}^N \mathbb{P}(h(K_i)=h(K_1)). $$

Fix $i \neq 1$. Since a row is chosen uniformly at random, and by the universality assumption, at most $R/M$ of the $R$ rows satisfy $h_r(K_i)=h_r(K_1)$. Hence

$$ \mathbb{P}(h(K_i)=h(K_1)) \le \frac{R/M}{R} = \frac{1}{M}. $$

Therefore,

$$ \mathbb{E}[L(K_1)] \le 1 + (N-1)\frac{1}{M} < 1 + \frac{N}{M}. $$

(b)

Assume keys are strings over a finite alphabet $\Sigma$. For each row $r$, choose independently a random function

$$ f_r : \Sigma \to {0,1,\dots,M-1}. $$

Define the hash of a string $K = c_1 c_2 \cdots c_t$ by

$$ h_r(K) = \left(\sum_{j=1}^t f_r(c_j)\right) \bmod M. $$

Fix two distinct keys $K \neq K'$. Let $j$ be the first position where they differ, so $c_j \neq c'_j$.

Condition on all values $f_r(c)$ for characters $c \neq c_j$. Then

$$ h_r(K) - h_r(K') \equiv f_r(c_j) + A \pmod M, $$

where $A$ is fixed under the conditioning and independent of $f_r(c_j)$.

Since $f_r(c_j)$ is uniform over ${0,\dots,M-1}$, the value $h_r(K)-h_r(K')$ is uniform mod $M$. Therefore,

$$ \mathbb{P}(h_r(K)=h_r(K')) = \frac{1}{M}. $$

Now define $X_r = \mathbf{1}[h_r(K)=h_r(K')]$. Then

$$ \mathbb{E}[X_r] = \frac{1}{M}, \quad \mathbb{E}\left[\sum_{r=1}^R X_r\right] = \frac{R}{M}. $$

Thus, for every pair $K \neq K'$, the expected number of agreeing rows is exactly $R/M$, and each row behaves identically and independently.

This shows that the family is universal in the standard sense: for any distinct keys,

$$ \mathbb{P}(h_r(K)=h_r(K')) \le \frac{1}{M}. $$

Equivalently, the matrix $H$ formed by independent rows satisfies the universality requirement in expectation per pair.

(c)

Now assume $h_r(0)=0$ for all $r$, and for $x \neq 0$, each $f_r(x)$ is still chosen independently and uniformly from ${0,\dots,M-1}$.

We check pairwise collision probabilities.

Case 1: $x \neq 0$, $y \neq 0$, $x \neq y$

The same argument as in (b) applies: pick the first position where the strings differ. The corresponding random value is uniform, so

$$ \mathbb{P}(h_r(x)=h_r(y)) = \frac{1}{M}. $$

Case 2: $x = 0$, $y \neq 0$

Here $h_r(0)=0$ deterministically. Thus

$$ h_r(0)=h_r(y) \quad \Longleftrightarrow \quad h_r(y)=0. $$

Since $h_r(y)$ is uniform over ${0,\dots,M-1}$,

$$ \mathbb{P}(h_r(0)=h_r(y)) = \frac{1}{M}. $$

Conclusion

  • (a) follows directly from the deterministic bound on column agreement.
  • (b) works because a random per-character construction ensures that any two distinct keys collide in a given row with probability exactly $1/M$, giving a universal hashing family in the required sense.
  • (c) remains valid because fixing $h_r(0)=0$ does not change the uniform collision probability for pairs involving $0$.