How Python Dicts Actually Work (and why you should care)

I’ve been writing Python for 8 years. Dicts were always just key: value to me — fast lookups, done. Then I looked under the hood.

Here’s what I found, and why it changed how I think about performance.

It’s a hash table. But not the one you learned in school.

When you write d["name"] = "Alice", Python doesn’t just “store it somewhere.” It:

1. Calls hash("name") → gets a big integer
2. Masks it to fit the table size → gets a slot index
3. Drops the key-value pair into that slot

Simple enough. But the implementation? That’s where it gets interesting.

The compact dict revolution (Python 3.6+)

Before 3.6, dicts were sparse arrays — imagine a parking lot where every third spot is taken but you’re paying for all of them. Massive waste.

Python 3.6 split the dict into two structures:

Indices:  [-, 1, -, 0, -, -, -, 2]   ← tiny (1 byte each)
Entries:  [("name","Alice"), ("age",25), ("city","NYC")]  ← dense, no gaps

The indices array is just pointers. The entries array holds the actual data, packed tight. Result: 25-50% less memory.

And here’s the kicker — because entries are stored in insertion order, dicts now preserve insertion order. It was an accident in 3.6, then made a language guarantee in 3.7. OrderedDict became mostly obsolete overnight.

What happens when two keys collide?

Hash collisions are inevitable. CPython handles them with open addressing and perturbation probing:

j = ((5 * j) + 1 + perturb) % size
perturb >>= 5

This isn’t linear probing (check next slot, then next, then next). The perturbation mixes in the full hash value, so even keys that initially map to the same slot will scatter across the table differently. It avoids the clustering problem that kills simpler hash tables.

Resizing: why your dict suddenly eats more memory

Dicts resize when they’re 2/3 full. The growth is aggressive — roughly doubling each time (minimum size is 8).

import sys
d = {}
for i in range(20):
    d[i] = i
    print(f"{i}: {sys.getsizeof(d)} bytes")

# 0: 64 bytes
# 5: 232 bytes   ← jumped!
# 10: 360 bytes  ← jumped again!

Every resize rehashes everything. That’s O(n). But it happens so rarely that inserts are still O(1) amortized.

One gotcha: deleting keys doesn’t shrink the dict. CPython uses tombstone markers for deleted slots. If you build a huge dict and delete most of it, the memory stays allocated. Rebuild it if you need to reclaim space.

Things that blew my mind

{} is faster than dict(). The literal compiles to a single BUILD_MAP bytecode instruction. dict() has to look up the name, call the function, push a frame. Try it:

import timeit
timeit.timeit('{}')       # ~25ns
timeit.timeit('dict()')   # ~80ns

hash(-1) returns -2. Internally, CPython uses -1 as an error indicator for C-level hash functions. So if any hash computation produces -1, it gets silently changed to -2. Run hash(-1) yourself — it returns -2.

Your entire Python runtime is dicts. Module globals? Dict. Class attributes? Dict. Instance __dict__? Dict. Function keyword args? Dict. When you optimize dict performance, you optimize everything.

When NOT to use a dict

Dicts are great, but they’re not always the answer:

• Membership testing only? Use a set — same hash table, no values, less memory
• Fixed set of fields? Use @dataclass or NamedTuple — clearer, typed, IDE support
• Millions of instances? Use __slots__ to skip the per-instance __dict__ — saves ~200 bytes per object

The takeaway

Understanding dict internals isn’t academic trivia. It’s the difference between guessing at performance and knowing. It’s why you reach for set over list for lookups, why you use __slots__ in hot paths, and why you can confidently say “dict lookup is O(1)” in a design review instead of hoping nobody asks follow-up questions.

I’m documenting more Python internals like this at py-deep-dive on GitHub. Star it if you want to follow along.