= Universal hash family
{title2=$\Pr_h[h(x)=h(y)]\leq1/q$}
= Universal2 hashing
{synonym}
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$,
$$
\Pr_{h\in\mathcal H}[h(x)=h(y)]\leq\frac1q.
$$
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]\leq 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.https://dl.acm.org/doi/10.1145/800105.803400[Carter and Wegman, Universal classes of hash functions, STOC 1977]{ref}https://www.cs.princeton.edu/courses/archive/fall09/cos521/Handouts/universalclasses.pdf[Carter and Wegman, Universal Classes of Hash Functions, 1979]{ref}
Back to article page
