Universal Hashing and Guarantees That Hold for Every Input

A hash table with chaining is only as good as its hash function, and for any fixed hash function an adversary who knows it can choose keys that all collide. The usual defence is to say that keys are “random”, which is an assumption about the input rather than about the algorithm. Universal hashing removes the assumption: the algorithm chooses the function at random from a family, and the expected behaviour is good for every fixed set of keys, because the adversary cannot know which function will be chosen.

The construction and its analysis are worth working through because the guarantee is precise, the family is small, and the cost of evaluation determines whether the guarantee is usable in practice.

What universality actually requires

A family H of functions from a universe U to [0, m) is universal if, for every pair of distinct keys x ≠ y, the probability that a uniformly random h from H maps them to the same bucket is at most 1/m:

$$ \Pr_{h \in H}[h(x) = h(y)] \le \frac{1}{m} $$

This is a pairwise condition, not a full independence condition. It constrains the joint distribution of two outputs and says nothing about three or more. That is exactly enough for the analyses that matter, because the expected chain length at a bucket is a sum over keys of indicators, and bounding the expectation requires only the pairwise probabilities.

The analysis of unsuccessful search in a table with n keys and m buckets: the number of keys colliding with a given probe is a sum of n indicators, each with probability at most 1/m, so the expected count is at most n/m. If m ≥ n, the expected count is at most 1 and the expected search time is constant. The variance can be computed from the same pairwise condition, because it needs only the covariances of pairs, so the concentration statement also follows without higher-order independence.

The condition is weaker than it looks. A fully random function satisfies it with equality. A family where every pair of keys collides with probability exactly 1/m is called strongly universal, and it gives a stronger guarantee at higher cost. Universality is the minimum needed for the standard bounds, and it is much cheaper to construct.

The multiply-shift family and its cost

The standard practical family for machine-word keys uses one multiplication and one shift. Fix an odd constant a and define h_a(x) = (a · x mod 2^w) >> (w - m') for w-bit words and an output range of size 2^{m'}. Choosing a uniformly at random from the odd w-bit integers makes the family almost universal: the collision probability is bounded by a small constant times 2^{-m'}, not by 2^{-m'} itself.

