02 — Hash Tables, Sets & $O(n)$ Hash Joins

At a glance

After completing this lesson you can:

• Explain how CPython implements dictionaries and sets using compact hash tables and open addressing with perturbation.
• Turn $O(n \times m)$ nested loop lookups into $O(n + m)$ hash joins across large relational-style datasets.
• Diagnose hash collisions, unhashable type errors (TypeError: unhashable type), and mutable key corruption.

Time: ~50 minutes · Prerequisites: 01 — Complexity & Dynamic Arrays

Reading Companion

• Book: Grokking Algorithms (2nd Edition) — Aditya Y. Bhargava
• Chapter 5: Hash Tables (Hash functions, Collisions, Performance).
• Book: Fluent Python (2nd Edition) — Luciano Ramalho
• Chapter 3: Dictionaries and Sets (Modern dict implementation, set operations, hashability).

Why this matters in production

Merging two datasets (such as matching 50,000 orders with 10,000 customer records) with a naive nested loop for order in orders: for user in users: if order.user_id == user.id: ... requires $500,000,000$ comparisons, locking worker CPUs for seconds or minutes. Building a hash index first (user_index = {u.id: u for u in users}) cuts this to $60,000$ operations—a $8,300\times$ speedup executed in milliseconds.

Deep dive

1. Hashability in Python

An object is hashable if:

1. It implements __hash__() returning an integer that never changes during its lifetime.
2. It implements __eq__() for equality comparisons.
3. If a == b, then hash(a) == hash(b) must hold.

Mutable containers (list, dict, set) are unhashable. Tuples are hashable only if all their elements are hashable.

2. CPython's Compact Dict Representation (Raymond Hettinger design)

Since Python 3.6, dicts use a split table design:

• An indices array mapping hash slots to entries.
• An entries array storing keys, values, and precomputed hashes in insertion order.

Compact Dict Layout:
indices: [-1, 0, -1, 1, -1]  <- sparse table
entries: [
  (hash_a, "user_id", 101),   <- dense array (compact & ordered)
  (hash_b, "tenant", "acme"),
]

Hands on

python3 phase1-cs-and-architecture/01-data-structures/02-hash-tables-and-sets/examples/01_demo.py
python3 phase1-cs-and-architecture/01-data-structures/02-hash-tables-and-sets/examples/02_trap.py

AI Trap & Code Review

# BAD AI-GENERATED CODE — O(N*M) NESTED JOIN IN API HANDLER
def enrich_orders_with_customers(orders: list[dict], customers: list[dict]) -> list[dict]:
    enriched = []
    for order in orders:
        for cust in customers:  # Nested loop scan O(n * m)!
            if cust["id"] == order["customer_id"]:
                enriched.append({**order, "customer_name": cust["name"]})
                break
    return enriched

Exercises

1. Rung 1 (make_hashable_signature): Convert an arbitrary nested JSON-like dict (containing lists, strings, numbers, dicts) into a deeply immutable, hashable tuple representation.
2. Rung 2 (hash_join_datasets — Fix the AI Bug): Refactor the $O(n \times m)$ nested loop join into an optimal $O(n + m)$ hash join supporting left outer joins.
3. Rung 3 (detect_frequency_anomalies): Given a stream of tenant events, find all tenants whose event count exceeds a threshold $k$ in single-pass $O(n)$ time and $O(U)$ memory.
4. Rung 4 (two_sum_hash_lookup): Find pair of indices whose values sum to target in strictly single-pass $O(n)$ time.
5. Rung 5 (custom_hash_set): Implement a collision-handling set data structure using a fixed-size bucket array with chaining.

Wrapping up

Can you explain?

1. Why does a custom class implementing __eq__ without __hash__ become unhashable in Python 3?
2. How does an inner hash join differ from a left outer hash join?
3. What is the worst-case time complexity of a hash table lookup and when does it occur?

Further Reading & References

• CPython Source: listobject.c (Dynamic Array Implementation)
• Raymond Hettinger: Modern Dictionaries by Key-Sharing
• Alex Xu: System Design Interview — Rate Limiter Design
• Tim Roughgarden: Algorithms Illuminated Series