How is a Python dict implemented?

As an open-addressing hash table, written in C in CPython’s Objects/dictobject.c. Each key is hashed to a starting slot (the low bits of its hash), and when that slot is taken the dict follows a probe sequence to find another slot in the same table — it never chains a linked list off a bucket. Since Python 3.6 the table is "compact": a sparse array of small integer indices (dk_indices) points into a dense, append-only array of the actual (hash, key, value) entries (dk_entries), which both saves memory and makes iteration follow insertion order.

What is the probe sequence in a Python dict?

The rule CPython uses to find the next slot after a collision. It starts at i = hash & mask and, on each miss, recurs with perturb >>= 5; i = (i*5 + perturb + 1) & mask, where perturb begins as the full hash and PERTURB_SHIFT is 5. The recurrence "depends (eventually) on every bit in the hash code," so two keys that share the same low bits (and thus the same starting slot) quickly diverge to different slots. It is not linear probing, and it is not chaining.

Why does a Python dict preserve insertion order?

Because the entries live in a dense array (dk_entries) that is "mostly append only" — a new key is appended to the end, so iterating that array yields keys in the order they were first inserted. This started as a side effect of the compact-dict memory optimization in CPython 3.6; in Python 3.7 "the insertion-order preservation nature of dict objects has been declared to be an official part of the Python language spec." Deleting a key leaves a tombstone in the index array but does not reorder the survivors.

Why does Python randomize hashes and what is PYTHONHASHSEED?

By default the hash of str and bytes objects is "salted" with an unpredictable random value that is constant within one process but changes between runs — computed with SipHash (sys.hash_info.algorithm is "siphash13" on modern CPython). Python’s docs say this "is intended to provide protection against a denial-of-service caused by carefully chosen inputs that exploit the worst case performance of a dict insertion, O(n²) complexity." PYTHONHASHSEED lets you fix the seed for reproducible runs (for tests or debugging), at the cost of that protection.

What makes an object usable as a dict key?

It must be hashable: it needs a __hash__ that never changes over its lifetime and an __eq__ consistent with it, because "objects which compare equal have the same hash value." That is why lists and other mutable built-ins are unhashable — CPython’s docs warn that a mutable object "should not implement __hash__(), since the implementation of hashable collections requires that a key’s hash value is immutable (if the object’s hash value changes, it will be in the wrong hash bucket)." Mutate a key after inserting it and the dict can no longer find it.

Python’s Dict, Under the Hood

A namespace, a set of keyword arguments, and an object’s attributes are all the same thing: a dict. Walk the CPython hash table that powers them — open addressing, the perturb probe sequence, the compact two-array layout that made insertion order a language guarantee, resizing, and SipHash — with the probe walked live over a real hash.

Concept · Languages & Runtimes. The source ↗

A free, interactive, animated visual explainer of Python’s Dict, Under the Hood — built to be understood, not skimmed.

Questions

How is a Python dict implemented?: As an open-addressing hash table, written in C in CPython’s Objects/dictobject.c. Each key is hashed to a starting slot (the low bits of its hash), and when that slot is taken the dict follows a probe sequence to find another slot in the same table — it never chains a linked list off a bucket. Since Python 3.6 the table is "compact": a sparse array of small integer indices (dk_indices) points into a dense, append-only array of the actual (hash, key, value) entries (dk_entries), which both saves memory and makes iteration follow insertion order.
What is the probe sequence in a Python dict?: The rule CPython uses to find the next slot after a collision. It starts at i = hash & mask and, on each miss, recurs with perturb >>= 5; i = (i*5 + perturb + 1) & mask, where perturb begins as the full hash and PERTURB_SHIFT is 5. The recurrence "depends (eventually) on every bit in the hash code," so two keys that share the same low bits (and thus the same starting slot) quickly diverge to different slots. It is not linear probing, and it is not chaining.
Why does a Python dict preserve insertion order?: Because the entries live in a dense array (dk_entries) that is "mostly append only" — a new key is appended to the end, so iterating that array yields keys in the order they were first inserted. This started as a side effect of the compact-dict memory optimization in CPython 3.6; in Python 3.7 "the insertion-order preservation nature of dict objects has been declared to be an official part of the Python language spec." Deleting a key leaves a tombstone in the index array but does not reorder the survivors.
Why does Python randomize hashes and what is PYTHONHASHSEED?: By default the hash of str and bytes objects is "salted" with an unpredictable random value that is constant within one process but changes between runs — computed with SipHash (sys.hash_info.algorithm is "siphash13" on modern CPython). Python’s docs say this "is intended to provide protection against a denial-of-service caused by carefully chosen inputs that exploit the worst case performance of a dict insertion, O(n²) complexity." PYTHONHASHSEED lets you fix the seed for reproducible runs (for tests or debugging), at the cost of that protection.
What makes an object usable as a dict key?: It must be hashable: it needs a __hash__ that never changes over its lifetime and an __eq__ consistent with it, because "objects which compare equal have the same hash value." That is why lists and other mutable built-ins are unhashable — CPython’s docs warn that a mutable object "should not implement __hash__(), since the implementation of hashable collections requires that a key’s hash value is immutable (if the object’s hash value changes, it will be in the wrong hash bucket)." Mutate a key after inserting it and the dict can no longer find it.

Python’s Dict, Under the Hood

Questions

Related explainers