dict internals

CPython’s dict is a hash table with open addressing. Since Python 3.7, dicts officially preserve insertion order. This file covers what matters for interviews and performance.

Layout (Python 3.6+)

A dict has two parts:

1. A compact entries array: contiguous (hash, key, value) triples in insertion order.
2. A sparse indices array: integer indices into the entries array, addressed by hash(key) % table_size.

This layout (introduced in 3.6) saves memory compared to the older sparse-only design. It also gives ordering for free.

indices: [_, _, 0, _, 1, _, _, 2]   ← sparse, by hash
entries: [(h1, "a", 1), (h2, "b", 2), (h3, "c", 3)]   ← dense, in insertion order

Lookup algorithm (open addressing + perturbation)

To find key k:

1. Compute h = hash(k).
2. Index i = h & (size - 1).
3. Look at indices[i]. If empty, key not present.
4. If indices[i] = j, fetch entries[j]. Compare entries[j].hash == h and entries[j].key == k.
5. If both match, return value.
6. If hash matches but key doesn’t (rare), continue probing — perturb the index using i = (5*i + 1 + perturb) & mask and try again.

The perturbation function uses upper hash bits as the iteration progresses, ensuring good probe distribution.

Hash and equality contract

For a key to work in a dict (or set):

1. It must be hashable — hash(k) returns a stable int.
2. a == b must imply hash(a) == hash(b) (the key invariant).
3. Hash must not change for the lifetime of the object (immutable).

That’s why list, dict, set aren’t hashable: they’re mutable. Tuples are hashable if their contents are hashable.

User-defined classes inherit __hash__ from object (based on id). If you override __eq__, you must override __hash__ too — Python sets __hash__ = None when you define only __eq__, making the class unhashable.

When two keys hash to the same slot

Two distinct keys with the same hash are a collision. They go to different entries; the second probes to the next slot. If two keys are equal (==) and hashable, they collapse into one entry.

d = {1: "a", 1.0: "b", True: "c"}
print(d)   # {1: 'c'}  ← all three hash to the same value AND compare equal

Resizing

Dicts grow when load factor exceeds ~2/3. Resize doubles (or quadruples for small dicts) the capacity, rehashes all entries, and rebuilds the indices array. Cost: O(n) for that one insertion; amortized O(1).

Operations and complexity

Worst case is rare in practice — Python’s hash function is randomized (PYTHONHASHSEED) to defeat adversarial inputs.

Why hash randomization exists

Until Python 3.2, string hashing was deterministic. An attacker who knew the algorithm could pre-compute thousands of strings that all hash to the same bucket. POSTing them as form fields, JSON keys, or HTTP headers would force any dict-backed parser into O(N²) collision-handling — a denial-of-service vector now known as a hash-collision DoS attack.

The 2011 disclosure (oCERT-2011-003 / CVE-2012-1150) showed this affecting Python, Ruby, Java, PHP, Node.js, and others. Python 3.3 made hash randomization the default: every Python process picks a random seed at startup, so the same string hashes to a different value across runs. PYTHONHASHSEED environment variable can pin the seed for reproducibility.

PYTHONHASHSEED=0 python -c 'print(hash("foo"))'   # always the same
python -c 'print(hash("foo"))'                     # different each run (since 3.3)

This makes adversarial input ineffective — an attacker can’t pre-compute colliding keys without knowing the per-process seed.

Key consequences

• Insertion order preserved — for k in d iterates in insertion order.
• d.keys(), d.values(), d.items() are views, not copies. They reflect later mutations.
• Modifying a dict during iteration raises RuntimeError (in 3.x). Use list(d) to snapshot keys first.
• Set operations on views — d1.keys() & d2.keys() does set intersection.

Memory: dict vs tuple vs slot class

For small fixed-key records, dicts are wasteful. Per dict, ~232 bytes empty + per-entry overhead. Compare:

For 1M records, a slotted class can save 100MB+ over a dict. @dataclass(slots=True) gives you the ergonomics of dataclass with the memory profile of slots — usually the right choice for fixed-shape records at scale.

Interview angle

• “What’s the time complexity of dict lookup?” (O(1) average.)
• “Why do equal objects need equal hashes?” (Otherwise they end up in different buckets and the dict lookup fails.)
• “Are dicts ordered?” (Yes, since 3.7 officially; 3.6 unofficially.)
• “What happens if I mutate a key after inserting?” (Lookup fails — hash changed but bucket location is fixed. Use immutable keys.)
• “Two dicts with the same keys/values — are they ==?” (Yes — __eq__ ignores order.)