THE UNIVERSAL HASHING pick the hash at random, bound the collisions
An adversary who knows your hash can jam every key into one bucket. Universal hashing defeats that by choosing the hash randomly from a family: h = ((a·k + b) mod p) mod m with random a, b and prime p. Then for any two keys, the collision chance is at most 1/m — provable, no matter the input. Here a=3, b=7 sends key 42 to bucket 5.
THE TECHNIQUE h = ((a·k + b) mod p) mod m
The demo runs the Carter-Wegman hash on a couple of keys; the guarantee is over the random a,b: live demo
HISTORY & CREDIT Carter & Wegman · 1979
“A good fixed hash is enough.” — against an adaptive adversary only randomization gives a worst-case bound; that is why real hash maps randomize their seed. cited
the family · h(k) = ((ak+b) mod p) mod m, random a,b. the bound · for any k₁≠k₂, Pr[collision] ≤ 1/m — over the choice of hash. 1979 · Larry Carter & Mark Wegman, “Universal classes of hash functions.”
Randomize the hash, bound the worst case. probability
RECOMMEND FOR I-13 one member, on the compiler
On i-13, one member (a=3,b=7,p=1000003) sends 42→5 and 43→8; the bound lives over random a,b:
$ i13 run hs_universal.i13
RUN OK · 49 step(s) · peak stack 6
h42 = 5
h43 = 8
in_range = 1
differs = 1
Recommend as a NULL — a probabilistic bound (B41 adversary) + approximation. The 1/m guarantee is over randomness and defeats an adversary — the crypto/adversary gate. A fixed member is just arithmetic (B40). No coordinate-independent extra output two mechanisms differ on. NULL.