vault

CPython Dict Internals

17 min read

CPython Dict Internals

CPython’s dict is a compact, insertion-ordered, open-addressing hash table. Since CPython 3.6 it stores entries in a dense, append-only array (dk_entries) that preserves insertion order, and keeps a separate sparse hash-index array (dk_indices) of small integers that map a hash slot to a position in the dense array. This indirection — a hash table of indices rather than of full entries — is what makes the layout “compact”: the sparse array holds 1-, 2-, 4-, or 8-byte integers instead of full 24-byte key/value/hash triples, so most of the wasted space in a sparsely-loaded hash table costs almost nothing. The same restructuring is what made dicts remember insertion order, an implementation detail in 3.6 that was promoted to a language guarantee in 3.7. This note describes the layout as of CPython 3.14.5 (May 2026), grounded in Objects/dictobject.c and Include/internal/pycore_dict.h.

The dict is the single most important data structure in the runtime: every namespace (module globals, class bodies, instance __dict__) is a dict, so its performance characteristics are the runtime’s performance characteristics. Knowing its layout explains its memory footprint, why lookups are amortized O(1), why ordering is now stable, and why two instances of the same class share their attribute keys instead of duplicating them. This note is the canonical description of the table itself; the closely related Attribute Lookup Mechanics note describes how obj.attr uses a dict probe as one step in a larger resolution order, and links here for the probe mechanics rather than re-explaining them.

Mental Model — Two Arrays, One Indirection

The naive way to build a hash table is one big array of (hash, key, value) slots, most of them empty (because you keep the load factor low to avoid collisions). That wastes memory: an empty slot still costs the full slot width. CPython’s compact dict splits this into two arrays so that the sparse part is cheap:

  1. dk_indices — the actual hash table. A power-of-two array indexed by hash & mask. Each cell holds a small integer index (or one of two sentinels) pointing into the second array. Because it only stores indices, each cell is just 1 byte for tiny dicts, growing to 2/4/8 bytes only as the dict grows.
  2. dk_entries — a dense, packed array of (hash, key, value) records, filled strictly in insertion order and never reordered. Iteration walks this array front-to-back, which is exactly why iteration order equals insertion order.
flowchart LR
    subgraph indices["dk_indices (sparse hash table, 8 slots)"]
        i0["[0] = EMPTY"]
        i1["[1] = 2"]
        i2["[2] = EMPTY"]
        i3["[3] = 0"]
        i4["[4] = EMPTY"]
        i5["[5] = 1"]
        i6["[6] = EMPTY"]
        i7["[7] = EMPTY"]
    end
    subgraph entries["dk_entries (dense, insertion order)"]
        e0["[0] hash,'a',1  ← inserted 1st"]
        e1["[1] hash,'b',2  ← inserted 2nd"]
        e2["[2] hash,'c',3  ← inserted 3rd"]
    end
    i3 --> e0
    i5 --> e1
    i1 --> e2

Figure: a dict {'a':1,'b':2,'c':3} in a size-8 table. The sparse dk_indices array maps each key’s hash slot to a position in the dense dk_entries array. 'a' hashed to slot 3 and was inserted first, so dk_indices[3] = 0. Insight: the dense array is append-only and ordered; the sparse array is the only thing that is hash-addressed, and it stores small integers, so most of the “empty slot” cost is one byte per slot, not one full entry.

The header that ties these together is PyDictKeysObject (the “keys object”), and the dict object proper is PyDictObject. The split between them is the basis of the key-sharing optimization described below.

The Object Layout

The user-visible dict is a PyDictObject, defined in Include/cpython/dictobject.h:

typedef struct {
    PyObject_HEAD
    Py_ssize_t ma_used;          // number of live items
    uint64_t _ma_watcher_tag;    // dict-watcher + tier-2 mutation bits
    PyDictKeysObject *ma_keys;   // the keys object (the two arrays)
    PyDictValues *ma_values;     // NULL => combined; non-NULL => split table
} PyDictObject;

