Universal Hashing, in depth: Carter-Wegman, multiply-shift, tabulation, k-independence and what each application needs

Why a fixed hash function fails

Take the textbook function h(x) = x mod m with m = 1024 and insert 10,000 keys that are all multiples of 1024: record IDs allocated in pages, aligned addresses, timestamps rounded to a power of two. Every key lands in bucket 0. The chain holds 10,000 entries and every lookup is a linear scan. Choosing m prime helps with that pattern but not with others, and any fixed h with more keys than buckets has some bucket that at least |U|/m keys of the universe map to. If the input is chosen after the function is known, the worst case is always available.

The fix is to draw h after the input is fixed, or at least without the input being able to depend on it. Then a bad input for one draw is a good input for most others, and the expected cost is small for every input.

Universal, strongly universal and k-independent

Let H be a family of functions from a key universe U to buckets {0, ..., m-1}, and let h be drawn uniformly from H.

• Universal: for every pair of distinct keys x and y, Pr[h(x) = h(y)] ≤ 1/m. Pairs collide no more often than under a truly random function.
• c-approximately universal: the same with c/m. Multiply-shift is 2-approximately universal, which is good enough for almost every use.
• Strongly universal (pairwise independent): for distinct x, y and any buckets i, j, Pr[h(x) = i and h(y) = j] = 1/m². Each value is uniform, and any two values are independent.
• k-independent: any k distinct keys get independent, uniform hash values. Pairwise independence is k = 2. Higher k buys stronger concentration and is what some data structures need.

Universality is a statement about pairs, which is exactly what chaining needs. Fix a key x and a set S of n other keys. Let C_y be 1 if y collides with x. The chain x probes has expected length E[Σ C_y] = Σ Pr[h(x) = h(y)] ≤ n/m. With load factor α = n/m, a lookup costs 1 + α in expectation, for every S. Nothing about the keys was assumed; the expectation is over the draw of h alone.

Notice what this does not give. It does not bound the longest chain well (with n = m, pairwise independence alone only bounds the largest bucket by about √n), and it does not make outputs unpredictable to an observer. Those need more independence or a cryptographic function.

Carter-Wegman: the prime-field family

Pick a prime p larger than every key. Draw a uniformly from 1..p-1 and b from 0..p-1, and set h(x) = ((a·x + b) mod p) mod m. For distinct x and y, the map (a, b) → (a·x + b, a·y + b) mod p is a bijection onto pairs (r, s) with r ≠ s, because p is prime and x - y is invertible. So the pair (r, s) is uniform over the p(p-1) ordered pairs of distinct residues. The keys collide when r ≡ s mod m; for each r, at most ⌈p/m⌉ - 1 of the other residues share its class, giving Pr ≤ (⌈p/m⌉ - 1)/(p - 1) ≤ 1/m.

Dropping the condition a ≠ 0 and skipping the final mod m gives a strongly universal family into {0, ..., p-1}. In practice p = 2⁶¹ - 1 is popular because reduction modulo a Mersenne prime is a shift, a mask and an add, so no division is needed.

Multiply-shift: no division, power-of-two tables

Division is slow, and the most common bucket count is a power of two. Dietzfelbinger, Hagerup, Katajainen and Penttonen (1997) showed that for w-bit keys and m = 2^M buckets, with a a random odd w-bit number,

h_a(x) = (a * x mod 2**w) >> (w - M)

is 2-approximately universal: Pr[h(x) = h(y)] ≤ 2/m. In C with w = 64 it is one multiply and one shift, since unsigned overflow performs the mod 2⁶⁴ for free. The high bits are used because the low bits of a product depend only on the low bits of the inputs; taking the low M bits instead would reproduce the x mod m failure. For pairwise independence, multiply-add-shift with random 2w-bit a and b, h(x) = ((a·x + b) mod 2^(2w)) >> (2w - M), does the job for w-bit keys at the cost of wider arithmetic.

Simple tabulation

Simple tabulation splits a key into c characters, for example a 32-bit key into four bytes, and keeps c tables of 256 random words. The hash is the XOR of one table entry per character. It is 3-independent but not 4-independent: four keys formed from two values in each of two positions always XOR to zero, whatever the tables hold. Our run confirms it; the XOR of the four hashes was 0.

Despite that, Pătraşcu and Thorup showed in "The Power of Simple Tabulation Hashing" that it gives constant expected time for linear probing and works well for cuckoo hashing and min-wise sketches, properties that generic 3-independence does not imply. Its cost is a few table lookups that fit in L1 cache (4 KB for four 256-entry tables of 32-bit words).

Hashing strings and long keys

Variable-length keys are reduced with a polynomial. Treat the bytes s₀..s_(L-1) as coefficients and evaluate at a random point a modulo a prime p. Two different strings of the same length L give two different polynomials whose difference has fewer than L roots, so they collide with probability below L/p. Strings of different lengths need the length mixed in first (see failure modes). With p = 2⁶¹ - 1 and L = 10⁶ that is under 10⁻¹². Then hash the resulting 61-bit value into buckets with any family above. This two-stage pattern, with a precise bound at each stage, is the standard approach; the polynomial string hashing article covers the rolling variant used for substring search.

