---

📘 Perfect Hashing (in Hashing Techniques)

Perfect Hashing is a hashing technique that guarantees no collisions.
This means each key is mapped to a unique slot in the hash table.

In simple words:

👉 Perfect hashing = a hash function that produces zero collisions for a fixed set of keys.

It is mainly used when the set of keys is known in advance (static set).

---

📌 Why Perfect Hashing?

Typical hash functions may cause collisions → require chaining or probing.

Perfect Hashing eliminates this by designing a special hash function for the given keys.

✔ Search → O(1) worst case
✔ Insert (static) → done once
✔ No clustering
✔ No chains or probing

---

📘 Types of Perfect Hashing

Perfect hashing is divided into two types:

---

1. Static Perfect Hashing

• Keys are known beforehand
• No future insertions
• Ideal for reading-based lookup tables
• Used in lexical analyzers, compilers, keyword tables, databases, etc.

---

2. Dynamic Perfect Hashing

• Allows insert/delete
• Maintains O(1) worst-case lookup
• Uses two-level hashing
• More complex but more flexible

---

📘 Two-Level Perfect Hashing (Most famous technique)

Used in FKS Scheme (Fredman, Komlós, Szemerédi).

Concept:

Level 1:

• Use a universal hash function h to map keys into buckets.

Level 2:

• Each bucket gets its own sub-table
• Sub-table size = square of number of keys in that bucket:
  [
  m_i = (n_i)^2
  ]
• Hash function chosen such that no collision occurs inside each bucket

Because ( n_i^2 ) grows fast, probability of collision becomes very low → can choose hash until perfect.

Result:

• Total space = O(n)
• Worst-case lookup time = O(1)
• Guaranteed collision-free structure

---

📘 Simple Example

Keys = {12, 5, 19, 3}

Step 1: Level 1 Hash

Use h1(k) = k % 3

Key	h1(k)	Bucket
12	0	B0
3	0	B0
5	2	B2
19	1	B1

Buckets:

• B0 = {12, 3} → size = 2 → second table size = 4 slots
• B1 = {19} → size = 1 → second table size = 1 slot
• B2 = {5} → size = 1 → second table size = 1 slot

Step 2: Level 2 Hash

Choose a good hash function for each bucket so that no collision occurs.

Final result:

• No collisions anywhere.
• Lookup is O(1).

---

📘 Properties of Perfect Hashing

Property	Value
Collisions	None
Lookup	O(1) worst-case
Space	O(n)
Suitable for	Static sets
Construction time	May be expensive
Insert/delete	Hard (except in dynamic version)

---

👍 Advantages

• Fastest possible lookup (O(1) worst case)
• No collision handling needed
• Excellent for static tables
• Predictable performance

---

👎 Disadvantages

• Difficult to construct
• Not suitable when keys change frequently
• May need extra memory in level-2 tables
• Hash function depends on the key set

---

📘 Applications of Perfect Hashing

• Compilers (keyword tables)
• Symbol tables for programming languages
• Network packet classification
• Database indexing for fixed datasets
• Read-only search structures

---

📘 Python Example – Simple Perfect Hashing (Static Set)

This example uses a direct perfect map using a manually created hash:

class PerfectHashTable:
    def __init__(self, keys):
        self.size = len(keys)
        self.table = [None] * self.size

        # Try different hash multipliers until collision-free
        for A in range(1, 1000):
            success = True
            temp = [None] * self.size

            for k in keys:
                index = (k * A) % self.size
                if temp[index] is None:
                    temp[index] = k
                else:
                    success = False
                    break

            if success:
                self.A = A
                self.table = temp
                break

    def search(self, key):
        index = (key * self.A) % self.size
        if self.table[index] == key:
            return True
        return False


# Example usage
keys = [12, 5, 19, 3]
ph = PerfectHashTable(keys)

print("Search 19:", ph.search(19))  # True
print("Search 8:", ph.search(8))    # False

Note:
This is a simplified demonstration — real perfect hashing uses universal hashing and 2-level tables.

---

📘 Summary (Exam Notes)

• Perfect hashing = collision-free hashing technique
• Lookup = O(1) worst case
• ~ Two types: static & dynamic
• Mainly implemented using two-level hashing
• Works best for fixed key sets
• Compilers and databases commonly use it
• Expensive to construct but very fast to search

---