Py
Python/Python Internals/Dict & Set Internals

Dict & Set Internals

CPython's dict is a compact, insertion-ordered open-addressing hash table giving average O(1) lookup — and set is the very same machinery with the values removed.

Advanced35mInterview Production

Learning objectives

  • › Explain how a hash table turns a key into a slot index and resolves collisions by probing
  • › Describe the compact, insertion-ordered dict layout introduced in CPython 3.6/3.7
  • › State the __hash__/__eq__ contract and why keys must be hashable and effectively immutable
  • › Reason about load factor, resize cost, and O(1) average vs O(n) worst-case lookup

Prerequisites

DictionariesHashing basicsImmutabilityBig-O notation

Version notes

  • · The compact dict layout landed in CPython 3.6 (a memory-saving change whose side effect was preserving insertion order); insertion order became a language guarantee in 3.7.
  • · Since 3.3, string/bytes hashing is randomized per process by default (PEP 456, SipHash); set PYTHONHASHSEED to a fixed value to make it reproducible.
  • · Sets never adopted the compact/ordered layout — a set has no defined iteration order, in any version.

Simple explanation

What it is. A dict is a hash table: it stores key->value pairs in an array of slots and uses the key's hash to jump almost directly to the right slot instead of scanning. CPython implements it as an open-addressing table with a compact, insertion-ordered layout, and a set is the same table with no value column.

Why it exists. Without hashing, finding a key means checking every entry — O(n). A hash table converts the key into an integer (its hash), reduces that to a slot index, and looks there first, giving average O(1) lookup, insertion and deletion. dicts are everywhere inside CPython — module namespaces, instance __dict__, keyword arguments, class attributes — so this speed is load-bearing for the whole language.

The problem it solves. It delivers near-constant-time membership and lookup even for huge collections, at the price of two requirements: keys must be hashable (so they can be located), and each key's hash and equality must stay stable while it lives in the table (so it can be found again).

How it works. hash(key) produces an integer; CPython masks it with hash & (table_size - 1) to pick a starting slot (table size is always a power of two, so the mask is a cheap bitwise AND). If that slot already holds a different key — a collision — it walks a deterministic perturbation-based probe sequence to further slots until it finds the key or an empty slot. The compact layout keeps entries in a dense, append-only array (insertion order) while a separate sparse index array of slots points into it, which is exactly why iteration follows insertion order. When the table passes roughly two-thirds full (the load factor), it grows and rehashes every key into a larger table.

Analogy: A hash table is a coat-check. Rather than searching every hook, the attendant runs your ticket number through a formula and jumps straight to a hook. If two tickets map to the same hook (a collision), they check the next hooks in a fixed order until they find yours or an empty one. The compact layout is like a numbered arrival logbook (the order coats came in) plus a card index that points into it.

Common misconceptions

  • "Dicts are unordered." — Not since 3.7: dicts preserve insertion order as a language guarantee. Sets, however, remain unordered.
  • "Hashing makes lookup always O(1)." — It's O(1) on average. A pathological set of colliding keys (or an adversarial one) degrades to O(n).
  • "Any object can be a dict key." — Only hashable objects. Lists, dicts and sets are unhashable because they're mutable; tuples of immutables and frozensets are fine.
  • "CPython dicts use linked-list chaining like Java's HashMap." — They use open addressing: collisions probe other slots in the same table, not a chained bucket.

Common alternatives

  • list of (key, value) pairs — trivial, but O(n) lookup
  • collections.OrderedDict — order-aware API (move_to_end, order-sensitive equality); plain dict now covers most needs
  • frozenset / frozen dataclass / tuple — hashable value objects to use as composite keys
  • a sorted structure (bisect on a list, or a tree) — O(log n) lookup that also keeps keys sorted

Interactive visualization

Step 1 / 5
1d = {}
2d["apple"] = 1      # hash("apple")  -> a slot
3d["banana"] = 2     # hash("banana") -> a slot
4print(d["apple"])   # hash again     -> O(1) lookup

Heap / objects

tbldict

8 slots (all empty)

An empty hash table

A dict is a hash table: a sparse array of slots. A small dict starts with 8 slots, mostly empty.

Code examples

BeginnerDicts preserve insertion order
python
Loading editor…

Note: Iteration walks the dense entries array, so it follows insertion order. Updating a value never moves the key.

