Dictionaries, Hashing, Lookup & Mapping Patterns

The dictionary (dict) is Python’s core data structure. Beyond providing $O(1)$ average-case key lookup, CPython’s modern dictionary implementation (PEP 468/469, designed by Raymond Hettinger) uses a compact high-density memory architecture that preserves insertion order while reducing memory usage by up to 60%.

This chapter details CPython compact dictionary architecture, hash collision resolution mechanics, SipHash anti-DoS security, and key-sharing dictionaries.

1. CPython Compact Dictionary Architecture (PEP 468/469)

Prior to Python 3.6, PyDictObject allocated a sparse array of 24-byte entry slots, wasting significant memory. Modern CPython uses a two-table compact architecture:

Sparse Indices Table: An array of 1-byte, 2-byte, or 4-byte integers storing array indices or -1 for empty slots.
Dense Entries Array: A compact contiguous array storing PyDictKeyEntry structs (hash, key_ptr, value_ptr).

Modern Compact PyDictObject Memory Layout:

Sparse Indices Array (1 byte per slot for small dicts):
Slot Index: [  0  | -1  |  2  | -1  |  1  | -1  | -1  | -1  ]
               |               |        |
               v               v        v
Dense Entries Array (24 bytes per entry, contiguous in memory):
Entry 0: [ hash: 0x8A3F | key: &"id"   | value: &101 ]
Entry 1: [ hash: 0x4B12 | key: &"name" | value: &"Ada" ]
Entry 2: [ hash: 0x9F01 | key: &"role" | value: &"Admin" ]

Why Dicts Preserve Insertion Order:

Because new key-value pairs are appended to the Dense Entries Array sequentially, iterating over a dictionary iterates through the dense array from index 0 to $N-1$, naturally preserving insertion order!

2. Collision Resolution: Perturb-based Open Addressing

When looking up a key, CPython hashes the key using hash(key). If two keys map to the same index slot (index = hash & mask), a collision occurs.

CPython resolves collisions using open addressing with perturbation:

Perturb Formula:
i = (5 * i + 1 + perturb) % mask
perturb = perturb >> 5

Perturbation Probe Sequence:

Hash Key -> Initial Slot Index (i = hash & mask)
                    |
                    +---> Slot Occupied by another key? (Collision!)
                    |
                    v
Calculate Next Probe: i = (5*i + 1 + perturb) & mask
                    |
                    v (Repeats until matching key or empty slot is found)

This formula shifts the top bits of the 64-bit hash into the lower index calculation on each probe, ensuring all bits of the hash participate in probing and preventing linear clustering attacks.

3. Hash Randomization (SipHash Anti-DoS Security)

If an attacker knows your application’s hash algorithm, they can craft thousands of keys that all produce identical hash values (hash1 == hash2). Sending these keys in a web request forces the dictionary into $O(N)$ linear probe chains, spiking server CPU to 100% (Hash Collision Denial of Service).

CPython mitigates this by applying SipHash-2-4 with a random per-process secret seed initialized at VM startup. The string "user_123" will produce completely different hash values across separate Python process runs.

Hashable Key Contract: A key must implement __hash__ and __eq__. The hash value must remain immutable while stored in the mapping. Never use mutable objects (lists, dicts) as keys.
Key-Sharing Dicts (PyDictKeysObject): Object instances (__dict__) share a single key table across instances of the same class, allocating memory payload only for values.

⚡

Revision Mode Active Condensed for 5-minute review. Focused on 30-second pitches, mental anchors, and high-frequency interview traps.

⚡ 30-Second Elevator Pitch

“CPython dictionaries use a compact two-table architecture (sparse indices array + dense entries array) that reduces memory usage by up to 60% and naturally preserves insertion order. Hash collisions are resolved via open addressing with bit-shifting perturbation probing. CPython uses process-randomized SipHash algorithms to prevent Hash Collision Denial of Service attacks.”

🧠 Under The Hood & Mental Model

Compact Two-Table Architecture: The sparse index array maps hash slots to indices in the contiguous dense entries table.
Insertion Order: A natural side effect of appending items sequentially to the dense entries array.
Perturbation Probing: Bit-shifts the upper hash bits during collision resolution to explore hash slots non-linearly.
Key Invariance: Mutating an object in a way that alters its __hash__ or __eq__ while it is inside a dict breaks lookup permanently.

💻 High-Yield Code & Gotcha

# ❌ ANTI-PATTERN: Mutating a Custom Object's Hash Fields inside a Dict
class UserKey:
    def __init__(self, user_id):
        self.user_id = user_id
    def __hash__(self):
        return hash(self.user_id)

key = UserKey(42)
data = {key: "Admin"}

# MUTATION BUG: Changing user_id changes the hash!
key.user_id = 99  

# GOTCHA: The dict CANNOT FIND the key anymore! Returns KeyError!
print(data[key])

# ✅ PRODUCTION PATTERN: Immutable Key Design via dataclass/frozen
from dataclasses import dataclass

@dataclass(frozen=True)  # Makes instances immutable and auto-generates stable __hash__
class UserKey:
    user_id: int

key = UserKey(42)
data = {key: "Admin"}

⚠️ GOTCHA: Evaluating `dict.get(key, expensive_fallback())`

Passing a function call as the default value to .get() causes expensive_fallback() to execute on every single call, even when the key exists! Use an explicit if key in d: check or dict.setdefault() when fallback creation is costly.

⚖️ Trade-Offs & Comparison

+ dict: Average $O(1)$ lookup, update, and deletion by key identifier.
- dict: Requires hashable keys; ~3x larger memory footprint than an equivalent tuple sequence.
dict.get() vs dict[]: Use dict[key] when absence indicates a bug (raises KeyError); use .get() when key absence is expected.

🌟 My Experience (STAR Anchor)

“A user session lookup service suffered latency degradation during traffic spikes. Profiling revealed a custom session key object was being mutated after dictionary insertion, forcing fallback linear searches. I refactored the key class into a frozen dataclass, guaranteeing hash stability and restoring sub-millisecond $O(1)$ lookups.”

Python Interview Handbook

Dictionaries, Hashing, Lookup & Mapping Patterns

1. CPython Compact Dictionary Architecture (PEP 468/469)

Why Dicts Preserve Insertion Order:

2. Collision Resolution: Perturb-based Open Addressing

3. Hash Randomization (SipHash Anti-DoS Security)

⚡ 30-Second Elevator Pitch

🧠 Under The Hood & Mental Model

💻 High-Yield Code & Gotcha

⚠️ GOTCHA: Evaluating `dict.get(key, expensive_fallback())`

⚖️ Trade-Offs & Comparison

🌟 My Experience (STAR Anchor)

How does CPython's compact dictionary architecture (PEP 468/469) preserve key insertion order?

No Interactive Questions Yet

Dictionaries, Hashing, Lookup & Mapping Patterns

1. CPython Compact Dictionary Architecture (PEP 468/469)

Why Dicts Preserve Insertion Order:

2. Collision Resolution: Perturb-based Open Addressing

3. Hash Randomization (SipHash Anti-DoS Security)

4. Production Key Contracts & Key-Sharing Dicts

⚡ 30-Second Elevator Pitch

🧠 Under The Hood & Mental Model

💻 High-Yield Code & Gotcha

⚠️ GOTCHA: Evaluating dict.get(key, expensive_fallback())

⚖️ Trade-Offs & Comparison

🌟 My Experience (STAR Anchor)

How does CPython's compact dictionary architecture (PEP 468/469) preserve key insertion order?

No Interactive Questions Yet

⚠️ GOTCHA: Evaluating `dict.get(key, expensive_fallback())`