Universal and Perfect Hashing

Eight addresses, one bucket

A server tracks its open connections in a hash table. The key is the address of each connection's buffer, the value is the connection, and the table has $m = 8$ buckets with a chain of entries in each. The hash function is the textbook one, $h (x) = x mod 8$ . Tonight the allocator hands out these eight addresses:

$S = [104, 232, 368, 416, 592, 744, 880, 968] .$

Every one of them is a multiple of 8, because allocators align buffers. So every one lands in bucket 0:

h(x) = x mod 8 on S: one chain of eight entries (address:connection), seven empty buckets.

This is the dictionary problem: keep a set of $n$ keys from a universe $U = {0, \dots, u - 1}$ under insert, delete and lookup. In a chained table, a lookup of $x$ walks the chain of bucket $h (x)$ , so we count key examinations: one per entry the lookup compares with $x$ . A successful lookup of the $j$ -th entry of a chain costs $j$ . Here the eight lookups cost $1 + 2 + \dots + 8 = 36$ , an average of 4.5. For $n$ keys in one chain it is $(n + 1) / 2$ per lookup and $Θ (n^{2})$ for all of them. A table was supposed to give $O (1)$ .

S = [104, 232, 368, 416, 592, 744, 880, 968]

def buckets(keys, h, m):
    out = [[] for _ in range(m)]
    for x in keys:
        out[h(x)].append(x)
    return out

def lookup_costs(keys, h, m):
    """Key examinations of a successful lookup of each key: its position in its chain."""
    table = buckets(keys, h, m)
    return [table[h(x)].index(x) + 1 for x in keys]

assert buckets(S, lambda x: x % 8, 8)[0] == S
assert sum(lookup_costs(S, lambda x: x % 8, 8)) == 36
assert all(hash(x) == x for x in S)       # CPython hashes a small int to itself

The last line matters. Python randomizes the hash of strings and bytes on every run, but a small integer hashes to itself. A table built on hash(x) % 8 is exactly the table in the figure.

A better fixed function?

The obvious repair is a cleverer function: multiply by a large odd constant, mix the bits, take a prime modulus. Each of these fixes this key set. None of them fixes every key set.

Theorem (every fixed function has a bad key set). If $u > (n - 1) m$ , then for every function $h : U \to {0, \dots, m - 1}$ some bucket receives at least $n$ keys of $U$ .

Proof. The $m$ buckets split the $u$ keys. If every bucket received at most $n - 1$ of them, there would be at most $(n - 1) m < u$ keys in total. ∎

So an adversary who knows $h$ inserts $n$ keys from that bucket, and every lookup costs $Θ (n)$ . The adversary need not even be malicious. Aligned addresses, IDs issued in steps of 1000 and timestamps rounded to the minute all look like a chosen key set to some function. The waste is in the order of events: the function was fixed before the keys were chosen, so the keys can be chosen to fit it.

The model: who moves first

Swap the order. The adversary picks the key set $S$ first. Then the table flips coins and draws its function $h$ at random from a family $H$ , and the adversary never sees which one it got. The cost is key examinations, and a bound is expected: over the table's coins, for every key set. No assumption is made about the keys being random.

That is the meaning of "expected" that module 01 used for quickselect. There the coin chose the pivot and the input was arbitrary. Here the coin chooses the function and the key set is arbitrary.

The same keys under a random function

Here is a family to draw from. Pick a prime $p$ larger than every key, draw $a$ from ${1, \dots, p - 1}$ and $b$ from ${0, \dots, p - 1}$ , and use

$h_{a, b} (x) = ((a x + b) mod p) mod m .$

This is the Carter–Wegman family. With $p = 1009$ , suppose the coins give $a = 71$ and $b = 29$ . The eight addresses land in buckets 6 5 4 0 4 1 0 1:

h(x) = ((71x + 29) mod 1009) mod 8 on S: three chains of two, two of one, three empty.

Three pairs of keys collide: $(368, 592)$ , $(416, 880)$ and $(744, 968)$ . The eight lookups cost 11 examinations, an average of 1.375.

def make_hash(a, b, p, m):
    return lambda x: ((a * x + b) % p) % m

def colliding_pairs(keys, h):
    return [(keys[i], keys[j]) for i in range(len(keys)) for j in range(i + 1, len(keys))
            if h(keys[i]) == h(keys[j])]