The two fields that matter for understanding the structure are ma_keys and ma_values:

  • ma_keys points at the PyDictKeysObject holding both arrays. In a combined table this keys object holds the keys and the values (values live inside dk_entries).
  • ma_values is the discriminator between combined and split tables. The header comment states it directly: “If ma_values is NULL, the table is ‘combined’: keys and values are stored in ma_keys. If ma_values is not NULL, the table is split: keys are stored in ma_keys and values are stored in ma_values.” Split tables are the mechanism behind PEP 412 key-sharing, covered in its own section below.

The PyDictKeysObject (in pycore_dict.h) is where the two arrays live:

struct _dictkeysobject {
    Py_ssize_t dk_refcnt;        // shared keys are refcounted (split tables)
    uint8_t dk_log2_size;        // log2 of dk_indices length (power of 2)
    uint8_t dk_log2_index_bytes; // log2 of the byte-size of dk_indices
    uint8_t dk_kind;             // GENERAL | UNICODE | SPLIT
    uint32_t dk_version;         // bumped/zeroed for the type/version cache
    Py_ssize_t dk_usable;        // remaining free entry slots before resize
    Py_ssize_t dk_nentries;      // entries used in dk_entries so far
    char dk_indices[];           // the sparse index array (variable width)
    // dk_entries[] (PyDictKeyEntry or PyDictUnicodeEntry) follows in memory
};

Walking the load-bearing fields:

  • dk_log2_size is the base-2 logarithm of the number of slots in dk_indices. The table is always a power of two, which is why slot selection can use a cheap bitmask (hash & (size-1)) instead of a modulo. The minimum is PyDict_LOG_MINSIZE = 3, i.e. 8 slots (PyDict_MINSIZE 8).
  • dk_log2_index_bytes records how wide each dk_indices cell is. The header documents the rule: 1 byte if dk_size <= 0xff, 2 bytes if <= 0xffff, 4 bytes if <= 0xffffffff, 8 bytes otherwise. A 256-slot dict uses 1-byte indices; the index width grows only as the dict does.
  • dk_kind is one of DICT_KEYS_GENERAL (0), DICT_KEYS_UNICODE (1), or DICT_KEYS_SPLIT (2). This distinction drives the entry layout (next section).
  • dk_usable counts how many entry slots remain before a resize is forced; dk_nentries counts how many are in use. The dense dk_entries array has room for USABLE_FRACTION(dk_size) records; when dk_usable hits zero, the dict grows.

The dense entry array comes in two flavours, selected by dk_kind:

typedef struct {                 // PyDictKeyEntry  (general dicts)
    Py_hash_t me_hash;           // cached hash of me_key
    PyObject *me_key;
    PyObject *me_value;          // only meaningful for combined tables
} PyDictKeyEntry;
 
typedef struct {                 // PyDictUnicodeEntry  (all-str-key dicts)
    PyObject *me_key;            // must be exact str
    PyObject *me_value;
} PyDictUnicodeEntry;

The key optimization here is that a dict whose keys are all exact str objects (DICT_KEYS_UNICODE) uses PyDictUnicodeEntry, which omits the me_hash field entirely — saving 8 bytes per entry on a 64-bit build. This is sound because the hash of a str is cached on the string object itself, in the PyASCIIObject/PyUnicodeObject header, so it can be recomputed for free with unicode_get_hash(me_key) (a field read, no rehash). The whatsnew for 3.11 records the win concretely: “sys.getsizeof(dict.fromkeys("abcdefg")) is reduced from 352 bytes to 272 bytes (23% smaller) on 64-bit platforms” (What’s New in Python 3.11, contributed by Inada Naoki). Because most dicts in a Python program are namespaces with string keys, this is the common case, not a corner case. The moment a non-str (or str subclass) key is inserted, the keys object falls back to the general layout with me_hash present.

