Python dictionaries from the inside: the CPython hash table

What actually happens inside d[key]

A Python dictionary does not keep "key-value" pairs in a list where a lookup has to check every element. It uses a hash table instead: an array of cells where the place for each key is worked out in advance, from a number.

Let's go through it step by step — the same subject as the full version of the article, just without the formulas from the C source.

Step 1: every key has a number

When you write d["python"] = 3, the first thing Python does is turn "python" into a number with the hash() function. That number is like a tag number at a coat check: it does not hold the key itself, but it says where to put it.

For integers it is simple: hash(5) is almost always just 5. For strings it is harder: Python deliberately makes the hash of one and the same string different on every new run of the program. This is a defense. If a string's hash were always predictable, someone could pick a million keys with the same hash on purpose and slow the program to a crawl. Below you can try both cases on real numbers (for strings, on a simplified example — Python's real algorithm cannot be reproduced across runs, and that is the whole point).

Step 2: the number turns into a cell

The table has a definite number of cells — always a power of two (8, 16, 32...). To turn a big hash number into the number of one of those cells, Python takes the last few bits of the hash. This is a very fast operation — faster than division with a remainder, though in meaning it does the same thing.

Step 3: and what if the cell is taken?

Two different keys land in the same cell now and then — this is called a collision. Python does not settle for the next free cell in a row (that would work badly). It jumps around the table in a special order that uses the parts of the hash left unused at step 2. As a result the key finds a free place fairly quickly, even when the table is already quite full.

Step 4: the table grows by itself

If the table is filled almost completely, searching it slows down — there are hardly any "nearly empty" candidate cells left. So Python keeps an eye on how full it is: as soon as the table is about two thirds full, it creates a new one, usually twice as big, and lays all the keys out in it again. That is why the size of a dictionary's internal table jumps up from time to time as you add elements — this is normal, part of the ordinary work of a dictionary, not a bug or a "memory leak".

Interactive visualization

Below is the same coat check, only step by step. Top left is the board of tags, below it the rail with the entries. Press play and watch two moments: at step 3 the tag turns out to be taken and the key has to look for another one, and at step 6 the whole board is swapped for a bigger one — but the rail is not touched, and the entries stay in the same order.

The keys here are ordinary integers, and that is no accident: for integers hash(n) equals n itself, so any slot number can be checked in your own Python. A string's hash is new on every run, so numbers like these could not be checked.

What to remember

Three things about the Python dictionary you can rely on in real code: the order of the keys stays the way you added them (a language guarantee since version 3.7); lookup, insertion and deletion are on average very fast and barely depend on the size of the dictionary; and the specific numbers, such as "two thirds full" or "the new size of the table", are internal CPython mechanics that could in theory differ in another Python implementation. If you want to see the exact formulas and the code all of this rests on, the article above has an "In depth" version.

Why know this?

Because dictionaries are the substrate of the language, not just one container among others. Every attribute access, every module namespace, every set of keyword arguments is a dictionary operation. If your service has a hot loop, there is almost certainly a dictionary inside it, even if you never wrote one by hand.

The practical consequence: CPython has not one dictionary lookup implementation but several specializations, and switching between them shows up in the numbers. The clearest demonstration is the optimization from 3.11: if all of a dictionary's keys are strings, the interpreter stops storing their hashes in the table, and sys.getsizeof(dict.fromkeys("abcdefg")) drops from 352 to 272 bytes. Add a single non-string key to such a dictionary and the table switches to the general mode. Neither transition is visible in the Python source code: to explain the regression you have to know about the layout.

The mental model

Picture a coat check. The sparse dk_indices array is the board of numbered tags on the wall: almost empty, cheap to enlarge. The dense dk_entries array is the rail with the coats themselves, hung strictly in the order they arrived. The hash says which tag to read; the tag says where to go along the rail.

Growing the table redraws the board and never rehangs the coats. That is exactly why iteration order survives a resize — and exactly why the property was originally a side effect of the layout rather than a promise of the language:

That is how the CPython authors described the side effect of the compact dictionary in 3.6 — one release before the same behavior became an official part of the language.

The design: two tables instead of one

“Sparse” and “dense” are not decorations

Two words without which nothing below adds up.

A sparse array is one that deliberately has more free cells than it needs. For an open-addressing hash table this is not a luxury but a working condition: a key is found by the formula “take the hash, cut off the low bits, look in the slot,” and if no free slots are left, the search for a free place and the resolution of collisions both degenerate into a scan of the whole table. So CPython never lets the table fill past two thirds (USABLE_FRACTION) — at least a third of the slots always stands empty, and that is not waste but working headroom.