The proof is a geometric argument. Multiplying by an odd a modulo 2^w is a bijection, so the set {a · x mod 2^w} over all odd a is the set of all odd multiples of x’s odd part. Two distinct keys x and y differ by d = x - y; the collision condition is that a · d mod 2^w falls in a specific interval of length 2^w / 2^{m'} after the shift. Counting how many odd a put it there, over the 2^{w-1} choices, gives a collision probability bounded by a small constant multiple of 2^{-m'} rather than exactly 2^{-m'}. That constant is why the family is described as almost universal, and for the analysis of chaining it changes only the constant in the expected chain length.

The cost is one integer multiply, a few cycles on common hardware, and one shift. That is cheaper than a modulo by a prime, which is a division, and it is why the multiply-shift family is what high-performance hash tables use. The family requires the table size to be a power of two, which is a constraint on the table rather than on the hash.

// Multiply-shift for 64-bit keys, output in [0, 2^m).
// `a` is a random odd 64-bit value chosen once per table.
#[inline]
fn hash_mul_shift(a: u64, x: u64, m: u32) -> usize {
    (a.wrapping_mul(x) >> (64 - m)) as usize
}

struct Table {
    buckets: Vec<Vec<u64>>,
    a: u64,
    m: u32,
}

impl Table {
    fn new(m: u32) -> Self {
        // Any odd constant is a member of the family; a real table draws it at random.
        let a = 0x9E37_79B9_7F4A_7C15 | 1;
        Table { buckets: vec![Vec::new(); 1 << m], a, m }
    }
}

The constant in the example is a fixed odd value for illustration; a real table draws a from a source of randomness once at construction. Drawing it once per table is enough because the adversary must commit to keys before seeing a, and the guarantee is over the choice of a for a fixed key set.

The prime-modulus family and when it is worth the division

The original Carter-Wegman construction works over a prime p larger than the universe: choose a uniformly from [1, p-1] and b uniformly from [0, p-1], and define h(x) = ((a · x + b) mod p) mod m. For any two distinct keys the probability of collision is at most 1/m plus a term of order m/p, which vanishes when p is much larger than m.

The family is strongly universal when the outer reduction is dropped and m = p, which is why it appears in analyses that need the stronger condition. It costs a multiplication, an addition, and two modulo operations, and modulo by a non-power-of-two is a division: on the order of twenty to forty cycles for 64-bit operands, against one or two for the multiply. That ratio is why the family is used in contexts where the analysis is the point, and the multiply-shift family is used where throughput is.

There is a middle option. Choose p to be a prime just below 2^64 and use the fact that reduction modulo such a p can be done with two multiplies and no division, via the identity that 2^64 ≡ 2^64 - p (mod p). The technique is the same one used for fast reduction in cryptographic field arithmetic. It costs more than multiply-shift but avoids the division, and it keeps the stronger universality property.

Two-level schemes and the worst case

Universal hashing gives an expected bound. Fredman, Komlós, and Szemerédi showed that a two-level construction gives a worst-case constant lookup, with O(n) space, for any fixed key set. The first level hashes n keys into n buckets with a universal function; the i-th bucket receives n_i keys and is given a second-level table of size n_i^2 with its own universal function.

The expected space is linear because the sum of n_i^2 over the buckets is small in expectation. With m = n buckets, a bucket receives n_i keys with mean 1, and E[n_i^2] = Var[n_i] + E[n_i]^2 is just under 2 for a universal function, so summing over the n buckets gives an expectation below 2n. A bucket whose second-level table would be too large is rebuilt with a fresh function; by Markov’s inequality the probability that a given bucket exceeds twice its expected size is at most one half, so the expected number of rebuilds is constant.

The second level is collision-free with positive probability when the table size is n_i^2, because the expected number of colliding pairs is (n_i choose 2) / n_i^2 < 1/2, so the probability of no collision is at least 1/2. Trying functions until one is collision-free takes at most two attempts in expectation, and the resulting structure answers a lookup in two hash evaluations and two array accesses, with no chaining and no worst case beyond that.

This is the construction behind perfect hashing for static key sets, and it is the reason “worst-case O(1) lookup” is a real guarantee rather than an average-case claim. The price is that the structure is built for a fixed key set: inserting a new key invalidates the second-level sizing and requires a rebuild, which costs O(n).

Failure modes that survive a universal family

A universal family bounds the collision probability for distinct keys, and that bound is useless for equal keys. If the key set contains many duplicates, they all land in the same bucket by definition, and the chain length is the multiplicity. A hash table that must handle duplicates needs the bucket to store counts or to allow the chain to be long without degrading, and no choice of hash function changes this.

The family also assumes the keys are fixed before the function is chosen. If the adversary can observe the function and then choose keys, the guarantee evaporates: the adversary picks a colliding set directly. Systems that face an adversary over time must reseed the function periodically, which is why some hash tables randomize the seed per process rather than per table, and why a table whose keys arrive from an untrusted source needs the seed to be unpredictable.

Hash flooding attacks exploit exactly this. A server that hashes request parameters into a table with a fixed function can be made to collide all parameters into one bucket, turning each lookup into a linear scan and the request handling into quadratic work. The defence is a per-process random seed chosen before any request is parsed. The attack does not require knowing the implementation, only the hash function, and the countermeasure does not require a cryptographic hash, only a family the attacker cannot predict.

The third failure is arithmetic overflow. The multiply-shift family computes a · x in w bits with wraparound; in a language where the multiplication is checked or where the operands are narrower than the intended width, the wraparound either traps or is computed at a different width, and the universality proof no longer applies. The proof depends on arithmetic modulo 2^w exactly, so the implementation must wrap.

Sizing the table

The expected chain length is n/m, and the analysis is only useful when m is close to n. A table that grows by doubling keeps m within a factor of two of n, so the expected chain length stays between one half and one, and lookups stay constant. A table that grows by a fixed increment rehashes on every few insertions and pays Θ(n) each time, which is the amortization argument from dynamic arrays applied to rehashing.

Rehashing requires a new function, not just a larger table. Keeping the same a while doubling m changes only the shift, which preserves the family membership for the new output size but does not give a fresh independent choice. For the guarantee to hold across the rehash, the new function must be drawn independently of the old one, because the adversary’s key set is now conditioned on the old function having been in use.

The distinction matters in the analysis of the whole sequence of operations. The expected cost of a lookup is constant for a fixed function and a fixed table size; over a sequence of insertions with rehashes, the expectation is over all the functions chosen, and linearity gives the same constant as long as each rehash draws independently. Drawing a fresh seed at each rehash is cheap and makes the argument valid without extra work.

The connection to the rest of the cluster is direct: the bounded draws that choose a come from Unbiased Random Integers from a Finite Random Source, and the two-level construction is an existence argument of the kind described in The Probabilistic Method, converted into a data structure by rebuilding the buckets that fail.