h71 = make_hash(71, 29, 1009, 8)
assert [h71(x) for x in S] == [6, 5, 4, 0, 4, 1, 0, 1]
assert colliding_pairs(S, h71) == [(368, 592), (416, 880), (744, 968)]
assert len(colliding_pairs(S, lambda x: x % 8)) == 28
assert sum(lookup_costs(S, h71, 8)) == 11

One draw proves nothing, of course. The claim is about the draw: whatever eight keys the adversary had chosen, the expected number of colliding pairs is at most $(\binom{8}{2}) / 8 = 3.5$ , and the expected average lookup is at most $1 + 7 / 16 = 1.4375$ . The next two sections prove it.

Universal families

Invariant (universality)

A family $H$ of functions $U \to {0, \dots, m - 1}$ is universal if for every pair of distinct keys $x \neq y$ , ${Pr}_{h \in H} [h (x) = h (y)] \leq 1 / m$ , over the random choice of $h$ .

The quantifiers carry the whole idea. The bound holds for every pair, so it holds for the pairs in whatever set the adversary chose. The probability is over the function, which is drawn after the keys.

Theorem (expected chain length). Let $h$ be drawn from a universal family, $S$ any set of $n$ keys and $x$ any key. The expected number of other keys of $S$ in $x$ 's bucket is at most $(n - 1) / m$ if $x \in S$ , and at most $n / m$ if not. So a lookup costs at most $1 + n / m$ key examinations in expectation, and $O (1)$ when $m = Θ (n)$ .

Proof. For each $y \in S$ other than $x$ , let $I_{y} = 1$ if $h (y) = h (x)$ and 0 otherwise. By universality, $E [I_{y}] = Pr [h (y) = h (x)] \leq 1 / m$ . The number of keys sharing $x$ 's bucket is $\sum_{y} I_{y}$ , and by linearity of expectation its expectation is at most $1 / m$ times the number of terms. ∎

Linearity needs no independence: the events $h (y) = h (x)$ can depend on each other in any way. That is why a condition on pairs is enough for chain lengths. The same sum over all pairs gives $E [colliding pairs] \leq (\binom{n}{2}) / m$ . For a successful lookup averaged over the keys, each key examines itself plus the keys inserted before it in its chain, which is half the pairs on average: $1 + (n - 1) / (2 m)$ , just under 1.5 when $m = n$ .

Why Carter–Wegman is universal

Theorem (Carter–Wegman). If $p$ is prime and every key is below $p$ , the family $h_{a, b} (x) = ((a x + b) mod p) mod m$ with $a \in {1, \dots, p - 1}$ and $b \in {0, \dots, p - 1}$ is universal.

Proof. Fix keys $x \neq y$ and look first at the values before the final $mod m$ :

$r = (a x + b) mod p, s = (a y + b) mod p .$

Given $r$ and $s$ , we can solve for $a$ and $b$ in arithmetic mod $p$ : $a = (r - s) (x - y)^{- 1}$ and $b = r - a x$ . So the map $(a, b) \mapsto (r, s)$ is one-to-one, and $a \neq 0$ exactly when $r \neq s$ . The family has $p (p - 1)$ members and there are $p (p - 1)$ ordered pairs of distinct residues, so the map is a bijection onto them. A random $(a, b)$ therefore gives a uniformly random pair of distinct residues $(r, s)$ .

Now $x$ and $y$ collide when $r \equiv s (\mod m)$ . For a fixed $r$ , the values $s \neq r$ in ${0, \dots, p - 1}$ with $s \equiv r (\mod m)$ are $r \pm m, r \pm 2 m, \dots$ , and there are at most $⌈ p / m ⌉ - 1 \leq (p - 1) / m$ of them. Out of the $p - 1$ equally likely values of $s$ , at most $(p - 1) / m$ collide, so $Pr [h (x) = h (y)] \leq 1 / m$ . ∎

The step not to skip is the inverse $(x - y)^{- 1}$ . It exists because $p$ is prime and $0 < | x - y | < p$ . That is why $p$ must be prime and larger than every key.

The count can be checked exhaustively on a small prime. With $p = 101$ and $m = 8$ , every pair collides under exactly 1176 of the 10,100 functions, whatever the pair. The proof predicts this: the count depends only on how many residue pairs share a class mod 8.

