Dict

The dict is Python's workhorse. Beyond your own code, the interpreter uses dicts for module globals, object attributes and class namespaces. In interviews it's the hash map behind Two Sum, frequency counts, grouping and memoisation. Knowing how it works helps you explain why lookups are $O(1)$ on average, how collisions are handled, and why iteration follows insertion order.

Two arrays, not one#

A textbook hash table is one big array with entries scattered across it and lots of empty gaps. Since CPython 3.6, the compact dict splits that into two arrays:

1. Indices (dk_indices): a sparse array of small integers. Each slot holds a row number in the entries array, or -1 for empty.
2. Entries (dk_entries): a dense array of (hash, key, value) rows, appended in insertion order.

Inserting "apple" then "banana":

1. Append (hash("apple"), "apple", 1) as entry row 0.
2. Compute a slot from the hash (with 8 slots, the low 3 bits: hash & 7). Say it's 3. Write 0 into indices slot 3.
3. Repeat for "banana": row 1, slot 7.

Why this layout wins:

• Memory: the empty space lives in the indices array, whose slots are tiny integers (1 byte each for small dicts), not 24-byte entries.
• Order: iterating just walks the entries array top to bottom, so you get insertion order for free. Python 3.7 made insertion order a language guarantee.

Collisions: open addressing#

When two keys land on the same slot, CPython does not chain them in linked lists. It uses open addressing: it computes another slot and tries again, inside the same indices array.

Inserting "cherry" into the table above:

1. hash("cherry") & 7 gives slot 3, which is already taken by "apple".
2. The probe formula gives the next slot, say 6. It's empty, so row 2 is written there.

The probe sequence isn't simply slot + 1. CPython mixes in the higher bits of the hash (a value called perturb) so that keys with similar low bits spread out:

# One probe step (simplified from CPython's dictobject.c)
def next_slot(slot, perturb, table_size):
    slot = (5 * slot + 1 + perturb) % table_size
    perturb >>= 5
    return slot, perturb

Lookups follow the same sequence: probe, compare the stored hash, then compare keys (is first, then ==), and stop at an empty slot.

Open addressing keeps everything in contiguous memory, which is friendly to CPU caches. Deleting a key leaves a "dummy" marker in its index slot so that probe chains passing through it still work.

Resizing#

When the table gets about two-thirds full, CPython allocates a larger table and reinserts every entry. That single insert costs $O(n)$, but it happens rarely enough that inserts are amortised $O(1)$, the same argument as list append.

What operations cost#

Almost every dict operation is $O(1)$ on average:

In interviews, $O(1)$ average is the accepted answer. Mention the worst case only if asked.

Keys must be hashable#

A key's hash must never change while it's in the dict, or a lookup would probe the wrong slot and never find it. So keys must be hashable: immutable built-ins, or objects that define __hash__ and __eq__ consistently.

d = {}
d[(1, 2)] = "tuple is fine"

try:
    d[[1, 2]] = "list is not"
except TypeError as e:
    print(e)                 # unhashable type: 'list'

# Turn unhashable state into a key
grid_row = [1, 2, 3]
seen = {tuple(grid_row)}     # list -> tuple
counts = [0] * 26
key = tuple(counts)          # "Group Anagrams" signature

Interview gotchas#

A few dict behaviours regularly surprise people in interviews.

# Equal keys collide on purpose: 1, 1.0 and True are the same key
d = {1: "int"}
d[True] = "bool"
d[1.0] = "float"
print(d)                     # {1: 'float'}

# Don't change size while iterating
d = {"a": 1, "b": 2}
try:
    for k in d:
        del d[k]
except RuntimeError as e:
    # dictionary changed size during iteration
    print(e)
for k in list(d):            # iterate over a snapshot instead
    del d[k]

# Missing keys
from collections import defaultdict, Counter
print({}.get("x", 0))        # 0: no KeyError
groups = defaultdict(list)
groups["fruit"].append("apple")
print(Counter("banana").most_common(1))   # [('a', 3)]

• set uses the same hashing and open-addressing ideas, so membership is $O(1)$ on average. Unlike dicts, sets do not keep insertion order.
• Hash randomisation means str hashes differ between runs; never depend on set iteration order.

Key takeaways#

• A compact dict is a sparse indices array pointing into a dense entries array.
• Collisions use open addressing with a perturbed probe sequence, not chaining.
• Iteration follows insertion order because entries are appended in order (guaranteed since 3.7).
• Inserts are amortised $O(1)$; the table resizes at about two-thirds full.
• Keys must be hashable; convert lists to tuples to use them as keys.