CPython's dict Implementation in C: Combined Tables, Split Keys, and the Probe Sequence

TL;DR: CPython’s dict is a hash table split into a PyDictObject header and a PyDictKeysObject that holds the actual table. It uses open addressing with a perturb-based probe sequence, resizes at 2/3 load, preserves insertion order, and can share keys across instances (split tables) — a huge win for object __dict__s. Here’s how it all fits together in CPython 3.15.

Python’s dict is a hash table with a twist: since 3.6 it’s compact and preserves insertion order, and since 3.3 a single keys object can be shared by many instances of the same class. In CPython this lives in Objects/dictobject.c. Let’s trace the representation and the hot paths through the 3.15 source.

The object struct

A dict is split into two pieces: the PyDictObject header and a PyDictKeysObject that holds the actual hash table:

c
// Include/cpython/dictobject.h
typedef struct {
    PyObject_HEAD
    Py_ssize_t ma_used;            /* number of items */
    uint64_t _ma_watcher_tag;     /* watcher bits + mutation counter + unique id */
    PyDictKeysObject *ma_keys;     /* the hash table */
    PyDictValues *ma_values;      /* NULL => combined table */
} PyDictObject;

ma_values is the switch between the two table kinds. When it’s NULL, the dict is combined: keys and values both live inside ma_keys. When it’s non-NULL, the dict is split: keys live in the shared ma_keys, values in a per-instance ma_values array.

PyDictKeysObject

The keys object is the hash table. Its header is followed in memory by dk_indices (the probe array) and then dk_entries:

c
// Include/internal/pycore_dict.h
struct _dictkeysobject {
    Py_ssize_t dk_refcnt;
    uint8_t dk_log2_size;          /* log2(table size), power of two */
    uint8_t dk_log2_index_bytes;   /* 1/2/4/8 byte indices */
    uint8_t dk_kind;               /* GENERAL / UNICODE / SPLIT */
    uint8_t ... (mutex on free-threaded builds)
    uint32_t dk_version;
    Py_ssize_t dk_usable;          /* free slots left */
    Py_ssize_t dk_nentries;       /* used entries in dk_entries */
    char dk_indices[];             /* the hash table */
    /* dk_entries[] follows */
};

dk_kind distinguishes general tables (arbitrary keys, PyDictKeyEntry with cached hash) from Unicode-keyed tables (PyDictUnicodeEntry, no cached hash needed because Unicode objects cache their own hash). The third kind, DICT_KEYS_SPLIT, is the shared-keys case.

Two entry types:

c
// Include/internal/pycore_dict.h
typedef struct {
    Py_hash_t me_hash;
    PyObject *me_key;
    PyObject *me_value;   /* meaningful only for combined tables */
} PyDictKeyEntry;

typedef struct {
    PyObject *me_key;     /* must be exact Unicode with cached hash */
    PyObject *me_value;   /* meaningful only for combined tables */
} PyDictUnicodeEntry;

Combined vs. split tables

Combined table (ma_values == NULL): each entry stores key, hash, and value together in dk_entries. dk_refcnt == 1. This is the default for ordinary dicts.

Split table (ma_values != NULL): keys are stored once in a shared PyDictKeysObject (marked DICT_KEYS_SPLIT), values in a per-instance PyDictValues. Only Unicode keys are allowed. This is the optimization for instance __dict__: thousands of objects of the same class share one keys table, and each instance only pays for its own value array.

c
// Include/internal/pycore_dict.h
#define _PyDict_HasSplitTable(d) ((d)->ma_values != NULL)

Memory layout

text

PyDictObject (GC-tracked)
+---------------------------+
| ob_refcnt / ob_type       |
+---------------------------+
| ma_used                   |
+---------------------------+
| _ma_watcher_tag           |
+---------------------------+
| *ma_keys  ----------------+--> PyDictKeysObject (PyMem)
| *ma_values (or NULL)       |    +---------------------------+
+---------------------------+    | dk_refcnt                 |
                                  | dk_log2_size              |
                                  | dk_log2_index_bytes       |
                                  | dk_kind                   |
                                  | dk_version                |
                                  | dk_usable                 |
                                  | dk_nentries               |
                                  +---------------------------+
                                  | dk_indices[]              |  <- hash table
                                  |   int8/16/32/64 per slot  |
                                  +---------------------------+
                                  | dk_entries[]              |  <- key/value rows
                                  |   (USABLE_FRACTION(size)) |
                                  +---------------------------+

