Engineering / Mathematics — Discrete Probability
Hash Function Families
Families of hash functions, keyed selection, and the properties required of them in algorithm design.
Executive summary
A single fixed hash function has no useful probabilistic guarantee, because an adversary can find its bad inputs in advance. A family from which one is drawn at random does.
The design question is which statistical property the family must satisfy, and the answer is usually far weaker than full randomness.
Learning objectives
- Explain why families rather than single functions are analysed.
- State the collision property required of a family.
- Distinguish the guarantee from that of a cryptographic hash.
01Why families
For any fixed function from a large domain to a small range, the pigeonhole principle guarantees many colliding pairs, and they can be located in advance. A guarantee of the form collisions are rare is therefore meaningless for a single function.
Hash function family
A collection H = {h_k} indexed by a key k, each mapping a domain D to a range R. A key is drawn uniformly at random and the resulting function used.
The probability is now over the key, with the inputs fixed and possibly adversarial. That is the right order of quantifiers: for every pair of distinct inputs, most keys separate them.
02The collision property
Universal family
H is universal if for every pair of distinct x, y ∈ D:
P_k[h_k(x) = h_k(y)] ≤ 1/|R|.
This is the property nearly every hashing analysis actually uses. It is a statement about pairs only, so it is implied by pairwise independence and is strictly weaker.
| Property | Guarantee | Randomness needed |
|---|---|---|
| Universal | Pairwise collision rate ≤ 1/|R| | O(log|D|) bits |
| Pairwise independent | Any two outputs jointly uniform | O(log|D|) bits |
| k-wise independent | Any k outputs jointly uniform | O(k log|D|) bits |
| Truly random | All outputs jointly uniform | O(|D| log|R|) bits |
03Not the same as a cryptographic hash
A universal family can be trivially invertible and still perfectly serviceable for hash tables. A cryptographic hash is a single fixed function with no key, whose security rests on the assumed infeasibility of finding collisions rather than on their statistical rarity.
Confusing the two leads to real errors in both directions: using a fast universal family where collision resistance against an adversary is required, or paying for a cryptographic hash where a multiply-and-shift would do.
04Frequently asked questions
Can a universal family be constructed cheaply?
Yes. Choosing a prime p above the domain size and setting h_{a,b}(x) = ((ax + b) mod p) mod m gives a universal family for non-zero a, needing only two random values.
Does universality guarantee even distribution?
It guarantees a bound on pairwise collisions, which is enough to bound the expected chain length in a hash table. It says nothing about higher-order clustering, for which stronger independence is needed.
Is a keyed cryptographic hash a universal family?
It behaves as one under standard assumptions, but the guarantee is computational rather than information-theoretic. Where an unconditional bound is needed, an explicitly universal family is required.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 125-127.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.