universal hashing
A hash table stores items in slots picked by a hash function, and trouble starts when many items collide into the same slot. For any one fixed hash function, an adversary who knows it can choose keys that all collide, wrecking performance. Universal hashing escapes this by choosing the hash function at random from a carefully designed family at the start, so no fixed set of keys can be made to collide too often — the adversary cannot aim at a function you have not picked yet.
Precisely: a family H of hash functions mapping keys into m slots is called universal if, for every pair of distinct keys x and y, when h is chosen uniformly at random from H, the collision probability Pr[h(x) = h(y)] is at most 1/m. That single guarantee is exactly what you need. By an indicator argument, the expected number of keys colliding with a given key, among n stored keys, is at most (n - 1)/m, so with a table of size m = O(n) each lookup touches an expected O(1) items — constant expected time, regardless of which keys are inserted. A standard universal family: pick a prime p larger than any key, choose random a in {1,...,p-1} and b in {0,...,p-1}, and let h(x) = ((a x + b) mod p) mod m; one can prove any two distinct keys collide with probability at most 1/m over the random a, b.
Universal hashing matters because it makes hash-table performance a property of your random choice rather than a hope about the input, defeating worst-case and even adversarial inputs in expectation. It underlies perfect hashing, fingerprinting, and many randomized data structures. The honest caveat: the O(1) is expected over the choice of hash function, not a per-operation guarantee — a particular function can still produce a long chain — and the guarantee holds only if the function is genuinely chosen at random and kept secret from whoever supplies the keys. Reusing a fixed function reopens the adversarial door.
With the family h(x) = ((a x + b) mod p) mod m and m = 1000 slots, inserting 1000 keys gives each key an expected (1000 - 1)/1000 < 1 other key in its slot — so chains stay short on average for any keys at all, because the shortness comes from random a, b, not from assuming the keys are random.
Random function, not random keys: collisions stay rare for any adversary's input.
Universality bounds collision probability over the random choice of function, so the O(1) lookup is an expectation, not a worst-case guarantee. It only holds if the function is chosen at random and not revealed to an adversary who can then pick colliding keys.