A dense array is the opposite: it is filled consecutively from position zero, with no gaps, and grows only at the tail. Gaps appear in it only as the trace of deleted keys, and they live until the next rebuild.

The compact dictionary is made of both at once — and the whole trick is which of the two was made the sparse one.

What dk_indices is for in the first place

Before Python 3.6 there was a single array. Here is that very struct from CPython 3.5:

struct _dictkeysobject {
    Py_ssize_t dk_refcnt;
    Py_ssize_t dk_size;
    dict_lookup_func dk_lookup;
    Py_ssize_t dk_usable;
    PyDictKeyEntry dk_entries[1];
};

Here dk_entries is the hash table: slot number i is dk_entries[i], a whole entry made of hash, key and value. That is, the sparse array was an array of 24-byte entries, and the mandatory empty third cost 24 bytes per slot.

The idea of the compact dictionary (Raymond Hettinger's message to python-dev, December 2012) in one sentence: let the cheap array be the sparse one and the expensive one be dense. Sparseness is needed by the hash table itself, not by the entries, so the hash table was moved into a separate array of small integers, and all that empty headroom came to cost one byte per slot instead of twenty-four.

The arithmetic is easy to do in your head. A table of 8 slots holding 5 live keys:

On a table of 65,536 slots (43,690 entries) it is 1,572,864 bytes against 1,179,632 — the very “between 20% and 25% smaller” memory usage with which the 3.6 release notes describe the new implementation.

And now the answer to “what is this extra layer for at all”: without it, key lookup would become linear. dk_entries is ordered by insertion time, not by hash — you cannot compute from it where a key lies, you can only scan every entry in turn. dk_indices is the hash table: the address of a slot comes out of the hash in a single hash & mask operation, and the slot already holds the number of the entry you need. One access instead of a scan, O(1) instead of O(n).

Insertion order came out of this as a side effect: since entries are appended to the dense array one after another, walking that array yields the keys in the order they were added. There is no separate structure for order in the dictionary.

The two structures side by side

dk_indices is the sparse array — the one whose size is dk_size and is always a power of two. A slot holds neither a key nor a value but a small integer: the index of an entry in the second array. Or one of the service values: DKIX_EMPTY (−1) for an empty slot and DKIX_DUMMY (−2) for a slot whose key was deleted. The width of one slot is chosen to match the size of the table — from the comment on dk_indices in pycore_dict.h:

/* The size in bytes of an indice depends on dk_size:
   - 1 byte if dk_size <= 0xff (char*)
   - 2 bytes if dk_size <= 0xffff (int16_t*)
   - 4 bytes if dk_size <= 0xffffffff (int32_t*)
   - 8 bytes otherwise (int64_t*) */
char dk_indices[];

This is why “the board is cheap to enlarge”: a dictionary of eight slots spends 8 bytes on dk_indices, not eight full entries. Even at a table of 65 thousand slots it is two bytes per slot.

dk_entries is the dense array of the entries themselves, in insertion order. And here is what an entry actually holds:

typedef struct {
    /* Cached hash code of me_key. */
    Py_hash_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictKeyEntry;

Three fields of one machine word each — on a 64-bit build exactly 24 bytes per entry. The key and the value are pointers: the objects themselves live somewhere else on the heap, the dictionary stores only addresses and holds references to them. And me_hash is a cache: the key's hash is computed once on insertion and kept alongside, so that hash() need not be called again on every comparison in the probe sequence and on every growth of the table.

How these arrays get filled

Inserting a new key is four events in all, and their order is not the one that looks natural. Here is the body of insert_combined_dict from dictobject.c, cut down to the writes to memory:

Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
dictkeys_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
 
if (DK_IS_UNICODE(mp->ma_keys)) {
    PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
    STORE_KEY(ep, key);
    STORE_VALUE(ep, value);
}
else {
    PyDictKeyEntry *ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
    STORE_KEY(ep, key);
    STORE_VALUE(ep, value);
    STORE_HASH(ep, hash);
}
STORE_KEYS_USABLE(mp->ma_keys, mp->ma_keys->dk_usable - 1);
STORE_KEYS_NENTRIES(mp->ma_keys, mp->ma_keys->dk_nentries + 1);

It reads like this:

1. find_empty_slot looks for a free slot in dk_indices — by the hash and, on a collision, by the probe sequence (covered below). The key and the value take no part in that search at all: the slot is chosen by the bits of the hash.
2. dictkeys_set_index writes the current value of dk_nentries into the slot it found — the number of an entry that does not exist yet. The index lands on the board before the entry itself is created.
3. Only now is the entry at index dk_nentries in dk_entries filled in: two pointers, plus the hash in the general mode.
4. dk_usable goes down by one, dk_nentries goes up. The first counter is what is left before a resize (USABLE_FRACTION), the second is the boundary of the filled part of the dense array.

Nothing else is written to memory on insertion. Neither the key nor the value is copied anywhere: STORE_KEY and STORE_VALUE save the addresses of objects that already exist and raise their reference counts.

Below are the same four steps in interactive form: the play button runs the insertion phase by phase, and the switch at the top changes the entry layout from the general one to the string one.

The second kind of entry: when every key is a string

The entry has a second form as well. If all the table's keys are strings, CPython uses a different struct:

typedef struct {
    PyObject *me_key;   /* The key must be Unicode and have hash. */
    PyObject *me_value;
} PyDictUnicodeEntry;

There is no hash field at all here — 16 bytes instead of 24. The hash is not lost in the process: a string object has it cached inside the object already, so there is no point keeping a second copy in the table. Which of the two variants is in use is recorded in the dk_kind field (DICT_KEYS_GENERAL or DICT_KEYS_UNICODE; there is a third one, DICT_KEYS_SPLIT, covered below). This is the saving mechanism the 3.11 changelog talks about: sys.getsizeof(dict.fromkeys("abcdefg")) is 272 bytes instead of the previous 352. You can switch between the modes in the visualization above.

It is the order in dk_entries that gives the dictionary what became an official language guarantee rather than an implementation detail in Python 3.7: iterating a dict goes in the order the keys were inserted.

There is a third variant too — the split table (PEP 412, “key-sharing dictionary”): if many objects of one class have the same set of string attributes, they can share one and the same dk_indices and key part, each keeping its values in its own ma_values. This is an optimization for instance __dict__s, not for general-purpose dictionaries — the main text of this article is about the ordinary, “combined” dictionary.

Step 1: from key to number

The first thing that happens on d[key] = value or d[key] is a call to hash(key). What comes next depends heavily on the type of the key:

• For int the hash almost always equals the value: hash(n) == n for most integers (with reduction modulo the Mersenne prime 2⁶¹−1 on 64-bit builds — see sys.hash_info). The exception is -1. CPython reserves -1 as the error code for C functions returning Py_hash_t, so several of its hash functions (for bytes, float, pointers — see Python/pyhash.c) explicitly replace a computed -1 with -2. The same convention applies to int: hash(-1) == -2.
• For str (and bytes), since PEP 456 it is SipHash13, and with a seed that is random for every run of the process (PYTHONHASHSEED). This is a deliberate security decision: before PEP 456 a predictable string hash gave the classic "hash flooding" DoS attack through specially crafted keys. The practical consequence: hash("cpython") in two different runs of python3 is, as a rule, two different numbers.

Below is that same first step, key → hash(key), in interactive form. For int the real hash() value is shown; for str it is a deliberately simplified demonstration function (not SipHash), because a real string hash is by construction not reproducible across runs.

Step 2: from number to slot

A hash is an arbitrary integer, while the table is an array of dk_size slots, where dk_size is always a power of two. The initial candidate slot comes from the cheapest operation available here at all:

mask = dk_size - 1;
i = hash & mask;

& mask instead of % dk_size is the usual trick for powers of two: the low bits of hash are the remainder, with no division as such.

Collisions: the CPython probe sequence

Two different keys will almost inevitably produce the same i sooner or later. Here CPython uses neither linear probing nor a textbook scheme based on double hashing, but a recurrence of its own, taken straight from the comment in dictobject.c:

perturb = hash;
i = hash & mask;
 
while (slot_at(i)->occupied) {
    perturb >>= PERTURB_SHIFT;      /* PERTURB_SHIFT == 5 */
    i = (i*5 + perturb + 1) & mask;
}

The idea: ordinary linear probing (i = i + 1) is too regular — with the table partly filled it produces long collision runs that correlate with mask itself. The perturb term, shifted right by 5 bits at every step, gradually "mixes" the high bits of the original hash into the probe sequence — precisely the bits that & mask on its own never uses. The result is a pseudo-random but completely deterministic walk over all dk_size slots.

Check the formula yourself — the table below recomputes CPython's real probe sequence for the hash you enter and the slots you mark as occupied:

Table growth: when, and by how much

A hash table filled to the brim degenerates into a linear search — CPython never gets that far and keeps headroom. Three numbers from dictobject.c fully determine when and how the table grows:

#define PyDict_MINSIZE 8
#define USABLE_FRACTION(n) (((n) << 1)/3)   /* resize at 2/3 full */
#define GROWTH_RATE(d) ((d)->ma_used*3)

A fresh dictionary starts at dk_size = 8 and dk_usable = USABLE_FRACTION(8) = 5 — exactly what the comment in the source describes: "8 allows dicts with no more than 5 active entries". Every successful insertion lowers dk_usable by 1; when it would have to go negative, a resize runs before the insertion: the new minimum size is GROWTH_RATE(mp), that is ma_used * 3, and the actual new dk_size is the nearest power of two not smaller than that value. If there were no deletions, ma_used * 3 almost always lands in the range "the next power of two after doubling", hence the comment in the source: "dicts double in size when growing without deletions".

Interactive visualization

Step through six insertions into a table of 8 slots. Note the probing on the collision at step 3 and the growth at step 6 — the entry array is copied verbatim, and not one entry changes position.

The keys here are integers rather than strings, and that is deliberate: hash(n) == n, so every slot number below can be checked in your own interpreter, whereas a string hash is not reproducible across runs (see step 1).

The same dictionary in full, if you want to see for yourself:

import sys
 
d = {}
for k in (3, 6, 11, 1, 7):
    d[k] = "…"
print(sys.getsizeof(d))      # the table is still 8 slots
 
d[2] = "…"                   # the sixth insertion crosses the 2/3 threshold
print(sys.getsizeof(d))      # grown: dk_indices is now 16 slots
print(list(d))               # [3, 6, 11, 1, 7, 2] — insertion order survived

Update and delete: three different paths

Everything about inserting a new key has been said, but d[k] = v is also an update of a key that already exists, and del d[k] works quite differently again. The three paths behave differently, and the difference is visible to the naked eye.

Update: nothing moves

If the lookup found the key, insertdict never gets as far as creating an entry:

if (old_value != value) {
    uint64_t new_version = _PyDict_NotifyEvent(
            interp, PyDict_EVENT_MODIFIED, mp, key, value);
    assert(old_value != NULL);
    assert(!_PyDict_HasSplitTable(mp));
    if (DK_IS_UNICODE(mp->ma_keys)) {
        PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[ix];
        STORE_VALUE(ep, value);
    }
    else {
        PyDictKeyEntry *ep = &DK_ENTRIES(mp->ma_keys)[ix];
        STORE_VALUE(ep, value);
    }
    mp->ma_version_tag = new_version;
}
Py_XDECREF(old_value);

One field is overwritten — me_value — and the old value gets a Py_DECREF. Neither dk_indices nor me_key nor me_hash is touched, and dk_nentries and dk_usable do not change. Hence the practical consequence people often argue about: assigning to an existing key does not change iteration order. The key stays at its position in dk_entries, and therefore in iteration.

Deletion: a tombstone instead of an entry

delitem_common touches both structures. Below is its body, cut down to the writes to memory:

Py_ssize_t hashpos = lookdict_index(mp->ma_keys, hash, ix);
STORE_USED(mp, mp->ma_used - 1);
mp->ma_keys->dk_version = 0;
dictkeys_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
 
PyDictKeyEntry *ep = &DK_ENTRIES(mp->ma_keys)[ix];
old_key = ep->me_key;
STORE_KEY(ep, NULL);
STORE_VALUE(ep, NULL);
STORE_HASH(ep, 0);

In place of the index, the slot gets DKIX_DUMMY (−2) — a “tombstone”. The slot cannot be marked as empty, and the source says outright why:

If the slot became DKIX_EMPTY, a lookup for a key that once jumped over this slot further down the probe sequence because of a collision would stop right there — and a key sitting in the dictionary would stop being found.

The entry in dk_entries is zeroed in place: a hole is left at its position. And — most important for the next section — the free-capacity counter is not restored. The comment in the source explains that too: since tombstones remain in dk_indices, dk_usable cannot be raised, even though there are now fewer live keys.

The last frame is worth remembering separately: deleting a key and inserting it back is not the same as updating the value. The slot in dk_indices is reused (find_empty_slot stops at an empty slot and at a tombstone alike), but a new entry is created at the tail — and the key moves to the end of the iteration order.

So does dk_indices grow without bound?

The previous section adds up to an alarming picture: every insertion spends capacity, every deletion leaves garbage behind and returns nothing. Insert and delete for long enough and the table ought to swell without limit.

It ought not to, and here is why. The dk_usable capacity does leak away, but when it reaches zero the next insertion triggers a rebuild, and the size of the new table is computed from the number of live keys: GROWTH_RATE(mp) is ma_used * 3, and ma_used counts only the live ones. Dead entries and tombstones do not enter that calculation and simply disappear during the copy. So the size of the table is determined by how many keys the dictionary holds now, not by how many operations were performed on it.

Three things follow from this, each of them easy to check for yourself.

First: under a constant insert-then-delete cycle the dictionary does not grow. A million insert/delete pairs with a hundred live keys change the size exactly once, right at the start:

import sys
 
d = {i: i for i in range(100)}
prev, changes = sys.getsizeof(d), []
for i in range(1_000_000):
    d[("k", i)] = i
    del d[("k", i)]
    if sys.getsizeof(d) != prev:
        changes.append((i, prev, sys.getsizeof(d)))
        prev = sys.getsizeof(d)
 
print(len(d), changes)   # 100 [(70, 4688, 9304)]
print(sys.getsizeof(d))  # 9304 — and constant from here on

Second: the table can shrink as well. A dictionary of a thousand keys with ten of them left shrinks almost sixtyfold at the very first rebuild:

import sys
 
d = {i: i for i in range(1000)}
for i in range(990):
    del d[i]
print(sys.getsizeof(d))      # 36952 — the deletions returned nothing
 
for n in range(1, 400):      # insert/delete cycle: still 10 live keys
    d[("n", n)] = n
    del d[("n", n)]
print(sys.getsizeof(d))      # 632

Third: deletions on their own do not free memory. A rebuild happens only on insertion, so a dictionary that has been emptied and is written to no more keeps holding the old table:

import sys
 
d = {i: i for i in range(1000)}
for i in range(1000):
    del d[i]
print(len(d), sys.getsizeof(d))   # 0 36952 — empty, but the memory is held
 
d.clear()
print(sys.getsizeof(d))           # 64 — now it has been released

There is exactly one practical conclusion: if almost everything has been deleted from a large dictionary that will go on living for a long time, and no insertions into it are expected — call clear() or build a new dictionary. In every other case the mechanism cleans up after itself.

The frames in Fig. 3 and Fig. 4 are not a model but a measurement: the state of a real dictionary, read straight out of the interpreter's memory. The script below reproduces it in full (ctypes here reads private CPython structures — fine for taking a look, categorically unfit for working code).

import ctypes
import sys
 
class DictKeys(ctypes.Structure):
    _fields_ = [("dk_refcnt", ctypes.c_ssize_t),
                ("dk_log2_size", ctypes.c_uint8),
                ("dk_log2_index_bytes", ctypes.c_uint8),
                ("dk_kind", ctypes.c_uint8),
                ("dk_version", ctypes.c_uint32),
                ("dk_usable", ctypes.c_ssize_t),
                ("dk_nentries", ctypes.c_ssize_t)]
 
class Dict(ctypes.Structure):
    _fields_ = [("ob_refcnt", ctypes.c_ssize_t),
                ("ob_type", ctypes.c_void_p),
                ("ma_used", ctypes.c_ssize_t),
                ("ma_version_tag", ctypes.c_uint64),
                ("ma_keys", ctypes.POINTER(DictKeys)),
                ("ma_values", ctypes.c_void_p)]
 
def state(d):
    obj = Dict.from_address(id(d))
    keys = obj.ma_keys.contents
    size = 1 << keys.dk_log2_size
    base = ctypes.addressof(keys) + ctypes.sizeof(DictKeys)
    slots = list((ctypes.c_int8 * size).from_address(base))
    return (f"used={obj.ma_used} size={size} usable={keys.dk_usable} "
            f"nentries={keys.dk_nentries} bytes={sys.getsizeof(d)}\n  {slots}")
 
d = {1: 1, 2: 2, 3: 3}
print("three inserts", state(d))
d[1] = 100
print("update       ", state(d))   # the counters did not change
del d[2]
print("delete       ", state(d))   # slot 2 now holds -2, usable unchanged
d[2] = 22
print("insert back  ", state(d), list(d))   # [1, 3, 2] — the key moved to the end

Under the hood: version history

The most often misremembered fact about dictionaries is when insertion order became something you could rely on. That is not one event but two, exactly one release apart:

What here is a language guarantee and what is an implementation detail

Two levels are worth keeping apart:

• Language guarantee (safe to rely on in production): dictionaries preserve insertion order — since Python 3.7 this is part of the specification, not a side effect (see the 3.7 changelog). Whatever the key type — int, str, any hashable — dict[key] is amortized O(1).
• CPython implementation detail (may change in another version, or in PyPy/GraalPy): the specific numbers 8 / ⅔ / ×3, the PERTURB_SHIFT = 5 formula, the split into dk_indices/dk_entries itself, the key-sharing dict of PEP 412, dropping stored hashes for string keys in 3.11. Code explicitly tied to those numbers (rather than to the dictionary's public behavior) is a red flag in code review.