Universal Hashing and Perfect Hashing

In 2011, the same hash collision vulnerability hit Python, PHP, Ruby, Java, and several other languages simultaneously. Attackers discovered that submitting carefully crafted HTTP POST data — with parameter names all hashing to the same slot — could cause web servers to spend seconds processing a single request. The fix was not changing the hash function; it was randomising the hash function at startup. This is universal hashing in practice.

Universal hashing is the theoretical foundation for this defence: if the hash function is chosen randomly from a 2-universal family, no adversary can reliably cause collisions without knowing which function was selected. The adversary's best attack strategy — crafting inputs that collide under the fixed function — is defeated.

Why Fixed Hash Functions Fail

Any deterministic hash function h can be attacked. Given h, an adversary can find n keys that all hash to the same slot — making every operation O(n). This is a real attack: hash DoS attacks against web servers were widely exploited before randomisation became standard (Crosby & Wallach, 2003).

Universal Hash Family Construction

The polynomial hash family for strings is 2-universal: choose random a,b modulo prime p > m: h_{a,b}(x) = (ax + b) mod p mod m

import random

class UniversalHash:
    """2-universal hash family for integers."""
    def __init__(self, m: int, prime: int = 10**9+7):
        self.m = m
        self.p = prime
        self.a = random.randint(1, prime - 1)
        self.b = random.randint(0, prime - 1)

    def hash(self, x: int) -> int:
        return (self.a * x + self.b) % self.p % self.m

    def rehash(self):
        """Pick a new random function from the family."""
        self.a = random.randint(1, self.p - 1)
        self.b = random.randint(0, self.p - 1)

# Demonstrate: collision probability ≈ 1/m
h = UniversalHash(m=100)
collisions = sum(1 for _ in range(10000)
                 if h.hash(42) == h.hash(99))
print(f'Collision probability ≈ {collisions/10000:.3f} (expected ≤ {1/100:.3f})')

Python's Hash Randomisation

Since Python 3.3, Python randomises its string/bytes hash function at startup (PYTHONHASHSEED). This is exactly universal hashing in practice — prevents hash DoS attacks.

import os
# Python uses random seed at startup
print(hash('hello'))  # Different every run unless PYTHONHASHSEED set
print(os.environ.get('PYTHONHASHSEED', 'random'))  # 'random' = randomised

# Stable hashing when needed (e.g., caching)
import hashlib
stable = int(hashlib.md5(b'hello').hexdigest(), 16) % (10**9)
print(stable)  # Same every run

Perfect Hashing — O(1) Worst Case

For a static set of n keys, FKS (Fredman-Komlós-Szemerédi) perfect hashing achieves O(1) worst-case lookup with O(n) space: 1. Hash n keys into n/2 buckets (first level, some collisions expected) 2. For each bucket with k_i keys, use a second-level table of size k_i² — guarantees no collisions with high probability

Total space: O(n) expected. Build time: O(n) expected. Lookup: O(1) worst case.

Used in compilers (keyword lookup), databases (static index), and network packet classification.

Frequently Asked Questions