vault

Dictionary Ordering Assumptions

17 min read

Dictionary Ordering Assumptions

Since Python 3.7 a dict iterates in insertion order, and that is a language guarantee — portable across every conforming implementation, not a CPython quirk you rely on at your peril. The documentation is explicit: “Changed in version 3.7: Dictionary order is guaranteed to be insertion order. This behavior was an implementation detail of CPython from 3.6” (Python 3.14 — Built-in Types). That single sentence packs three distinct facts — unordered before 3.6, ordered-but-unofficial in 3.6, ordered-and-official in 3.7 — and the traps that remain all live in the gap between “iteration order is defined” and the things programmers assume follow from it but don’t. The compact insertion-ordered layout that makes this work is the subject of CPython Dict Internals; this note is about what you may and may not lean on.

Mental Model — Order Is Defined, But It’s Insertion Order, Not Logical Order

The right mental model is: a dict remembers the sequence in which keys were first inserted, and iterates in that sequence — full stop. It does not track “the order you’d expect,” “sorted order,” or “the order after your edits in some intuitive sense.” Every remaining trap is a case where the programmer’s intuition about order diverges from the literal first-insertion rule, or assumes order matters somewhere it doesn’t (equality), or relies on the guarantee in a context where it never applied (set, pre-3.7).

flowchart TD
    A["What is GUARANTEED (>=3.7, all impls)"] --> A1["iteration / list(d) / keys / values / items<br/>= first-insertion order"]
    A --> A2["popitem() removes the LAST-inserted pair (LIFO)"]
    B["What is NOT what intuition expects"] --> B1["update existing key: position UNCHANGED"]
    B --> B2["del + re-insert key: moves to the END"]
    B --> B3["dict == dict: ORDER-INSENSITIVE<br/>{1:1,2:2} == {2:2,1:1} is True"]
    C["What does NOT carry an order guarantee"] --> C1["set / frozenset — hash-ordered, never insertion"]
    C --> C2["pre-3.7 dicts / non-CPython pre-3.7"]

The diagram sorts the territory into three buckets. Left: the things the language promises (insertion-order iteration; LIFO popitem). Middle: behaviours that are well-defined but routinely surprise people — updating a key keeps its slot, but deleting-then-reinserting sends it to the back, and crucially dict equality ignores order entirely. Right: places where no order guarantee exists at all, chiefly set. The insight: “dicts are ordered” is true but narrow — it is exactly first-insertion iteration order, and nothing more.

The History, Precisely

Three eras, each verifiable from primary docs:

  1. Before 3.6 — genuinely unordered. A dict could iterate keys in any order, and the order could change between runs or after resizes. Code that relied on order was simply buggy.
  2. 3.6 — ordered, but an implementation detail. CPython 3.6 reimplemented dict with the compact, insertion-ordered layout (see CPython Dict Internals); iteration happened to follow insertion order. But the 3.6 What’s New warned this was not to be relied on: “The order-preserving aspect of this new implementation is considered an implementation detail and should not be relied upon” (Python 3.6 What’s New). On 3.6, ordered code worked on CPython but was non-portable.
  3. 3.7 — ordered by the language spec. The guarantee was promoted from “CPython does this” to “the language does this,” so it is now portable to any conforming implementation. This is the line quoted in the opening blockquote.

The practical upshot: on 3.7+ CPython you may rely on dict order freely. On 3.6 rely on it only if you never run on another implementation. On anything older, or any pre-3.7 alternative implementation, do not rely on it at all.

The 3.6 caveat is worth quoting in full, because it explicitly anticipated the 3.7 promotion: “The order-preserving aspect of this new implementation is considered an implementation detail and should not be relied upon (this may change in the future)” (Python 3.6 What’s New) — and it did change, in 3.7.

A piece of history that surprises most Python programmers: CPython was not first. The compact, insertion-ordered dict design originated as a proposal by Raymond Hettinger on the python-dev mailing list in December 2012, and PyPy shipped it before CPython did — PyPy’s blog post “Faster, more memory efficient and more ordered dictionaries on PyPy” (22 January 2015) announced that “the new design, besides being more memory efficient, is ordered by design: it preserves the insertion order,” explicitly “based on an idea by Raymond Hettinger on python-dev” (PyPy blog, 2015). CPython’s own compact reimplementation landed roughly a year and a half later, in 3.6 (released late 2016). The same post notes the design also made PyPy’s collections.OrderedDict “a thin subclass of dict” — the exact relationship CPython arrived at later. The portability lesson cuts both ways: for the 2015–2016 window, code relying on insertion order ran correctly on PyPy but not on contemporary CPython — the reverse of the “CPython is the reference” intuition. Today (3.7+) the order is guaranteed by the language, so neither implementation is special; but the episode is a clean reminder that “implementation detail” is exactly the category of thing that differs between implementations until a PEP nails it down.

