What is Perfect Hashing?

A technique used for a fixed set of keys where a hash function is chosen to ensure NO collisions occur, allowing for O(1) worst-case lookups.

FKS Hashing (Two-level hashing)?

A common perfect hashing scheme using a primary hash table where each bucket is itself another small hash table with its own function.

Ideal for read-only datasets like reserved keywords in a compiler, dictionary lookups, or static configuration tables.

Perfect Hashing

Perfect hashing is 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.

7 KEYS · 7 BUCKETS

LEVEL ONE

Level one: 7 keys into 7 buckets. Collisions are expected and allowed here — the bucket sizes are 0, 1, 1, 2, 2, 1, 0.

Bucket 1 holds 1 key, so its secondary table gets 1² = 1 slots. The square is what makes a collision-free hash likely enough to find by trying.

Keys

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². 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) mod p) mod 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) mod p) mod n_i² 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²) 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".

Sample Problems

Design HashMap

Although typically solved with Chaining, understanding Perfect Hashing gives insight into collision-free design.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Frequency Table

Introduction

Complexity

Time (Best)

O(1)

Time (Average)

O(1)

Time (Worst)

O(1)

Space

O(N)

Perfect Hashing Code

1class PerfectHashSet {
2    constructor(keys) {
3        this.prime = 101;
4        this.size = keys.length;
5        this.primary = new Array(this.size).fill(null);
6        this.build(keys);
7    }
8
9    hash(key, a, b, m) {
10        return ((a * key + b) % this.prime) % m;
11    }
12
13    build(keys) {
14        // 1. Primary Hash
15        this.a = Math.floor(Math.random() * (this.prime - 1)) + 1;
16        this.b = Math.floor(Math.random() * this.prime);
17        
18        const buckets = Array.from({length: this.size}, () => []);
19        for (let k of keys) {
20            const idx = this.hash(k, this.a, this.b, this.size);
21            buckets[idx].push(k);
22        }
23
24        // 2. Secondary Hash
25        for (let i = 0; i < this.size; i++) {
26            const bKeys = buckets[i];
27            if (bKeys.length === 0) continue;
28            
29            const m = bKeys.length * bKeys.length;
30            let found = false;
31            while (!found) {
32                const sa = Math.floor(Math.random() * (this.prime - 1)) + 1;
33                const sb = Math.floor(Math.random() * this.prime);
34                const slots = new Array(m).fill(null);
35                let collision = false;
36                
37                for (let k of bKeys) {
38                    const h = this.hash(k, sa, sb, m);
39                    if (slots[h] !== null) { collision = true; break; }
40                    slots[h] = k;
41                }
42                if (!collision) {
43                    this.primary[i] = { a: sa, b: sb, m, slots };
44                    found = true;
45                }
46            }
47        }
48    }
49
50    contains(key) {
51        const pIdx = this.hash(key, this.a, this.b, this.size);
52        const bucket = this.primary[pIdx];
53        if (!bucket) return false;
54        const sIdx = this.hash(key, bucket.a, bucket.b, bucket.m);
55        return bucket.slots[sIdx] === key;
56    }
57}

Related Lessons

Perfect Hashing

Intuition

Concept

How it Works

Step-by-Step Breakdown

When to Use

When NOT to Use

How to Identify

Sample Problems

Design HashMap

AI resume checker — match your resume to the job description

Hash Map

Hash Set

Frequency Table

Time Complexity

Frequently Asked Questions

What is Perfect Hashing?

FKS Hashing (Two-level hashing)?

When is it used?