The object model,
not the syntax.

What a dict actually does with a key

A dict is an array of slots. When you write d[k] = v, Python does four things in order:

1. Compute hash(k), a plain integer.
2. Turn that integer into an index by masking off the low bits: i = hash(k) & (table_size - 1).
3. Look at slot i. If it is empty, store the key there and stop. If it holds something, compare: first the cached hashes, then == on the keys themselves. Equal means overwrite the value. Not equal means a collision, so probe to another slot and repeat.
4. Remember that slot number. The dict never recomputes it.

Point four is the whole ballgame. The key's position in the table is a function of its hash at the moment it was inserted. Nothing watches the key afterwards.

The layout since Python 3.6

Modern CPython splits a dict into two arrays rather than one:

• A sparse index array, sized to a power of two, holding small integers. Most entries are the "empty" marker.
• A dense entries array, holding (hash, key, value) triples packed together in insertion order with no gaps.

A lookup masks the hash to get a position in the index array, reads the small integer there, and uses it to index into the dense array. That indirection buys two things at once. Memory drops sharply, because the sparse array that must stay mostly empty now holds 1-byte or 2-byte integers instead of full 24-byte triples. And insertion order falls out for free, because the dense array is only ever appended to.

Collision handling

CPython uses open addressing, not chaining. There are no linked lists hanging off buckets. When slot i is taken by a different key, the probe sequence moves to another slot in the same array using a recurrence that mixes in the still-unused high bits of the hash:

perturb = hash
j = hash & mask
while occupied(j) and not_our_key(j):
    perturb >>= 5
    j = (5*j + 1 + perturb) & mask

Feeding the high bits back in matters. Plain linear probing would send every key that collides in the low bits down the identical path, so one collision would make the next more likely, a feedback loop called primary clustering. Perturbing scatters colliding keys onto different paths and keeps clusters from feeding on each other.

Open addressing is chosen because it keeps everything in one contiguous allocation. A probe reads adjacent memory, which is cache friendly, whereas chaining would follow a pointer into a separately allocated node and very likely miss cache. That trade is the same one you will make again on the operating systems page.

Hash table probe visualizer

Insert keys and watch them land. Use "force collision" to add keys that all mask to the same slot, then watch probing walk them along. Insert past the load factor to trigger a resize, or mutate a stored key to reproduce the KeyError from the previous section.

What yield does to a function

When the compiler sees yield anywhere in a function body, it flags the whole function as a generator function. Calling it now does something quite different from a normal call: it builds a generator object holding a suspended stack frame and returns immediately. None of the body has run. Not one line.

Each next() resumes that frame at the saved instruction pointer, with local variables exactly as they were, runs until it hits the next yield, hands back the value, and suspends again. The frame is a heap-allocated object that outlives any individual call, which is why the locals survive across suspensions.

def gen():
    print("starting")
    yield 1
    print("middle")
    yield 2

g = gen()          # prints nothing at all
next(g)            # prints "starting", returns 1
next(g)            # prints "middle",   returns 2
next(g)            # raises StopIteration

That first line explains a bug people hit constantly: validation written at the top of a generator function does not run when you call it. It runs when someone first iterates it, which may be somewhere else entirely, inside a different try block, or never.

Where the memory actually goes

Compare processing a large file two ways:

# eager: the whole file becomes a list of str objects
lines = f.readlines()
total = sum(len(l) for l in lines)

# lazy: one line alive at a time
total = sum(len(l) for l in f)

The eager version allocates one str object per line and a list of pointers to them, so peak memory is proportional to the file. The lazy version holds one line, sums into an int, and lets the previous line's refcount drop to zero so it is freed immediately. Peak memory is proportional to the longest line. For a 10 GB file on a 16 GB machine that is the difference between working and not working, and no amount of faster hardware changes the answer.

The saving is not about speed. Both versions do the same amount of per-line work and the generator version is often marginally slower per item because of the resume overhead. What you buy is a bounded working set.

Three levels of copying

import copy
original = [[1, 2], [3, 4]]

alias   = original                 # no copy: same object
shallow = original[:]              # new outer list, same inner lists
deep    = copy.deepcopy(original)  # new everything, recursively

Three arrows into one inner list is the entire bug surface of shallow copying.

Decorators

A decorator is a function that takes a function and returns a replacement. The @ syntax is pure sugar: @d above def f means f = d(f) after the def runs.

import functools, time

def timed(fn):
    @functools.wraps(fn)                # copies __name__, __doc__, __wrapped__
    def wrapper(*args, **kwargs):
        t0 = time.perf_counter()
        try:
            return fn(*args, **kwargs)
        finally:                        # still times a call that raised
            print(fn.__name__, time.perf_counter() - t0)
    return wrapper

functools.wraps is not cosmetic. Without it the decorated function reports the wrapper's name, loses its docstring and type hints, and breaks anything that introspects it, which includes pytest fixtures, Sphinx, dataclasses and most serialisation. Always include it.

A decorator that takes arguments needs one more layer, because @retry(3) means "call retry(3), then apply whatever it returns as the decorator":

def retry(n):
    def deco(fn):
        @functools.wraps(fn)
        def wrapper(*a, **kw):
            for attempt in range(n):
                try:
                    return fn(*a, **kw)
                except Exception:
                    if attempt == n - 1: raise
        return wrapper
    return deco

Context managers

The point of with is that cleanup happens on every exit path, including exceptions, return and break. Two ways to write one:

class Timer:
    def __enter__(self):
        self.t0 = time.perf_counter()
        return self                 # this is what "as t" receives
    def __exit__(self, exc_type, exc, tb):
        self.elapsed = time.perf_counter() - self.t0
        return False                # False propagates the exception, True swallows it

from contextlib import contextmanager

@contextmanager
def timer():
    t0 = time.perf_counter()
    try:
        yield                        # everything before is __enter__
    finally:
        print(time.perf_counter() - t0)   # after is __exit__

Two details worth having ready. The try/finally in the generator form is mandatory, because an exception in the body is thrown back in at the yield, and without finally your cleanup is skipped. And returning a truthy value from __exit__ suppresses the exception, which is how contextlib.suppress works and is a thing you should almost never do by hand.

Argument forms

def f(pos, /, normal, *args, kwonly, **kwargs):
    ...
#     ^        ^        ^       ^         ^
#     |        |        |       |         collects extra keywords into a dict
#     |        |        |       must be passed by name (after * )
#     |        |        collects extra positionals into a tuple
#     |        either position or name
#     positional only (before / ), name is not part of the API

At a call site * and ** unpack rather than collect: f(*seq, **mapping) spreads a sequence into positionals and a mapping into keywords. Positional-only parameters, marked by /, let you rename a parameter later without breaking callers, which is why the C-implemented builtins use them heavily.

Comprehensions

squares  = [x*x for x in xs if x > 0]        # list
uniq     = {x.id for x in xs}                # set
by_id    = {x.id: x for x in xs}             # dict
lazy     = (x*x for x in xs)                 # generator, evaluates nothing yet
flat     = [y for row in grid for y in row]  # nested: outer loop first, left to right

A comprehension has its own scope, so its loop variable does not leak into the enclosing function. That has been true for list comprehensions since Python 3 and is why the loop-variable-after-the-loop trick works for for statements but not for comprehensions.

The shelf: what to reach for, and when

Complexity reflex table

Filter by structure, or hide the answers and score yourself. Worst case is shown where it differs from the average, because the gap is usually the interesting part.