How does CPython's compact dict layout preserve insertion order?

### Before and after Up to CPython 3.5 a dict was one array of buckets, each bucket a triple of `(hash, key pointer, value pointer)` — 24 bytes on a 64-bit build. Open addressing needs slack to stay fast, so roughly a third of those 24-byte triples sat empty, and iteration walked the bucket array in whatever order the hash function scattered keys into it. That is why dicts were unordered. CPython 3.6 split the structure in two, an idea borrowed from PyPy: * a **sparse index array** — this is the hash table proper. It is sized to a power of two and every slot holds either an empty marker, a deleted marker, or a small integer: the position of the entry in the second array. * a **dense entries array** — the actual data, appended to in insertion order and never reordered. A dict holding `{"a": 1, "b": 2}` looks roughly like this: ```text index: [ -, 1, -, -, 0, -, -, - ] <- sparse, small ints entries: [ (hash_a, "a", 1), (hash_b, "b", 2) ] <- dense, append-only ``` ### The lookup path Looking up a key masks its hash down to the index array's size, reads that slot, and follows a probe sequence perturbed by the rest of the hash until it hits an empty slot or a match. What it finds in a slot is an integer, so it then jumps to `entries[i]` and compares — identity first, then the stored hash, then `__eq__`. Two indirections instead of one, in exchange for a much smaller table. (The probe strategy itself is general hash-table theory; what is CPython-specific is that the thing being probed is an array of *indices*, not of entries.) ### Where ordering comes from Insertion appends to `entries` and records the new position in the index slot. Nothing ever moves an entry backwards. Iteration ignores the index array entirely and scans `entries` front to back, skipping holes. So iteration order *is* insertion order, without a linked list or any bookkeeping — unlike `collections.OrderedDict`, which pays for a doubly linked list to get the same property plus order-sensitive equality and `move_to_end`. Growth preserves it too. When the table fills, a new, larger index array is built and the live entries are copied across **in their existing order**, then renumbered. A dict that has resized ten times still iterates in first-insertion order. ### Resizing CPython keeps two thirds of the index slots usable. Fill the last usable slot and the next insertion rebuilds the table, sized from the number of *live* entries — roughly three times that count, rounded up to a power of two — rather than doubling blindly. You can watch it happen: ```python import sys d, last = {}, sys.getsizeof({}) for i in range(200): d[i] = i if sys.getsizeof(d) != last: last = sys.getsizeof(d) print(len(d), last) # 1 224 / 6 352 / 11 632 / 22 1168 / 43 2264 / 86 4688 / 171 9304 ``` The jumps at 6, 11, 22, 43, 86, 171 are the two-thirds rule: a table of 8 slots keeps 5 usable, 16 keeps 10, 32 keeps 21, and so on. ### Per-entry memory Two details make the layout cheaper than it looks. **The index array uses the narrowest integer that can address the entries.** One byte per slot while the table has fewer than 256 slots, two bytes up to 65,536, then four, then eight. So the empty slack costs one or two bytes per slot rather than 24. **A dict whose keys are all `str` uses a narrower entry.** Since 3.11, such a table stores only the key and value pointers and drops the cached hash, because `str` objects cache their own hash internally. That is 16 bytes per entry instead of 24, and it is why a 1,000-key dict with string keys measures about 26 KB while the same dict with integer keys measures about 37 KB. ### Why it is asked The question separates people who memorized "dicts are ordered now" from people who know why. The two-array split explains the ordering guarantee, the memory reduction, why an empty slot is cheap, why deletion leaves a hole in the dense array, and why a resize is what compacts those holes away. Every one of those is a real production consequence, and they all fall out of one picture.