Behind the scenes

  • ▸A CPython dict has two parts: a sparse array of indices (dk_indices) and a dense, append-only array of entries (dk_entries) holding (hash, key, value). Iteration walks the dense array, which is why order matches insertion.
  • ▸The starting slot is hash & (size - 1); because size is always a power of two, this mask replaces an expensive modulo with a single bitwise AND.
  • ▸On a collision, CPython follows a perturbation probe — idx = (5*idx + 1 + perturb) & mask, feeding in the high bits of the hash — so probe sequences scatter and clustering stays rare.
  • ▸A dict resizes (grows and rehashes every key into a larger table) once it passes about two-thirds full; inserts stay O(1) amortised, but any single insert that triggers a resize is O(n).
  • ▸set uses the same open-addressing idea but a single table of keys with no value column and no compact/ordered index — so sets are fast for membership yet have no defined iteration order.
  • ▸Small ints hash to themselves; str/bytes hashing is salted per process (SipHash), which is why a set of strings can iterate in a different order between runs unless PYTHONHASHSEED is fixed.

Interview insights

Key definitions

  • · Hash table: an array of slots where an element's position is computed from its key's hash, giving average O(1) lookup.
  • · Open addressing: a collision strategy that stores every entry in the table itself and probes other slots on a collision (as opposed to chaining with per-bucket linked lists).
  • · Load factor: the fraction of slots in use; CPython resizes the table once it climbs above roughly two-thirds.
How is a Python dict implemented, and why is lookup average O(1)?

Concise answer: It's an open-addressing hash table. hash(key) is masked to a slot index; you look there first and probe a short deterministic sequence on collisions. With a bounded load factor, that averages out to O(1).

Detailed answer: CPython stores entries in a compact, insertion-ordered dense array plus a sparse index array of slots. To find a key it computes hash(key), masks it with & (size-1) to a slot, and compares; on a collision it follows a perturbation probe sequence until it hits the key or an empty slot. Because the table is kept under about two-thirds full — resizing and rehashing when it fills — probe sequences stay short, so lookup, insertion and deletion are O(1) amortised on average. The worst case (many colliding keys) degrades to O(n).

Common mistake: Saying dicts use linked-list chaining like Java's HashMap — CPython uses open addressing inside one table.

Follow-ups:

  • · What makes a valid key?
  • · When and how does a dict resize?
  • · Why does iteration follow insertion order?
What is the contract between __hash__ and __eq__, and what breaks if you get it wrong?

Concise answer: Objects that compare equal must have equal hashes, and a key's hash must not change while it's in the table. Break either and dicts/sets 'lose' keys or store apparent duplicates.

Detailed answer: Lookup first jumps to the slot derived from hash(key), then confirms the match with ==. If two equal objects have different hashes they land in different slots, so a set can hold both (duplicates) and a dict lookup with one may miss the other. If you override __eq__ but not __hash__, Python makes the type unhashable to stop you creating that hazard. And if you mutate a key so its hash changes after insertion, it's effectively lost — it's no longer where the table expects it. The fix is immutable keys: tuples, frozensets, or frozen dataclasses.

Common mistake: Using a mutable object (or one with __eq__ but no __hash__) as a key.

Follow-ups:

  • · Why are lists unhashable but tuples usually aren't?
  • · What exactly does frozen=True generate?
Why can a set of strings iterate in a different order on each run, and how do you make it reproducible?

Concise answer: String hashing is salted with a per-process random seed (hash randomization, PEP 456) and sets are unordered, so where each string lands varies run to run. Set PYTHONHASHSEED to a fixed value for reproducibility.

Detailed answer: To defend against hash-flooding denial-of-service, CPython salts str/bytes hashing with a random per-process seed (since 3.3). Sets have no insertion-order guarantee, so the slot each string occupies — and therefore iteration order — changes between runs. Dicts are immune in their VISIBLE order because they iterate by insertion, though their underlying slot layout still varies. Export PYTHONHASHSEED=0 (or any fixed integer) to disable randomization, e.g. for deterministic tests or reproducible debugging.

Common mistake: Assuming set() iteration order is stable, or sorting output to 'fix' it without understanding why it varied.

Follow-ups:

  • · Does this affect dict order? (No — dicts iterate in insertion order.)
  • · What attack does hash randomization prevent?

Knowledge check

Multiple choiceQuestion 1 of 3

Since which Python version is a dict GUARANTEED to preserve insertion order?

What's the output?Question 2 of 3

What does this print?

python
class K:
    def __eq__(self, o):
        return True
print(K.__hash__ is None)
Multiple choiceQuestion 3 of 3

Two objects compare equal (a == b is True) but hash(a) != hash(b). What happens when you use them as dict keys?

Score: 0/3