If split:
PyDictValues (PyMem)
+---------------------------+
| capacity / size / embedded / valid |
+---------------------------+
| values[capacity]           |
+---------------------------+
| insertion-order byte array |
+---------------------------+

The index array uses the smallest integer width that fits the table size (1 byte up to 128 slots, 2 bytes up to 2^15, etc.), saving memory for the common small dictionaries.

Hash probing

The hash table is open-addressed with the classic CPython probe sequence. The initial slot is hash & mask (mask = size-1, size is a power of two). On collision:

c
// Objects/dictobject.c  (do_lookup)
size_t i = (size_t)hash & mask;
for (;;) {
    ix = dictkeys_get_index(dk, i);
    if (ix >= 0) { ... compare ... }
    else if (ix == DKIX_EMPTY) return DKIX_EMPTY;
    perturb >>= PERTURB_SHIFT;          /* PERTURB_SHIFT == 5 */
    i = mask & (i*5 + perturb + 1);
}

DKIX_EMPTY is -1, DKIX_DUMMY is -2. A dummy slot is a tombstone: it can’t be turned back into “empty” without breaking probe chains, so deletions leave dummies behind. Empty slots terminate a search. The perturb variable folds the high bits of the hash into later probes, so even pathological key sets (e.g. i << 16) eventually spread out.

Deletion and tombstones

Deleting a key doesn’t remove its entry from dk_entries (which would break insertion order cheaply); instead the index slot is overwritten with DKIX_DUMMY (-2). The entry row is set to NULL key/value so its references can be dropped. Dummies can’t be reused in free-threaded builds (to keep lock-free reads safe), so deletion-heavy tables accumulate tombstones and are compacted by the next resize, which copies only live entries.

popitem() is the special case: it removes the last entry outright, decrementing dk_nentries, giving amortized O(1) removal from the end while leaving a dummy behind in the index array.

Insertion path

PyDict_SetItem ultimately calls insertdict. For an empty dict it takes the fast insert_to_emptydict path; otherwise it looks up the key, and on a miss calls insert_combined_dict, which resizes if dk_usable is exhausted and then writes the new entry at the found slot:

c
// Objects/dictobject.c
if (old_value == NULL) {
    if (insert_combined_dict(mp, hash, key, value) < 0) goto Fail;
    STORE_USED(mp, mp->ma_used + 1);
}

For split tables, insert_split_key records the key in the shared keys (if room remains) and _PyDict_InsertSplitValue stores the value in the instance’s slot; once the shared table is full the dict is converted to a combined table.

Load factor and resizing

The table is resized when it reaches two-thirds full:

c
// Objects/dictobject.c
#define USABLE_FRACTION(n) (((n) << 1)/3)   /* 2/3 */

dk_usable counts free slots; when it hits zero a resize is triggered. Growth size is used * 3 (so the table roughly doubles when there are few deletions, but has more headroom otherwise):

c
// Objects/dictobject.c
#define GROWTH_RATE(d) ((d)->ma_used*3)

dictresize allocates a fresh PyDictKeysObject and re-inserts all entries, rebuilding indices with build_indices_generic / build_indices_unicode. After a resize the table is always combined, even if it was split before (split values are copied in and the old value array freed). Deletion-heavy tables may actually shrink.

Insertion order

Combined tables preserve order trivially: dk_entries is append-only, so iterating entries yields insertion order. The exception is popitem(), which removes the last entry and decrements dk_nentries, leaving a dummy in the index array.

Split tables record insertion order in a byte array stored after the value array:

c
// Include/internal/pycore_dict.h
static inline uint8_t *
get_insertion_order_array(PyDictValues *values) {
    return (uint8_t *)&values->values[values->capacity];
}

When a key is inserted, its entry index is appended to this byte array (_PyDictValues_AddToInsertionOrder). With capacity capped at SHARED_KEYS_MAX_SIZE (30), the shared-keys table is limited to 30 entries.

Shared keys (the split dict optimization)

When a class’s instances get attributes, CPython creates the instance __dict__ as a split dict sharing one keys object:

