TAOCP 6.4 Exercise 76
Let a key $K$ be a variable-length sequence $K = (x_0, x_1, \dots, x_{\ell-1}),$ where each $x_i$ is an integer digit in ${0,1,\dots,r-1}$, and $\ell \ge 0$ depends on $K$.
Exercise 76. [M21] [M21] Suggest a way to modify (9) for keys with variable length, preserving the properties of universal hashing.
Verified: yes
Solve time: 1m14s
Solution
Let a key $K$ be a variable-length sequence
$K = (x_0, x_1, \dots, x_{\ell-1}),$
where each $x_i$ is an integer digit in ${0,1,\dots,r-1}$, and $\ell \ge 0$ depends on $K$. Assume the hash family in (9) is of the Carter–Wegman linear form for fixed length, namely
$h_{\mathbf{a}}(K) = \left(\sum_{i=0}^{n-1} a_i x_i\right) \bmod M,$
with coefficients $a_i$ chosen independently and uniformly modulo $M$, and $M$ prime, so arithmetic is in the field $\mathbb{Z}_M$.
To extend this construction to variable-length keys while preserving universality, fix a maximum allowable length $L$ and introduce one additional coefficient for encoding length. Choose independent random coefficients
$a_0, a_1, \dots, a_L \in \mathbb{Z}_M.$
Define the hash function for a key $K = (x_0,\dots,x_{\ell-1})$, where $\ell \le L$, by
$h_{\mathbf{a}}(K) = \left(\sum_{i=0}^{\ell-1} a_i x_i + a_\ell ,\ell\right) \bmod M,$
and interpret $x_i = 0$ for $i \ge \ell$ if a uniform length-$L$ representation is preferred.
This construction reduces variable-length hashing to a linear form over $\mathbb{Z}_M^{L+1}$ by embedding each key as the vector
$(x_0,\dots,x_{\ell-1},0,\dots,0,\ell).$
To verify universality, let $K \ne K'$ with lengths $\ell \ne \ell'$ or differing components. Consider the difference
$h_{\mathbf{a}}(K) - h_{\mathbf{a}}(K') \equiv \sum_{i=0}^{L-1} a_i (x_i - x'_i) + a_L(\ell - \ell') \pmod M,$
where missing components are treated as $0$. Since $M$ is prime, this is a nontrivial linear constraint in the independent uniform variables $a_0,\dots,a_L$. At least one coefficient of the form $(x_i - x'_i)$ or $(\ell - \ell')$ is nonzero, so conditioning on all coefficients except one leaves a single linear equation in a uniformly random element of $\mathbb{Z}_M$, which is satisfied with probability $1/M$.
Hence, for distinct keys $K \ne K'$,
$\Pr[h_{\mathbf{a}}(K) = h_{\mathbf{a}}(K')] = \frac{1}{M},$
so the family remains universal.
This completes the proof. ∎