Trap 1 — Update Keeps Position, Delete+Reinsert Moves to the End

This is the most common surprise, and the two halves point opposite ways. Updating an existing key’s value leaves the key in its original position — the key was already inserted, so first-insertion order is untouched:

>>> d = {'a': 1, 'b': 2, 'c': 3}
>>> d['a'] = 99          # update existing key's value
>>> list(d)
['a', 'b', 'c']          # 'a' stays first

But deleting a key and then inserting it again counts as a new first insertion, so it lands at the end:

>>> d = {'a': 1, 'b': 2, 'c': 3}
>>> del d['a']
>>> d['a'] = 1
>>> list(d)
['b', 'c', 'a']          # 'a' is now last

The trap bites when code does an “in-place refresh” — pop a key and re-add it to update it — under the false belief that order is preserved. It isn’t; the refreshed key jumps to the back. If you need to update a value, assign to it (d[k] = new); only delete-then-add when you actually want the key reordered to the end. (This delete+reinsert move is, incidentally, exactly how an LRU cache promotes a key — see OrderedDict below.)

Why delete-then-reinsert moves to the end is a direct consequence of the compact layout (the full mechanism is CPython Dict Internals). A dict stores its pairs in a dense entries array in insertion order, with a separate sparse hash index pointing into it. Inserting a brand-new key appends to the entries array — that append is what defines “last.” Deleting a key does not compact the array; it tombstones the slot, leaving a gap that is not reused for new insertions until the whole dict is rebuilt (which happens on resize/compaction, not on a single delete). So when you delete 'a' and insert 'a' again, the original slot stays dead and the re-inserted 'a' is appended after every surviving key — hence it lands last. Updating an existing key’s value, by contrast, finds the live entry in place and overwrites only the value field; the entries array is untouched and position is preserved. The asymmetry — update keeps position, delete+reinsert appends — falls straight out of “new keys append, deletes tombstone.” A subtle corollary: because deletes leave gaps, a dict that has had many deletions can carry dead slots in its entries array until the next resize compacts them; this never affects iteration order (deleted slots are skipped) but it is why a heavily-churned dict can use more memory than its live size suggests — again, see CPython Dict Internals.

Trap 2 — set Does NOT Preserve Insertion Order

A dangerously common conflation: “dicts are ordered, so sets are too.” They are not. A set (and frozenset) is an open-addressed hash table with no insertion-order bookkeeping (see CPython Set Internals); iteration order is determined by hash values and table size, and is effectively arbitrary from the programmer’s view:

>>> list({3, 1, 2, 'x', 'aaa', 'bbb'})
[1, 2, 3, 'bbb', 'x', 'aaa']     # NOT insertion order; hash-ordered

frozenset is the same story — list(frozenset([3,1,2,'x','aaa','bbb'])) gives [1, 2, 3, 'aaa', 'bbb', 'x'], hash-ordered, not insertion-ordered. The docs give set and frozenset no ordering guarantee at all. The classic bug: “dedupe while preserving order” written as list(set(items)), which deduplicates and scrambles. The order-preserving dedupe uses a dict instead, precisely because dicts do guarantee order:

>>> list(dict.fromkeys(['b', 'a', 'b', 'c', 'a']))
['b', 'a', 'c']                  # first-seen order, duplicates removed

dict.fromkeys(iterable) builds a dict whose keys are the iterable’s elements (values default to None); because the dict preserves first-insertion order and silently ignores re-insertions of an existing key, the result is the input with later duplicates dropped, in original order. Wrapping list(...) then recovers the deduplicated sequence. This is the canonical order-preserving-dedupe idiom and the reason dict.fromkeys shows up far more often for deduplication than for its nominal “build a dict from keys” purpose. Reach for it, not set, whenever order matters.

Trap 3 — **kwargs and JSON Do Preserve Order (don’t conflate with set)

The flip side of Trap 2: people sometimes over-correct and assume **kwargs is unreliable. It is not — **kwargs preserves the call-site argument order, guaranteed since 3.6 by PEP 468 — “Preserving the order of **kwargs in a function” (Status: Final, Python-Version 3.6):

>>> def f(**kw): return list(kw)
>>> f(z=1, a=2, m=3, b=4)
['z', 'a', 'm', 'b']             # call-site order, preserved

Likewise, json.loads builds a regular dict, so on 3.7+ it preserves the key order from the JSON text:

>>> import json
>>> list(json.loads('{"z":1,"a":2,"m":3}'))
['z', 'a', 'm']