The Probe Sequence — Open Addressing with Perturbation

CPython resolves collisions by open addressing: when two keys hash to the same slot in dk_indices, the probe walks to other slots in the same array rather than chaining off the entry. The probe recurrence is the heart of the lookup, and the long design comment in dictobject.c (lines ~289–360) explains exactly why it is shaped the way it is.

The initial slot is the low bits of the hash: i = hash & mask, where mask = 2**dk_log2_size - 1. Taking the low i bits is “dirt cheap” and, the comment notes, better than random for the common case of consecutive integer keys (since hash(n) == n for small ints, contiguous ints map to contiguous slots with zero collisions). When a slot is occupied by a different key, the recurrence advances:

// from do_lookup() in dictobject.c
perturb >>= PERTURB_SHIFT;          // PERTURB_SHIFT == 5
i = mask & (i*5 + perturb + 1);

Walking this symbol by symbol:

  • perturb is initialized to the full hash value (all 64 bits), not just the low bits already used. Each step it is right-shifted by PERTURB_SHIFT (= 5), feeding progressively higher-order hash bits into the slot computation. This is what makes the probe sequence depend, eventually, on every bit of the hash — two keys that collide in their low bits will almost certainly diverge once their higher bits enter via perturb.
  • i*5 + perturb + 1 is the recurrence. Stripped of perturb, i = (5*i + 1) mod 2**k is a full-period generator: for any starting i, repeating it 2**k times visits every slot exactly once (a standard linear-congruential result the comment cites). That guarantees the probe never gets stuck cycling a subset of slots, so it always finds either the key or an empty slot.
  • & mask wraps the result back into the table.
  • Once perturb has been shifted enough times it becomes 0, and the recurrence degrades to the pure 5*i + 1 generator — still full-period, so termination is guaranteed as long as at least one slot is always empty (which the load-factor invariant ensures).

The lookup loop (do_lookup) reads dk_indices[i]. Three outcomes:

  • index >= 0: a live entry; compare its key (cheap me_hash/cached-hash check first, then a full PyObject_RichCompareBool(..., Py_EQ) only if hashes match) and return its position on a match.
  • DKIX_EMPTY (-1): the slot was never used → the key is absent, stop.
  • DKIX_DUMMY (-2): a deleted entry’s tombstone → keep probing (a deletion cannot stop the search, or it would hide keys inserted after it).

The actual 3.14 loop is manually unrolled (two probe steps per iteration) and comes in several check_lookup variants — compare_unicode_unicode (both table and query key are exact str, the fastest path, a pointer-equality-then-unicode_eq compare), compare_unicode_generic (str table, non-str query), and compare_generic (general). They all share the same do_lookup skeleton and the same recurrence above.

Load Factor, Resizing, and Growth

The table never fills completely — the comment is explicit: “To avoid slowing down lookups on a near-full table, we resize the table when it’s USABLE_FRACTION (currently two-thirds) full.” The macro encodes the bound:

#define USABLE_FRACTION(n) (((n) << 1)/3)   // ~ 2n/3

So a size-8 table can hold at most (8<<1)/3 = 5 entries before a resize. Keeping the load factor under 2/3 is what makes “we usually find the key on the first probe” true — the comment notes the odds are “solidly in our favor” at that load. The dense dk_entries array is sized to exactly USABLE_FRACTION(dk_size), so the two arrays grow together.

When dk_usable reaches zero, the dict grows according to GROWTH_RATE:

#define GROWTH_RATE(d) ((d)->ma_used*3)

The new table size is the next power of two ≥ used*3. The comment explains the choice: “This means that dicts double in size when growing without deletions, but have more head room when the number of deletions is on a par with the number of insertions.” Sizing to 3 × used (not 3 × capacity) means a dict that has had many deletions does not grow on the next insert — used reflects live entries, so deletions effectively reclaim space at the next resize. (The history in the comment is itself instructive: the rate was used*4 up to 3.2, used*2 in 3.3, used*2 + capacity/2 for 3.4–3.6, and used*3 since.)

