Universal hashing — probabilistic guarantee: Question bank

Symbols you need (read this first)

Before the traps, here is every symbol used on this page, in plain words. Nothing below assumes anything not listed here.

Definition The cast of symbols

$U$ — the universe: the (huge) set of all possible keys we might ever hash (e.g. all 64-bit integers).
$m$ — the table size: the number of slots/buckets, numbered $0, 1, \dots, m - 1$ . A key's hash is which of these $m$ slots it goes to.
$n$ — the number of keys currently stored in the table.
$α = \frac{n}{m}$ — the load factor: keys per slot on average. If $n = 50$ keys sit in $m = 100$ slots, $α = 0.5$ — the table is "half loaded". This ratio, not $n$ alone, controls how long chains get.
$h$ — a single hash function, mapping a key to a slot in ${0, \dots, m - 1}$ .
$H$ — a family (a whole set) of hash functions; universal hashing picks one $h$ from $H$ at random.
$p$ — a prime number chosen larger than the biggest key; it is the modulus in the concrete family.
$H_{a, b}$ — the concrete family $h_{a, b} (k) = ((ak + b) mod p) mod m$ , with random $a \in {1, \dots, p - 1}$ , $b \in {0, \dots, p - 1}$ .

Figure — Universal hashing — probabilistic guarantee

The next figure shows where the extra $1/ p$ comes from when $m$ does not divide $p$ — the trap in several questions below.

True or false — justify

A family is universal if each single key

x

lands in a uniformly random slot.

False. Universality is a statement about pairs

x \neq = y

colliding, not about one key's marginal distribution. A family can spread single keys perfectly yet still fail the pair bound. See Universal hashing — probabilistic guarantee for the exact definition.

"Universal hashing assumes the input keys are random."

False. The keys may be fully adversarial; the only randomness is our secret choice of

h

from

H

. Read the definition as "for fixed $x, y$ , over random $h$ ."

Pr [h (x) = h (y)] \leq 1/ m

for one specific pair, the family is universal.

False. The bound must hold for every distinct pair

x \neq = y

in the universe simultaneously; one good pair proves nothing.

The indicator

X_{x y}

(recall:

1

x, y

collide, else

0

) can be added across all

y \neq = x

only if the collisions are independent.

False — adding 0/1 indicators is always allowed. What we then take the expectation of uses linearity, which also needs no independence. Independence is never required anywhere in this analysis.

Linearity of expectation was used because the collision events

X_{x y}

are independent.

False — it was used precisely because they are not independent. Linearity

E [\sum] = \sum E

needs no independence, which is why it fits here. See Linearity of expectation.

With

m = Θ (n)

, worst-case search time in a universal-hashed chained table is

O (1)

False. Expected time is

O (1 + α) = O (1)

(with

α = n / m

constant); the worst case (all keys chain into one slot) is still

O (n)

. The guarantee is over coin flips, not adversarial inputs.

The family

h_{a, b} (k) = ((ak + b) mod p) mod m

is exactly universal for any

m

False. It is exactly universal (

Pr \leq 1/ m

) only when

m ∣ p

; otherwise buckets are uneven and it is almost-universal,

Pr \leq 1/ m + 1/ p

. See Modular arithmetic and primes.

Allowing

a = 0

h_{a, b}

is harmless.

False. With

a = 0

we get

h (k) = (b mod p) mod m

— a constant ignoring the key, so every pair collides with probability 1. That is why

a \in {1, \dots, p - 1}

Because

p

is huge, the extra

1/ p

in the almost-universal bound can be ignored in practice.

True. For a realistic prime

p \approx 2^{31}

1/ p

is astronomically smaller than

1/ m

, so the guarantee is effectively

1/ m

. The caveat matters for proofs, not performance.

Expected chain length seen by a key

x

already in the table is

\leq n / m

False. If

x

is present it also counts itself: expected length is

\leq 1 + \frac{n - 1}{m}

. The bare

n / m

(or

\frac{n - 1}{m}

) is for a key not yet inserted.

Spot the error

"Random hashing means collisions never happen, so search is always

O (1)

Collisions certainly still happen; universality only makes their expected count small (

\leq α = n / m

). It bounds an average, not a guarantee of zero.

"Since

E [X] \leq \frac{n - 1}{m}

, some search must cost at most

\frac{n - 1}{m}

The average being small does not bound the maximum of a fixed run — an adversary could still be unlucky-for-you on a bad coin flip. Expectation bounds the long-run average over the random

h

E [X_{x y}] = Pr [h (x) = h (y)]

only if

X_{x y}

is independent of other indicators."

No independence is needed. For any 0/1 variable,