The subtlety the brief flags as “old-JSON”: this preservation only holds because the backing object is an ordered dict — i.e. on 3.7+. The trap is assuming order survives a round-trip through a system that doesn’t use an ordered map (an older parser, a different language’s JSON library, or a code path that funnels keys through a set). JSON the format defines objects as unordered; Python’s parser happens to preserve order because its target type does. The mirror-image control on the output side is json.dumps(obj, sort_keys=...): by default json.dumps emits keys in the dict’s iteration order (json.dumps({'z':1,'a':2}) → '{"z": 1, "a": 2}'), but sort_keys=True forces lexicographic key order ('{"a": 2, "z": 1}') regardless of insertion order — the standard move when you need byte-stable JSON (cache keys, signatures, diff-friendly fixtures) that does not depend on insertion order at all.

Dict-merge operators preserve order too

Two ways to merge dicts both preserve order, and both follow the same rule — left keys first, then the right operand’s new keys appended in its order. The {**a, **b} dict-display unpacking syntax arrived in Python 3.5 via PEP 448 — Additional Unpacking Generalizations (Status: Final, Python-Version 3.5); its order-preserving behavior, however, is not a property of the syntax but of the underlying dict — it became an implementation detail in 3.6 and a language guarantee in 3.7, exactly like every other dict-order claim in this note. With that distinction in mind:

>>> list({**{'a': 1, 'b': 2}, **{'c': 3, 'a': 9}})
['a', 'b', 'c']                  # 'a' keeps its original slot; only its value updates to 9

The | (union) and |= (in-place update) operators, added in Python 3.9 by PEP 584 — Add Union Operators To dict (Status: Final, Python-Version 3.9), behave identically:

>>> list({'a': 1, 'b': 2} | {'c': 3, 'a': 9})
['a', 'b', 'c']

PEP 584 makes the ordering explicit: “each newly added key (and its value) being appended to the current sequence.” So a key present in both operands keeps its left-hand position but takes the right-hand value — the same update-keeps-position rule as Trap 1, applied across a merge. The trap to avoid is assuming a merged-in key from the right operand jumps ahead of existing keys; it does not — only genuinely new keys append, and they append in the right operand’s order.

Trap 4 — dict == Is Order-Insensitive

Even though iteration order is defined, equality ignores it. The language reference is explicit: “Mappings (instances of dict) compare equal if and only if they have equal (key, value) pairs” (Python 3.14 — Comparisons) — order is not part of the test:

>>> {'a': 1, 'b': 2} == {'b': 2, 'a': 1}
True                              # same pairs, different insertion order

The trap appears in tests: asserting result == expected on two dicts will not catch a wrong ordering, because == can’t see order. If you genuinely need to assert order, compare the materialised key sequences — list(result) == list(expected) — or use an OrderedDict on both sides (next section). Conversely, do not write order-sensitive dict comparisons by hand expecting == to honour order; it won’t.

What OrderedDict Is Still For

Since 3.7 a plain dict covers most of what collections.OrderedDict historically provided — the docs say so directly: “They have become less important now that the built-in dict class gained the ability to remember insertion order (this new behavior became guaranteed in Python 3.7)” (Python 3.14 — collections). But three distinct capabilities remain OrderedDict-only:

  1. Order-sensitive equality. “The equality operation for OrderedDict checks for matching order” (same source). So OrderedDict([('a',1),('b',2)]) == OrderedDict([('b',2),('a',1)]) is False, where the plain-dict equivalent is True. This makes OrderedDict the clean tool for asserting order in tests.
  2. move_to_end(key, last=True). Reposition an existing key to either end without delete-and-reinsert: “Move an existing key to either end of an ordered dictionary. The item is moved to the right end if last is true (the default) or to the beginning if last is false.” Plain dict has no equivalent operation.
  3. popitem(last=True). OrderedDict.popitem takes an argument: “The pairs are returned in LIFO order if last is true or FIFO order if false.” A plain dict.popitem() is always LIFO with no choice. Plus, per the docs, OrderedDict is “designed to be good at reordering operations,” so frequent move_to_end/reorder workloads (LRU caches) are its niche.

dict.popitem() Is LIFO Since 3.7

A direct consequence of insertion order: plain dict.popitem() removes and returns the last-inserted pair — “Remove and return a (key, value) pair from the dictionary. Pairs are returned in LIFO order” (Python 3.14 — Built-in Types), with “Changed in version 3.7: LIFO order is now guaranteed. In prior versions, popitem() would return an arbitrary (key, value) pair.”

>>> d = {'a': 1, 'b': 2, 'c': 3}
>>> d.popitem()
('c', 3)                          # last in, first out