A resize is also where tombstones get compacted away: dictresize rebuilds dk_indices from scratch and copies only live dk_entries into a fresh dense array, so deletions that left DKIX_DUMMY markers are physically removed and insertion order among survivors is preserved. This is why a dict that has churned through many insert/delete cycles does not accumulate unbounded tombstones.

Insertion Order as a Language Guarantee

Because new entries are appended to dk_entries and that array is never reordered, iteration (which walks dk_entries front-to-back, skipping NULL-valued slots) yields keys in insertion order. In CPython 3.6 this fell out of the new compact layout as an implementation detail. In 3.7 it became part of the language spec: “the insertion-order preservation nature of dict objects has been declared to be an official part of the Python language spec” (What’s New in Python 3.7). Concretely, deleting and re-inserting a key moves it to the end (it gets a new dk_entries slot); updating the value of an existing key does not change its position. The interaction between ordering assumptions and these subtleties is the subject of Dictionary Ordering Assumptions.

PEP 412 Key-Sharing, and the Modern Inline-Values Default

PEP 412 (Mark Shannon, Python 3.3) observed that instance __dict__s waste memory: every instance of a class typically has the same set of attribute names, yet each instance’s dict replicated the full keys object. The fix is the split table: the PyDictKeysObject (the keys, the hash index, and insertion order) is shared across all instances of a class — stored once on the type — while each instance carries only its own values array (ma_values). The PEP’s abstract: “The keys are replicated for each instance rather than being shared across many instances of the same class.” It claimed a 10–20% memory reduction for object-oriented programs.

Resolved (2026-06-01)

There is no dedicated PEP for the inline-values mechanism. PEP 412 (above) introduced the split-table key-sharing scheme in 3.3; the modern inline-values layout (Py_TPFLAGS_INLINE_VALUES / Py_TPFLAGS_MANAGED_DICT) is a Faster-CPython implementation change, not a standards-track PEP. This is corroborated by the 3.11 What’s New — “Objects now require less memory due to lazily created object namespaces. Their namespace dictionaries now also share keys more freely.” (no PEP cited) — and by the v3.14.5 dictobject.c source, where the Py_TPFLAGS_INLINE_VALUES / Py_TPFLAGS_MANAGED_DICT machinery carries no PEP reference (the only nearby issue tag is GH-130327, a later bugfix, not the introducing change). The scheme below is therefore traced directly from 3.14.5 source, which is the authoritative description.

In modern CPython (verified in 3.14.5), instance attributes do not start life in a dict at all. Instead:

  1. The type carries a shared PyDictKeysObject in its ht_cached_keys field (CACHED_KEYS(tp) in the source), built from the attribute names the class assigns (typically in __init__).
  2. Each instance carries an inline PyDictValues array embedded in the object’s own memory (right after the header), holding just the attribute values in the slot order of the shared keys. The _dictvalues struct carries a small prefix (capacity, size, embedded, valid) plus the values[] array.
  3. Reading obj.attr takes the fast path _PyObject_TryGetInstanceAttribute: it looks the name up once in the shared keys (_PyDictKeys_StringLookupSplit) to get an index ix, then returns values->values[ix] — no per-instance dict is ever allocated. This is the path the attribute-lookup machinery hits before falling back to a real dict (see Attribute Lookup Mechanics).
  4. obj.__dict__ is materialized lazily, only when something actually asks for it. _PyObject_MaterializeManagedDict builds a PyDictObject whose ma_values points at the (now externalized) inline array and whose ma_keys is the shared keys — i.e. a genuine PEP-412 split dict — and stores it in the object’s managed-dict slot.

