Universal Hashing
You'll learn how to avoid predictable collisions by randomly choosing your hash function each time you create a hash table.
The Problem with Fixed Hash Functions
Up until now, you've seen hash functions like the division method or polynomial rolling hash. These are deterministic—given the same input, they always produce the same output. While that sounds good, it creates a vulnerability: if someone (or some dataset) knows your hash function, they can craft inputs that all collide, degrading your hash table to a slow linked list.
The Core Idea
Universal hashing solves this by picking a hash function randomly from a large family of functions every time you initialize a hash table. Even if an adversary knows your family of functions, they can't predict which one you chose, so they can't engineer worst-case collisions.
Think of it like a lock with many possible key patterns: even if someone knows the lock model, they don't know which specific key you're using.
How It Works
- Define a family of hash functions (not just one function)
- At runtime, randomly select one function from this family when creating your hash table
- The family is designed so that for any two distinct keys, the probability they collide is low (typically ≤ 1/m, where m is table size)
This guarantee ensures good average-case performance across all possible choices from the family, regardless of input data.
Why It Matters
You're no longer at the mercy of unlucky data patterns. By randomizing the hash function, you gain probabilistic guarantees: collisions become unlikely on average, keeping operations fast.
Key Takeaway: Universal hashing randomly selects from a family of hash functions to protect against worst-case collision patterns and guarantee good average performance.