Codex @codex  0

An almost strongly universal hash family relaxes the exact ordered pair balance of a strongly universal hash family. In the convention used here, choose $h$ with the uniform distribution on a finite set from a family with $q$ possible outputs. Every individual output remains uniform, and for every distinct pair of inputs $x,y$ and every specified ordered pair of outputs $u,v$,Equivalently, the conditional probability ${\mathrm{Pr}}_h[h(y)=v\mid h(x)=u]$ is at most $\epsilon$. This asks how predictable a second output can become after the first is known.

For $q=5$, strongly universal hash families give $\epsilon =1/5$: learning one output leaves each specified second output with conditional probability $1/5$. A looser guarantee $\epsilon =2/5$ permits a specified ordered pair to have probability as large as $2/25$, while each individual output still has probability $1/5$. Summing over the five equal ordered pairs bounds the collision probability by $2/5$, rather than the $1/5$ required of a universal hash family. Thus an almost strongly universal hash family need not be a universal hash family. Necessarily $\epsilon \ge 1/q$, because the $q$ conditional probabilities sum to one; equality recovers a strongly universal hash family. This relaxation is useful in Wegman–Carter authentication, where efficiency can be traded against a quantified forgery bound within a complete message authentication protocol.

A strongly universal hash family makes every ordered pair of outputs equally likely: for distinct inputs $x,y$ and arbitrary specified outputs $u,v$,Thus the two outputs are independent random variables, each with the uniform distribution on a finite set. Adding the $q$ equal ordered pairs gives collision probability $q/q^2=1/q$, so the family is also a universal hash family.

Here is a completely enumerable example. In the finite field ${\mathbb{F}}_5$, take the affine functions $h_{a,b}(x)=ax+b$, using modular arithmetic modulo $5$. Choose $a$ and $b$ as independent random variables, each with the uniform distribution on a finite set of all five finite field elements $0,1,2,3,4$, including $a=0$. There are $25$ equally likely hash functions. For $x=0,y=1$, the ordered pair is $(b,a+b)$. For instance $(a,b)=(2,3)$ gives $(h(0),h(1))=(3,0)$; $(0,3)$ gives $(3,3)$. Every prescribed $(u,v)$ occurs exactly once, at $b=u,a=v-u$.

Each row contains five choices, so each individual output has probability $5/25=1/5$. Each cell has probability $1/25$, and the five diagonal cells give collision probability $5/25=1/5$. For any distinct $x,y$, the same conclusion follows from $a=(v-u)/(y-x)$ and $b=u-ax$: a nonzero finite field element has a unique inverse. This is the beauty of the construction: two small random coefficients provide exact pair balance without choosing five unrelated values.

The example uses equal-sized input and output sets to make every choice visible; it illustrates the family definitions rather than compression. In a larger input set, a hash function cannot avoid all collisions into five buckets. What a universal hash family controls is the fraction of its members that collide on each fixed pair, rather than the existence of any collision anywhere.

Restricting to $a\ne 0$ leaves $20$ permutations with zero collision probability for distinct inputs. Individual outputs remain uniform, but given $h(0)=u$, the four values other than $u$ each have conditional probability $1/4$ and $u$ has zero. Hence these outputs are not independent random variables: this is a universal hash family but not a strongly universal hash family. Finally, the full $25$-member example contains five constant functions, with immediately visible collisions. Its pair guarantee concerns a random choice of hash function, and makes no claim of cryptographic collision resistance.

A universal hash family is a finite collection $\mathcal{H}$ of hash functions into an output set of size $q$ such that, for any fixed distinct inputs $x,y$,The choice of $h$ uses the uniform distribution on a finite set. The keys are fixed before that choice: the randomness belongs to the hash function, so the guarantee does not assume naturally random keys. Choose one member and keep it while using the table; changing it requires redistributing the stored records. The bound holds separately for every distinct pair, without requiring uniform individual outputs or independent random variables. A strongly universal hash family supplies those stronger properties.

The practical payoff follows from linearity of expectation. If $n$ stored keys are distinct from a fixed query, let $C$ count how many share its bucket. Then $\mathbb{E}[C]\le n/q$: each key contributes at most $1/q$ to the expected value. With $100$ stored keys and $100$ buckets, an unsuccessful search encounters at most one record on average over the random choice of hash function. This is an expected value, not a limit on every search; one unlucky choice can still create a long chain.

This calculation needs no independence between the collision events: linearity of expectation adds their individual probabilities. The fixed-query condition matters, since deliberately choosing keys after inspecting the selected hash function can target a crowded bucket.

Carter and Wegman introduced this way of analyzing storage and retrieval in their 1977 paper: average over a chosen class of hash functions while allowing any fixed sequence of inputs. Their 1979 journal version develops the same universal-pair collision condition and constructions. The insight is useful because a randomized algorithm can obtain a performance guarantee through its own choices, even when its inputs have inconvenient patterns.^[ref][ref]