The split form converts to a combined table when the per-instance keys diverge from the shared set. In the source, storing an attribute whose name is not in the shared keys calls insert_split_key, which returns DKIX_EMPTY if the shared keys are full (SHARED_KEYS_MAX_SIZE = 30 attributes) or otherwise can’t accommodate the name; at that point make_dict_from_instance_attributes builds a standalone combined dict for that instance, the inline values are marked invalid (values->valid = 0), and that instance pays for its own full keys object from then on. So the memory win holds as long as instances of a class share a stable, modest (≤30) set of attribute names — which is the overwhelmingly common case.

The practical consequence: for a class whose instances all set the same few attributes, the attribute names are stored exactly once on the type, and each instance costs only its inline values array. This is why a million instances of a 3-attribute class do not pay for a million copies of the three key strings and three hash-index arrays. The interplay with explicit attribute slots (__slots__, which removes the dict entirely in favour of a fixed C array of member_descriptors) is covered in The slots Optimization.

Failure Modes and Surprises

  • Per-key tombstones bloat only transiently. A dict that is heavily inserted-and-deleted accumulates DKIX_DUMMY markers in dk_indices, which slightly lengthen probe chains, but the next resize compacts them. There is no permanent fragmentation of the index array, though a dict that grew large and then shrank does not shrink its tables until it is rebuilt (e.g. via dict(d) or a resize-triggering insert) — a large dict you cleared can keep a large backing table.
  • str-subclass keys silently disable the unicode optimization. Inserting a str subclass (or any non-exact-str) key converts the keys object from DICT_KEYS_UNICODE to DICT_KEYS_GENERAL, re-introducing the 8-byte me_hash per entry. A dict you expected to be compact can be larger because one key was an enum/str-subclass.
  • Diverging instance attributes defeat key-sharing. If different instances of a class set different attribute names (or more than SHARED_KEYS_MAX_SIZE = 30), the shared-keys optimization collapses to per-instance combined dicts and the memory win evaporates. Setting attributes only in __init__, in a consistent order, preserves it.
  • Mutating a dict during iteration is detected. Resizes move entries; the interpreter raises RuntimeError: dictionary changed size during iteration rather than producing silently wrong results. This is a deliberate guard, covered from the gotcha angle in Mutating a Collection While Iterating.
  • Hash quality still matters for adversarial inputs. Open addressing degrades to O(n) per operation if many keys collide. The perturb scheme defends against accidental clustering, and CPython randomizes str/bytes hashing (PYTHONHASHSEED/SipHash) to defend against deliberate hash-flooding, but a user-defined __hash__ that returns a constant will turn every dict operation linear.

Alternatives and When to Choose Them

When the dict’s job is a set of keys with no associated values, CPython Set Internals uses a structurally similar open-addressing table but without the compact two-array indirection — a set stores (hash, key) entries directly in the hash table, because there is no value array to keep dense and no insertion-order guarantee to maintain. For small, fixed key sets that you only construct once, a tuple of pairs scanned linearly can beat a dict’s constant-factor overhead. For ordered-by-key (not insertion) access you need a tree-backed structure (no stdlib built-in; sortedcontainers or a heap). When keys are dense small integers, a list indexed directly is far more compact than a dict. And collections.OrderedDict — once the only ordered mapping — now differs from a plain dict mainly in its move-to-end API and equality-is-order-sensitive semantics, both detailed in collections Data Structure Internals.

Production Notes

The compact dict was first proposed by Raymond Hettinger on python-dev in 2012 and implemented by Inada Naoki for 3.6 (python-dev, September 2016); the ordering-as-spec decision followed in 3.7. The key-sharing and inline-values work is part of Mark Shannon’s broader effort to shrink object overhead (the Faster CPython project), and the per-entry hash elision landed in 3.11. The cumulative effect is that the data structure underpinning every Python namespace has become substantially smaller and more cache-friendly across the 3.6→3.14 era without any change to its Python-level semantics — the same {} you have always written now sits on a markedly leaner table.

See Also

Graph View

Backlinks