An implementation and an exact check

import random

P = (1 << 61) - 1                      # Mersenne prime

class CarterWegman:
    def __init__(self, m, rng=random):
        self.m = m
        self.a = rng.randrange(1, P)
        self.b = rng.randrange(0, P)
    def __call__(self, x):             # keys must be below P
        return ((self.a * x + self.b) % P) % self.m

class MultiplyShift:
    def __init__(self, M, w=64, rng=random):
        self.M, self.w = M, w
        self.a = rng.randrange(1, 1 << w) | 1      # random odd multiplier
        self.mask = (1 << w) - 1
    def __call__(self, x):
        return ((self.a * x) & self.mask) >> (self.w - self.M)

class Tabulation:
    def __init__(self, M, rng=random):
        self.T = [[rng.getrandbits(M) for _ in range(256)] for _ in range(4)]
    def __call__(self, x):             # 32-bit keys, one table per byte
        h = 0
        for i in range(4):
            h ^= self.T[i][(x >> (8 * i)) & 0xFF]
        return h

def string_key(s: bytes, a: int) -> int:
    h = 0
    for byte in s:                     # Horner evaluation at the random point a
        h = (h * a + byte) % P
    return h

To check the bounds rather than trust them, enumerate every seed for small parameters. For Carter-Wegman with p = 13 and m = 4, the worst pair collides with probability 0.192 against a bound of 0.25; with p = 31 and m = 8, 0.097 against 0.125. For multiply-shift with w = 8 and M = 3, the worst pair collides with probability exactly 0.25, which is the 2/m bound: the factor of two is real, not slack in the proof.

Worked run: aligned keys

The 10,000 multiples of 1024 into 1,024 buckets, one random draw each (seed 3). A truly random function would give about 48,823 colliding pairs in expectation. That is the expected ceiling for Carter-Wegman; multiply-shift's 2/m bound allows up to twice it; tabulation, being 3-independent, matches it exactly in expectation. Single draws scatter around these figures.

Tabulation's larger maximum bucket is a reminder that these keys are highly structured: only two of the four bytes vary, so only two tables contribute. Its collision count is still around the random-function figure, and one draw is one sample, so run several seeds before reading anything into a single number.

How much independence each application needs

The linear probing row is the one that catches people. A pairwise independent family is enough for chaining but can leave linear probing with logarithmic expected time, because long runs depend on how several keys cluster together, not on pairs. For sketches like count-min, pairwise independence per row is exactly what the error analysis uses.

Operational guidance

• Draw a fresh seed per table and per rebuild. If a rebuild was triggered by a bad chain, reusing the seed reproduces it.
• Use a real random source for the seed. OS randomness at startup is fine. Seeding from the clock makes the draw guessable.
• Keep the seed private. Universal guarantees assume the input does not depend on the seed. Exposed hash values, timing differences or iteration order can leak it, and a linear family's seed is far easier to recover than a keyed PRF's key. For attacker-controlled keys use a keyed PRF.
• Fix seeds where reproducibility matters. Sketches merged across machines must share the same functions, so the seed becomes configuration, versioned with the data.
• Monitor the longest chain or probe sequence. It is cheap to track and is the first signal of a bad draw, a correlated key pattern or an attack.

Failure modes

• Keys at or above p. Carter-Wegman assumes keys below p; larger keys alias modulo p and collide deterministically.
• Low bits of multiply-shift. Masking the product instead of shifting brings back the x mod m failure.
• Even multiplier. An even a throws away a bit; the code forces it odd.
• Same seed for two cuckoo functions. Correlated choices break the independence the analysis needs; see the cuckoo hashing article.
• Leading zero bytes in string keys. Plain Horner evaluation maps the bytes of "ab" and the same bytes preceded by a zero byte to the same value whatever a is. Mix in the length or append a terminator before trusting the L/p bound for strings of different lengths.
• Truncating 64-bit hashes carelessly. Bucket index from a fast mixer's low bits is fine only if the mixer is good in those bits.

Trade-offs

Multiply-shift is the fastest and is enough for chaining and most open-addressing tables in practice. Carter-Wegman with a Mersenne prime is the cleanest to reason about and gives strong universality when you need it. Simple tabulation costs a few cache-resident lookups and earns guarantees for linear probing and cuckoo hashing that its formal independence would not suggest. Higher-degree polynomials give k-independence directly at k multiplications per key. None of them is a defence against an adversary who can watch the table; that is a cryptographic problem with a cryptographic price.

What to do next

1. Run the enumeration check above for your own family and parameters and confirm the collision bound before using it.
2. Replace any fixed modular hash in your code with multiply-shift drawn at table creation, and log the longest chain.
3. If you use linear probing, switch to tabulation or a 5-independent family and measure probe lengths on your real keys.
4. For sketches, store the seeds with the sketch so merges stay valid.
5. Read the perfect hashing article to see universal families build a table with no collisions at all, and the hash table article for adversarial inputs.