E [X_{x y}] = 1 \cdot Pr [X_{x y} = 1] + 0 \cdot Pr [X_{x y} = 0] = Pr [X_{x y} = 1]

"We do

mod p

then

mod m

just to be safe; one mod would do."

The

mod p

(with

p

prime) is the universality engine: it makes

(a, b) \mapsto (a x + b, a y + b)

a bijection so distinct keys get distinct residues. Dropping it destroys the collision bound. The

mod m

merely fits the answer into the

m

table slots.

p

can be any number bigger than the largest key."

It must be a prime larger than the max key. Primality is what makes

Z_{p}

a field so the linear map is invertible; a composite

p

breaks the bijection argument. See Modular arithmetic and primes.

"The load factor

α = n / m

can safely grow without bound."

Then expected cost

O (1 + α)

grows too. To keep operations

O (1)

we rehash into a larger table once

α

exceeds a threshold. See Load factor and rehashing.

"Open addressing makes universal hashing unnecessary."

The choice of hash function and the collision-resolution scheme are independent concerns; open addressing still needs a good

h

, and adversaries still exist. See Hashing — chaining vs open addressing.

Why questions

Why can a fixed hash function always be defeated?

Once the adversary knows

h

, they compute a set of keys that all map to one slot, forcing

O (n)

per operation. Knowledge of

h

is the weapon. See Adversarial inputs and randomized algorithms.

Why does hiding the random choice of

h

actually help?

The adversary must fix their keys before seeing your coin flips, so they can't tailor collisions to your specific

h

— the pair-collision bound then holds regardless of their keys.

Why is the guarantee stated over pairs rather than over the whole key set?

Because the analysis sums indicators

X_{x y}

over other keys

y

, and each term only needs the pairwise bound

Pr [h (x) = h (y)] \leq 1/ m

— a per-pair fact is enough to bound the total via linearity.

Why does

m ∤ p

add exactly the

+ 1/ p

term?

The

p

residues split into

m

buckets that cannot all be equal, so some buckets hold

⌈ p / m ⌉

residues instead of

⌊ p / m ⌋

. The collision chance becomes

\frac{⌈ p / m ⌉ - 1}{p - 1}

, which upper-bounds to

\frac{1}{m} + \frac{1}{p}

— the

\frac{1}{p}

is the "leftover" from uneven splitting (see figure s02).

Why must

p

be prime specifically (not just large)?

Z_{p}

with

p

prime, every nonzero

a

has an inverse, making

k \mapsto ak + b

a bijection; this is what guarantees distinct keys stay distinct mod

p

. Composite moduli have zero divisors that ruin this.

Why does keeping

m = Θ (n)

give

O (1)

operations?

Then

α = n / m

is a constant, so expected cost

O (1 + α) = O (1)

. It's the ratio of keys to slots, not

n

itself, that controls chain length.

Why is universal hashing a building block for perfect hashing?

Perfect hashing (FKS) uses a universal family at two levels, choosing functions with few/zero collisions, to get

O (1)

worst-case lookup on a static set. See Perfect hashing (FKS) — uses universal hashing as a building block.

Edge cases

What happens to the collision bound when

x = y

(same key)?

Undefined/irrelevant — universality only speaks of distinct keys

x \neq = y

. A key never "collides with itself"; it just maps where it maps.

When we insert the very first key into an empty table, how many collisions does it expect?

Zero. Here "

n

" means keys already present (

n = 0

before this insert), so the bound

\frac{n - 1}{m}

... — be careful: use the not-yet-inserted form

\frac{n}{m} = \frac{0}{m} = 0

. The first key always lands in an empty slot.

When

m ∣ p

exactly, what does the bound become?

The buckets are perfectly even (

p / m

residues each), so the extra term vanishes and the family is exactly universal:

Pr [h (x) = h (y)] \leq 1/ m

m = 1

(a single slot), is the family still "universal"?

Trivially yes:

Pr [h (x) = h (y)] \leq 1/1 = 1

always holds, but the table is useless since every key shares one

O (n)

chain. Universality is a ceiling, not a promise of usefulness.

m \to \infty

with

n

fixed, what happens to expected collisions?

The bound

\frac{n - 1}{m} \to 0

, so expected chain length approaches 1 — you're paying huge memory to almost eliminate collisions.

What if the adversary sees your

h

after it's chosen (e.g. via a side channel)?

The guarantee collapses — universality assumes the choice stays secret. A leaked

h

reduces you to the fixed-function case they can defeat.

Connections

Universal hashing — probabilistic guarantee
Linearity of expectation
Modular arithmetic and primes
Load factor and rehashing
Hashing — chaining vs open addressing
Adversarial inputs and randomized algorithms
Perfect hashing (FKS) — uses universal hashing as a building block