The trap here is pre-3.7 code (or non-CPython pre-3.7) that called popitem() expecting arbitrary removal, or post-3.7 code that wants FIFO from a plain dict — there is no FIFO popitem on dict; use OrderedDict(...).popitem(last=False) or pop the first key explicitly (d.pop(next(iter(d)))).

The dict Subclasses — Counter, defaultdict, ChainMap

The three workhorse mappings in collections each have an ordering story, and only one of them surprises people.

defaultdict is a transparent dict subclass — it inherits insertion-order iteration unchanged. The only wrinkle is that reading a missing key via __getitem__ triggers the factory and inserts that key (that is the whole point of defaultdict), so a lookup can append a new key to the order. Iterating defaultdict otherwise behaves exactly like dict. The docs note Counter (and by extension the family) “inherited the capability to remember insertion order” as of 3.7 (Python 3.14 — collections).

Counter also iterates in insertion order, but its signature method most_common() sorts by count, descending, with ties broken by first-encountered order — the docs are explicit: “Elements with equal counts are ordered in the order first encountered”:

>>> from collections import Counter
>>> list(Counter('abracadabra'))         # plain iteration: insertion order
['a', 'b', 'r', 'c', 'd']
>>> Counter('abracadabra').most_common(3) # by count desc; ties = first-seen
[('a', 5), ('b', 2), ('r', 2)]           # 'b' before 'r': both count 2, 'b' seen first

The trap is conflating these two orders — for x in counter is not most-common order; you must call most_common() for that, and you must not assume ties break alphabetically (they break by first appearance).

ChainMap is the genuine surprise. A ChainMap searches its underlying maps first-to-last for lookups (“Lookups search the underlying mappings successively until a key is found”), but iterates last-to-first — “the iteration order of a ChainMap is determined by scanning the mappings last to first” (same source), deduplicating so each key appears once:

>>> from collections import ChainMap
>>> cm = ChainMap({'z': 1, 'a': 2}, {'m': 3, 'a': 9})
>>> cm['a']                # lookup: FIRST map wins
2
>>> list(cm)               # iteration: scans LAST map first, then dedups
['m', 'a', 'z']

So for the shared key 'a', the value comes from the first map (2) while its position in iteration is governed by the last-to-first scan. The rationale is that last-to-first iteration makes the first (highest-priority) map’s entries appear last and thus “win” when you build a flat dict from the chain via dict(cm) — later writes overwrite earlier ones, so the high-priority map’s values survive. This is easy to get backwards; if you need a flattened, priority-correct dict, dict(cm) already does the right thing precisely because of this iteration order.

Real-World Bugs This Has Caused

The ordering gap is not academic — it has produced several recurring classes of production and test failures:

  • Pre-3.7 test flakiness. A test that asserted on the repr of a dict, or serialized a dict to a string and compared it, would pass or fail depending on the run’s hash randomization (PYTHONHASHSEED), because pre-3.6 dict iteration order depended on hash values. The same test suite would be green on one CI run and red on the next with no code change. The 3.7 guarantee eliminated this for CPython, but tests that still target older interpreters, or that route keys through a set, retain the flakiness.
  • Config-merge nondeterminism. Layered-configuration systems that merge dicts (defaults ← file ← environment ← CLI) and then serialize the result — to a cache key, a hash, a generated file — produced different bytes for the same logical config when the merge order was not pinned. Even on 3.7+ this resurfaces if any layer passes through a set or an unordered intermediate. The fix is either to pin order explicitly or to canonicalize on output with json.dumps(..., sort_keys=True).
  • Non-CPython portability. Code written and tested only on CPython 3.6 silently assumed order, then broke on an alternative implementation that had not (yet) adopted the guarantee. The cruel inverse also happened in 2015–2016: code that did rely on order ran on PyPy but failed on contemporaneous CPython. After 3.7 the language guarantee covers conforming implementations, but anything pre-3.7 — on any implementation — is a portability hazard.

Diagnosis

  • Order “randomly” wrong only on some runs / some Pythons: you are relying on dict order under 3.6-or-earlier semantics, or have routed keys through a set somewhere. Pin the Python version; search the path for set(...); check PYTHONHASHSEED is not what’s actually varying.
  • A reordering refresh that sends keys to the back: look for del d[k]; d[k] = ... or d[k] = d.pop(k) patterns — these reorder. Replace with plain assignment if you meant to preserve position.
  • A test that should catch reordering but passes anyway: the assertion is dict == dict, which is order-blind. Switch to list(a) == list(b) or OrderedDict.
  • for x in counter not in most-common order: plain Counter iteration is insertion order; you wanted counter.most_common().
  • ChainMap iterating “backwards”: that is by design — last-to-first; the value still comes from the first map on lookup.

See Also

Graph View

Backlinks