Perfect Hashing
A hashing technique that guarantees O(1) worst-case lookup time for a static set of keys by using a two-level hash table structure.
Build table to visualize
Enter keys to build the table
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Imagine organizing a library where every book has a permanently reserved spot. You don't just dump books into sections; you have a specific system (Level 1) to find the shelf, and another specific system (Level 2) to find the exact slot on that shelf. Because the books never change (static set), you can spend time upfront designing this perfect system so you never have to search.
Concept
Perfect Hashing uses a two-level hashing scheme to eliminate collisions entirely:
- Level 1: Hash N keys into N primary buckets. Some collisions may occur here.
- Level 2: For each bucket i containing n_i keys, create a secondary hash table of size n_i^2. By the Birthday Paradox, a table of quadratic size allows finding a collision-free hash function with high probability.
How it Works
Construction:
- Choose a primary hash function h(x) = ((ax+b) \pmod p) \pmod N.
- Distribute all keys into primary buckets.
- For each bucket i:
- If it has keys, find a secondary hash function h_i(x) = ((a_ix+b_i) \pmod p) \pmod {n_i^2} that causes zero collisions for the keys in that bucket.
- Store the parameters (a_i, b_i) and the secondary table.
Step-by-Step Breakdown
Watch the visualization:
- Primary Distribution: Keys are hashed into the main buckets. You'll see some buckets empty, some with multiple keys.
- Secondary Construction: For buckets with collisions, a secondary table (squared size) is created. The algorithm "rolls" random hash parameters until the keys fit perfectly without overlapping.
- Lookup: To find a key, we hash it once to find the bucket, then hash it again (using the bucket's specific parameters) to find the exact slot.
When to Use
Applications:
- Static Dictionaries: Reserved keywords in a compiler.
- CD-ROM / Read-Only Data: Optimizing access when data doesn't change.
- Hardware Lookup Tables: Network routing tables where lookup speed is critical.
When NOT to Use
- Dynamic Data: If you frequently add/remove keys, rebuilding the perfect hash table is too expensive.
- Memory Constraints: The quadratic size (n^2) for secondary tables can be memory-heavy if many keys collide in the primary step (though total space is linear on average).
How to Identify
"Static set", "Worst-case O(1) lookup", "Guaranteed constant time", "Two-level hashing".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.