c
// Objects/dictobject.c
static PyObject *
new_dict_with_shared_keys(PyDictKeysObject *keys) {
    size_t size = shared_keys_usable_size(keys);
    PyDictValues *values = new_values(size);
    ...
    dictkeys_incref(keys);
    ...
    return new_dict(keys, values, 0, 1);
}

ht_cached_keys on the type holds the shared keys. When an attribute is set, insert_split_key records the key in the shared table (if not already present) and _PyDict_InsertSplitValue stores the value in the instance’s value array. This turns per-instance dict memory from “full hash table” into “array of values” — a big win for objects with many attributes.

Iteration and views

dict.keys(), .values(), .items() return view objects that hold a reference to the underlying dict and iterate over dk_entries in order. Because the entries array is append-only for live inserts, iteration is O(n) with no hashing. Mutating the dict during iteration raises RuntimeError: dictionary changed size during iteration (detected via ma_used/dk_nentries changes).

Version numbers and watchers

Every keys object carries a dk_version (reset to 0 on any key change) and the dict carries a _ma_watcher_tag. The version lets the specializing interpreter and JIT cache “this dict has these keys” and invalidate cheaply when keys change. Watchers (registered via PyDict_AddWatcher) receive ADDED/MODIFIED/DELETED/CLONED/CLEARED/DEALLOCATED events, used by the adaptive optimizer and debuggers.

Inline values (managed dicts)

For small instance dicts, CPython can store values inside the object’s memory rather than in a separate PyDictValues allocation. The type’s tp_basicsize/tp_dictoffset machinery plus _PyInlineValuesSize computes a slot count from the shared keys’ usable size; a prefix byte array records which slots are populated and in what insertion order. _PyObject_MaterializeManagedDict converts such an inline dict into a real PyDictObject on demand (e.g. when __dict__ is accessed).

Free lists

Both PyDictObject and PyDictKeysObject are recycled:

c
// Objects/dictobject.c
PyDictObject *mp = _Py_FREELIST_POP(PyDictObject, dicts);
...
PyDictKeysObject *dk = _Py_FREELIST_POP_MEM(dictkeys);  /* only minsize unicode */

The dict object freelist and the keys freelist (only for the minimum-size Unicode case) avoid repeated PyMem_Malloc/PyObject_GC_New traffic. PyDict_Clear resets a dict to Py_EMPTY_KEYS rather than freeing it.

Allocation fast path for empty dicts

PyDict_New starts from the immortal Py_EMPTY_KEYS:

c
// Objects/dictobject.c
PyObject *PyDict_New(void) {
    return new_dict(Py_EMPTY_KEYS, NULL, 0, 0);
}

The first insertion into an empty dict (insert_to_emptydict) allocates a fresh minimum-size keys object and stores the single entry directly at hash & (MINSIZE-1), avoiding a full resize.

Frozendict

frozendict (new in 3.15) subclasses PyDictObject adding a cached ma_hash. It’s created untracked by the GC until finalized, and its keys object is immutable in practice: mutations are forbidden, so the hash can be computed once and cached:

c
// Include/internal/pycore_dict.h
typedef struct {
    PyDictObject ob_base;
    Py_hash_t ma_hash;
} PyFrozenDictObject;

Free-threading notes

In Py_GIL_DISABLED builds, dk_indices updates use atomic stores (STORE_INDEX), split keys are protected by dk_mutex, and reads can proceed lock-free using consume/acquire loads. Dicts are marked “shared” on first cross-thread access so that resizes delay freeing old keys/values via QSBR, keeping concurrent readers safe.

Key takeaways

dict is PyObject_HEAD + ma_used, watcher tag, ma_keys, and ma_values; ma_values == NULL means combined.
The hash table lives in PyDictKeysObject: an index array (dk_indices) of int8/16/32/64 slots plus an append-only entry array (dk_entries).
Lookups use open addressing with probe i = (5*i + 1 + perturb) & mask, perturb >>= 5.
Tables resize at 2/3 load; growth is used*3; entries are re-inserted.
Split tables share keys across instances (instance __dict__), storing values in a compact per-instance array with an insertion-order tail.
Insertion order comes from append-only entries (combined) or the order byte vector (split).
Dicts and minimum-size Unicode keys are freelist-recycled.