from fractions import Fraction

def collision_rate(x, y, p, m):
    hits = sum(1 for a in range(1, p) for b in range(p)
               if ((a * x + b) % p) % m == ((a * y + b) % p) % m)
    return Fraction(hits, (p - 1) * p)

rates = {collision_rate(x, y, 101, 8) for x, y in [(3, 11), (3, 91), (19, 27), (35, 99), (0, 64)]}
assert rates == {Fraction(1176, 10100)} and Fraction(1176, 10100) <= Fraction(1, 8)

Predict: use

h (x) = (a x + b) mod 1000

with random

a, b

, on keys that are multiples of 1000. How long are the chains?

One chain holds everything, for every choice of $a$ and $b$ : $a \cdot 1000 k \equiv 0$ , so every key goes to bucket $b$ . With a composite modulus, $x - y$ has no inverse, the bijection is gone, and so is universality. Randomness alone doesn't help. It has to be spread by arithmetic that can't be cancelled.

assert all(len({(a * 1000 * k + b) % 1000 for k in range(1, 6)}) == 1
           for a in (3, 7, 999) for b in (0, 5, 17))

Implementation

A chained table draws $a$ and $b$ once, when it is created, from a prime such as $p = 2^{61} - 1$ (larger than any 60-bit key). A lookup is a walk along one chain:

P61 = (1 << 61) - 1

def get(table, h, x):
    """Return (value, key examinations) for key x, or (None, examinations) if it is absent."""
    examined = 0
    for key, value in table[h(x)]:
        examined += 1
        if key == x:
            return value, examined
    return None, examined

h = make_hash(71, 29, 1009, 8)
table = [[] for _ in range(8)]
for x, name in zip(S, ["c1", "c2", "c3", "c4", "c5", "c6", "c7", "c8"]):
    table[h(x)].append((x, name))
assert get(table, h, 880) == ("c7", 2)
assert h(0) == 5 and get(table, h, 0) == (None, 1)     # an absent key walks the whole chain of 232

To keep $m = Θ (n)$ as keys arrive, the table doubles $m$ when $n$ exceeds it and draws a new function for the new size. Module 07 shows that the doublings cost $O (1)$ amortized per insert.

An expectation, not a promise

Predict: with a universal family and

m = n

, is every lookup

O (1)

No. The bound is on the expectation over the draw. A particular draw can have a long chain, and on the measured keys below some draws cost more than 3 examinations per lookup on average, while the typical draw costs about 1.25.

Universality controls only pairs, so it controls only the expectation of chain lengths. Stronger families control more. A family is $k$ -wise independent if the hash values of any $k$ distinct keys are uniform and independent. A random polynomial of degree $k - 1$ mod $p$ , reduced mod $m$ , comes close to it. Higher $k$ bounds higher moments of chain lengths, and with them the longest chain. That is stated here, not proved.

For a static set, one that is built once and then only queried, we can do better than any expectation: a worst case of two reads.

Perfect hashing for a set that never changes

Fredman, Komlós and Szemerédi (FKS) build a two-level table:

Level 1: draw $h$ from a universal family into $m = n$ buckets. Bucket $i$ receives $n_{i}$ keys.
Level 2: bucket $i$ gets its own table of $n_{i}^{2}$ slots and its own function $h_{i}$ , redrawn until no two of its keys share a slot.

A lookup of $x$ reads bucket $h (x)$ 's header (its $h_{i}$ and where its table starts), then one slot of that table. If $x$ is in the set, it is in that slot. Two reads, in the worst case.

Two lemmas make it work. The first says why a squared table is collision-free often enough. With $h_{i}$ universal into $n_{i}^{2}$ slots, $E [colliding pairs] \leq (\binom{n_{i}}{2}) / n_{i}^{2} < 1 / 2$ . By Markov's inequality, a draw has no collision with probability more than $1 / 2$ , so a bucket needs fewer than 2 draws in expectation.

The second says why the squares add up to linear space. A bucket of $n_{i}$ keys has $(\binom{n_{i}}{2})$ colliding pairs and $n_{i}^{2} = n_{i} + 2 (\binom{n_{i}}{2})$ , so

$\sum_{i} n_{i}^{2} = n + 2 C, C = number of colliding pairs at level 1 .$

Universality gives $E [C] \leq (\binom{n}{2}) / n = (n - 1) / 2$ , so $E [\sum n_{i}^{2}] < 2 n$ . By Markov, $Pr [\sum n_{i}^{2} > 4 n] < 1 / 2$ . Redraw level 1 until $\sum n_{i}^{2} \leq 4 n$ , which takes fewer than 2 draws in expectation, and the whole table has $n$ headers plus at most $4 n$ slots: $5 n$ in all.

On $S$ , level 1 is $h_{71, 29}$ with $m = n = 8$ , the table from before. It has $\sum n_{i}^{2} = 4 + 4 + 4 + 1 + 1 = 14 \leq 32$ . For level 2, try the candidate functions (1,0) (2,3) (5,1) (7,4) … in order, each with the same $p$ and a table of $n_{i}^{2}$ slots. Bucket 0 holds 416 and 880. Under $(1, 0)$ both are $0 mod 4$ and share slot 0, so the bucket needs a second try, and $(2, 3)$ puts them in slots 3 and 2.

Level 1 is the random table from before. In the two level-2 panels the rows are the 4 slots of bucket 0's own table: its first function puts both keys in slot 0, and its second separates them.

The other buckets go the same way. Bucket 1 (744, 968) needs three tries and lands in slots 2 and 1 under $(5, 1)$ . Bucket 4 (368, 592) takes $(2, 3)$ on its second try. The two single keys take $(1, 0)$ at once. Total space: 8 headers and 14 slots, 22 cells, against the guarantee of $5 n = 40$ .

CAND = [(1, 0), (2, 3), (5, 1), (7, 4), (11, 2), (13, 6)]

def second_level(bucket, p, candidates):
    """First candidate that is one-to-one on the bucket: (a, b, tries, slots)."""
    size = len(bucket) ** 2
    for tries, (a, b) in enumerate(candidates, 1):
        slots = [make_hash(a, b, p, size)(x) for x in bucket]
        if len(set(slots)) == len(slots):
            return a, b, tries, slots

level1 = buckets(S, h71, 8)
assert sum(len(bk) ** 2 for bk in level1) == 14 == 8 + 2 * len(colliding_pairs(S, h71))
rows = [(i, second_level(bk, 1009, CAND)) for i, bk in enumerate(level1) if bk]
assert rows == [(0, (2, 3, 2, [3, 2])), (1, (5, 1, 3, [2, 1])), (4, (2, 3, 2, [3, 2])),
                (5, (1, 0, 1, [0])), (6, (1, 0, 1, [0]))]
assert 8 + 14 == 22 <= 5 * 8

Predict: why give bucket

i

a table of

n_{i}^{2}

slots? Wouldn't

n_{i}

be enough?

With $n_{i}$ slots the expected number of colliding pairs is up to $(\binom{n_{i}}{2}) / n_{i} = (n_{i} - 1) / 2$ . That is at least 1 once $n_{i} \geq 3$ , so a collision-free draw gets rare as buckets grow, and even two keys in two slots collide half the time. The square makes the expectation below $1 / 2$ for every bucket, and the level-1 lemma shows the squares still sum to $O (n)$ .

Complexity

All costs count key examinations or slot reads. "Expected" is over the table's own coins, for every key set.

Structure	Lookup	Space	Build or update
any fixed $h$	$Θ (n)$ on some key set (pigeonhole)	$m$ buckets	$Θ (n)$ per insert on that set
chaining, universal $h$	expected $\leq 1 + n / m$	$m + n$	expected $O (1)$ per operation with $m = Θ (n)$ , plus resizing, $O (1)$ amortized
FKS, static set	2 reads, worst case	$\leq 5 n$ cells	expected $O (n)$ : fewer than 2 level-1 draws and fewer than 2 draws per bucket

Neither can be beaten by more than a constant: every lookup reads at least one cell, and storing $n$ keys takes $n$ cells. What randomness buys is the guarantee for every key set. The adversary can still choose the keys. It just can't choose them to fit a function it never sees.

Measure the claim

Take the keys $8192 i$ for $i < n$ , which are aligned even more cruelly than the addresses, and a table of $m = n$ buckets. For each of 40 seeds (0 to 39), draw a Carter–Wegman function with $p = 2^{61} - 1$ , look up every key and record the average examinations per lookup. Then compare with $x mod n$ :

$n$	universal: mean over seeds	universal: median	worst seed	$x mod n$
256	1.35	1.24	2.77	128.5
512	1.38	1.20	2.89	256.5
1,024	1.46	1.27	3.61	512.5
2,048	1.43	1.25	3.43	1,024.5

import random

def profile(n, seeds):
    keys = [8192 * i for i in range(n)]
    per_seed = []
    for seed in seeds:
        rng = random.Random(seed)
        h = make_hash(rng.randrange(1, P61), rng.randrange(P61), P61, n)
        per_seed.append(sum(lookup_costs(keys, h, n)) / n)
    per_seed.sort()
    return sum(per_seed) / len(per_seed), per_seed[len(per_seed) // 2], per_seed[-1]

table = {n: profile(n, range(40)) for n in (256, 512, 1024, 2048)}
assert [round(v, 2) for v in table[1024]] == [1.46, 1.27, 3.61]
assert all(mean <= 1.5 and median <= 1.3 and worst < 3.7 for mean, median, worst in table.values())
assert max(worst for _, _, worst in table.values()) > 3
assert [sum(lookup_costs([8192 * i for i in range(n)], lambda x, n=n: x % n, n)) / n
        for n in (256, 512)] == [128.5, 256.5]

The fixed function grows as $(n + 1) / 2$ because every key is a multiple of $n$ . The universal column stays flat near the bound of $1 + (n - 1) / (2 n) < 1.5$ . The spread between seeds is wide: the median is about 1.25, and one seed in forty costs more than twice that. On aligned keys the Carter–Wegman family has a heavy tail, so a mean of 40 samples can land above 1.5 without contradicting anything. A sample mean is not an expectation. The theorem promises the expectation, and the median shows what a typical table costs.

A problem that looks different

A payments partner sends a feed of a million transaction IDs, and you must report whether any ID appears twice. The partner is not trusted and can choose the IDs after reading your source code. Sorting settles it in $n \log n$ comparisons. Is there a method that is expected linear for every feed the partner could send? This lesson has the idea, and it isn't solved here. The lab's last problem is a different one.

Practise

In the lab you insert keys into chains one frame at a time and check that every entry sits in the bucket its function names, trace a two-level table on a new key set before running it, build a growing dictionary that draws a fresh function each time it doubles, measure collisions and lookup costs against the proofs with your own counts, and finish with a problem that doesn't say what it is.

Recap

You can now: show that every fixed hash function has a bad key set; prove Carter–Wegman universal with the inverse of $x - y$ mod $p$ ; bound the expected chain length by linearity; and build a two-level table for a static set with two reads per lookup and at most $5 n$ cells.
Invariant: for every pair $x \neq y$ , ${Pr}_{h} [h (x) = h (y)] \leq 1 / m$ . The adversary picks the keys, and then the coin picks $h$ .
Complexity achieved: expected $1 + n / m$ examinations per operation for every key set, and 2 reads in the worst case for a static set in at most $5 n$ cells, against $Θ (n)$ per lookup for a fixed function on its bad key set.
Failure mode: a fixed or exposed function, or a composite modulus, so that keys can be chosen, or simply happen, to collide. Integer keys through hash(x) % m in CPython are the everyday case.
In real software: CPython randomizes the hash of str and bytes per process with SipHash (PEP 456), controlled by PYTHONHASHSEED, so that a remote attacker can't precompute colliding strings. Integers are not randomized.
Retrieval: module 01's quickselect runs in expected $O (n)$ for every input. What plays the part of the random pivot here, and what plays the part of the input?

Check yourself

Why is $((a x + b) mod p) mod m$ universal, and where exactly does the proof use that $p$ is prime and larger than every key?
An attacker can observe your function after the table is built and keeps inserting keys. What breaks, and what would you change?
For a static set of $10^{5}$ keys, compare chaining with a universal function, FKS, and a sorted array with binary search: reads per lookup, worst case, and space.

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.

Universal and Perfect Hashing

Eight addresses, one bucket

A better fixed function?

The model: who moves first

The same keys under a random function

Universal families

Why Carter–Wegman is universal

Implementation

An expectation, not a promise

Perfect hashing for a set that never changes

Complexity

Measure the claim

A problem that looks different

Practise

Recap

Check yourself

Now try it yourself