Python OrderedDict: Reordering and LRU Caches
What you’ll learn
Section titled “What you’ll learn”- Why
OrderedDictexisted, and what changed whendictstarted keeping insertion order. - The operations only
OrderedDictoffers:move_to_end,popitem(last=False)and order-sensitive equality. - How to build a small LRU cache, and when
functools.lru_cacheis the better tool. - The costs and surprises: memory, equality rules, update semantics and JSON round trips.
Summary
Section titled “Summary”collections.OrderedDict is a dict subclass that remembers insertion order and is built for reordering. It was added in Python 3.1 (PEP 372). Since Python 3.7 the language guarantees that a plain dict also preserves insertion order, so OrderedDict is no longer needed just to keep keys in order. It still earns its place when you move keys to either end, pop from the front, or need two mappings to compare equal only when their order matches. The documentation describes it as designed to be “good at reordering operations”, with space efficiency and iteration speed as secondary goals.
The problem it solves
Section titled “The problem it solves”Before Python 3.6, iteration order of a dict was arbitrary, and OrderedDict was the only standard way to keep keys in the order they were added. CPython 3.6 reimplemented dict with a compact, order-preserving layout, and Python 3.7 declared insertion order part of the language. That solved “keep the order”.
The remaining problem is “change the order cheaply”. Picture an OrdersPortal agent screen that remembers recently viewed orders and evicts the oldest. A plain dict can move a key to the end with d[k] = d.pop(k) and find the oldest with next(iter(d)), but it has no efficient way to move a key to the front. OrderedDict names these operations and supports both ends.
The samples on this page are plain scripts: save each as a .py file and run it with python3 file.py. They were run on CPython 3.14.6 and the output below is from that run. Python 3.12 and later print an OrderedDict as OrderedDict({...}); Python 3.11 and earlier print a list of pairs such as OrderedDict([('ORD-2', 'Lin')]).
from collections import OrderedDict
# Recently viewed orders for one OrdersPortal agent, oldest first.# Before: a plain dict can do it, but "move to front" has no cheap equivalent.viewed = {"ORD-1": "Ada", "ORD-2": "Lin", "ORD-3": "Sam"}viewed["ORD-1"] = viewed.pop("ORD-1") # move to the end: OKoldest = next(iter(viewed)) # peek at the oldestviewed.pop(oldest) # evict itprint(viewed)
# After: OrderedDict names the operations and supports both ends.viewed = OrderedDict({"ORD-1": "Ada", "ORD-2": "Lin", "ORD-3": "Sam"})viewed.move_to_end("ORD-1") # most recentviewed.move_to_end("ORD-3", last=False) # pin to the frontprint(viewed.popitem(last=False)) # evict from the front (FIFO)print(viewed)Output:
{'ORD-3': 'Sam', 'ORD-1': 'Ada'}('ORD-3', 'Sam')OrderedDict({'ORD-2': 'Lin', 'ORD-1': 'Ada'})How it works
Section titled “How it works”An OrderedDict supports every dict operation and adds the following:
move_to_end(key, last=True)moves an existing key to the right end, or to the left end withlast=False. It raisesKeyErrorfor a missing key.popitem(last=True)removes and returns a pair: last-in first-out by default, first-in first-out withlast=False. A plaindict.popitem()takes no argument and always removes the last item.- Equality between two
OrderedDictobjects is order-sensitive, roughlylist(a.items()) == list(b.items()). Equality between anOrderedDictand any other mapping ignores order, like a normal dict. reversed()works on the mapping and on itskeys(),values()anditems()views.- The
|and|=merge operators (Python 3.9, PEP 584) return and update anOrderedDict.
from collections import OrderedDict
a = OrderedDict(ORD_1="paid", ORD_2="shipped")b = OrderedDict(ORD_2="shipped", ORD_1="paid")
print(a == b) # OrderedDict vs OrderedDict: order mattersprint(a == dict(b), dict(a) == dict(b)) # with a plain dict: order ignored
print(list(reversed(a)), list(reversed(a.items())))print(a.popitem()) # last=True: LIFOa["ORD_3"] = "pending"a["ORD_1"] = "refunded" # updating a key keeps its positionprint(list(a))print(a | {"ORD_4": "paid"}) # merge operator, Python 3.9+
try: a.move_to_end("ORD_99")except KeyError as exc: print("KeyError:", exc)Output:
FalseTrue True['ORD_2', 'ORD_1'] [('ORD_2', 'shipped'), ('ORD_1', 'paid')]('ORD_2', 'shipped')['ORD_1', 'ORD_3']OrderedDict({'ORD_1': 'refunded', 'ORD_3': 'pending', 'ORD_4': 'paid'})KeyError: 'ORD_99'Two details follow from the output. Assigning to an existing key does not move it, so “order of last update” needs an explicit move_to_end (the documentation’s LastUpdatedOrderedDict recipe does exactly that in __setitem__). And the mixed comparison a == dict(b) is True, which lets an OrderedDict stand in anywhere a dict is expected.
The cost is memory. CPython has implemented OrderedDict in C since Python 3.5, but it still keeps a separate ordering structure next to the hash table. For 1,000 string keys, sys.getsizeof reported 26,032 bytes for a dict and 74,480 bytes for the equivalent OrderedDict on CPython 3.14.6 (an implementation detail that varies by version and platform).
Realistic example
Section titled “Realistic example”OrdersPortal looks up customer profiles from a slow service on every order page. A small least-recently-used (LRU) cache keeps the three most recent profiles: a hit moves the key to the end, and an overflow evicts from the front.
from collections import OrderedDictfrom collections.abc import Callable, Hashable
class LRUCache: """Keep the most recently used `maxsize` results; evict the oldest."""
def __init__(self, loader: Callable[[Hashable], object], maxsize: int = 3): self._loader = loader self._maxsize = maxsize self._data: OrderedDict[Hashable, object] = OrderedDict() self.hits = self.misses = 0
def get(self, key: Hashable) -> object: if key in self._data: self._data.move_to_end(key) # mark as most recently used self.hits += 1 return self._data[key] self.misses += 1 value = self._loader(key) self._data[key] = value # new keys go to the end if len(self._data) > self._maxsize: evicted, _ = self._data.popitem(last=False) # oldest first print(f" evicted {evicted}") return value
def invalidate(self, key: Hashable) -> None: self._data.pop(key, None)
def keys_oldest_first(self) -> list[Hashable]: return list(self._data)
def load_customer(customer_id): # Stands in for a slow call to https://api.example.test/customers/<id> print(f" loading {customer_id}") return {"id": customer_id, "tier": "gold" if customer_id.endswith("7") else "standard"}
cache = LRUCache(load_customer, maxsize=3)for cid in ["C-101", "C-207", "C-101", "C-315", "C-427", "C-101", "C-207"]: print(cid, "->", cache.get(cid)["tier"])
print("order:", cache.keys_oldest_first())print(f"hits={cache.hits} misses={cache.misses}")Output:
loading C-101C-101 -> standard loading C-207C-207 -> goldC-101 -> standard loading C-315C-315 -> standard loading C-427 evicted C-207C-427 -> goldC-101 -> standard loading C-207 evicted C-315C-207 -> goldorder: ['C-427', 'C-101', 'C-207']hits=2 misses=5C-207 is evicted first because the second request for C-101 moved it to the end, leaving C-207 as the oldest. The explicit class is worth writing when you need invalidate(), per-entry expiry or visibility into the order; the Python documentation shows a TimeBoundedLRU recipe built the same way. The class is not thread-safe: guard get with a threading.Lock if several threads share it.
When you only need to memoize a pure function, functools.lru_cache(maxsize=3) gives the same eviction behavior with no code to maintain. Decorating an equivalent load_customer_tier and making the same seven calls reports CacheInfo(hits=2, misses=5, maxsize=3, currsize=3).
Common mistakes
Section titled “Common mistakes”- Using
OrderedDictonly to keep insertion order. On Python 3.7 and later adictalready does that, with less memory and faster iteration. KeepOrderedDictfor reordering or order-sensitive equality. - Expecting
==to always respect order. It does only when both sides areOrderedDict.OrderedDict(...) == dict(...)ignores order. - Expecting an update to move the key.
od[k] = von an existing key keeps its position. Callmove_to_end(k)if recency matters. - Calling
popitem(last=False)on a plain dict. It fails withTypeError: dict.popitem() takes no keyword arguments. Use(k := next(iter(d)), d.pop(k))or switch toOrderedDict. - Losing the type through JSON.
json.loadsreturns a plaindict. Order survives, but if you needOrderedDictbehavior again passobject_pairs_hook=OrderedDict. - Writing your own LRU for a pure function.
functools.lru_cacheis tested, thread-safe for its own bookkeeping and exposescache_info().
When to use it and when not to
Section titled “When to use it and when not to”| Need | dict (3.7+) |
OrderedDict |
functools.lru_cache |
collections.deque |
|---|---|---|---|---|
| Keep insertion order | Yes | Yes | Not applicable | Yes (sequence) |
| Move a key to the end | d[k] = d.pop(k) |
move_to_end(k) |
Automatic on hit | Not keyed |
| Move a key to the front | No efficient way | move_to_end(k, last=False) |
No | Not keyed |
| Pop oldest item | next(iter(d)) then pop |
popitem(last=False) |
Automatic eviction | popleft() |
Order-sensitive == |
No | Yes, between two OrderedDicts |
No | Yes |
| Memory | Lower | Higher | Managed for you | Low |
Pick OrderedDict for LRU and MRU structures with custom rules, for “pin to top” lists, and when tests or protocols must compare ordering. Pick a dict for everything else.
Compatibility
Section titled “Compatibility”| Version | Change |
|---|---|
| 3.1 | OrderedDict added (PEP 372; also in 2.7). |
| 3.2 | move_to_end() added. |
| 3.5 | Reimplemented in C; keys(), values() and items() views support reversed(). |
| 3.6 | Keyword-argument order is preserved by the constructor and update() (PEP 468); CPython’s dict becomes compact and order-preserving as an implementation detail. |
| 3.7 | Insertion order of dict becomes a language guarantee. |
| 3.8 | dict and its views support reversed(); namedtuple._asdict() returns dict instead of OrderedDict. |
| 3.9 | ` |
Interview questions
Section titled “Interview questions”1. Dicts are ordered now. Why does OrderedDict still exist?
Because it is optimized for reordering rather than for plain mapping. It offers move_to_end at both ends, popitem(last=False) and order-sensitive equality between OrderedDict objects. The documentation also notes its algorithm handles frequent reordering better than dict, which is why it is used for LRU caches.
2. What does OrderedDict(a=1, b=2) == {"b": 2, "a": 1} return?
True. Comparison with any non-OrderedDict mapping is order-insensitive; only OrderedDict versus OrderedDict checks order. This keeps it substitutable for a normal dict.
3. How do you emulate od.popitem(last=False) with a plain dict?
k = next(iter(d)); d.pop(k), or as one expression (k := next(iter(d)), d.pop(k)). Moving a key to the front has no efficient plain-dict equivalent.
4. Senior scenario: OrdersPortal’s pricing service caches exchange rates in a module-level OrderedDict LRU, and under load the hit rate is fine but rates are sometimes stale and occasional KeyErrors appear. What do you change?
Staleness means the cache needs expiry: store (timestamp, value) and treat old entries as misses, as the documentation’s TimeBoundedLRU recipe does, using time.monotonic(). The KeyErrors point to unsynchronized access from several threads, for example one thread evicting a key between another thread’s membership check and move_to_end. Protect the check-move-read sequence with a lock, or replace the hand-written cache with functools.lru_cache plus explicit cache_clear() on a schedule if per-entry expiry is not required. Also bound the size from production data, and expose hits and misses as metrics.
Key takeaways
Section titled “Key takeaways”- Since Python 3.7,
dictkeeps insertion order; use it by default. OrderedDictis for reordering:move_to_end,popitem(last=False)and order-sensitive equality.- It costs noticeably more memory than a
dict. - Updating an existing key never moves it; eviction logic must call
move_to_end. - For memoizing pure functions,
functools.lru_cachebeats a hand-written LRU.
Related pages
Section titled “Related pages”- Dictionaries: the built-in mapping and its ordering guarantee.
- collections module:
OrderedDictalongsideCounter,defaultdict,dequeandnamedtuple. - lru_cache: the standard memoizing LRU decorator.
- deque: O(1) operations at both ends of a sequence.
- ChainMap: layered lookups across several mappings.
- namedtuple: whose
_asdict()returnedOrderedDictbefore Python 3.8.
Official references
Section titled “Official references”- collections.OrderedDict (Python 3.14 docs)
- OrderedDict examples and recipes (Python 3.14 docs)
- Mapping types: dict (Python 3.14 docs)
- What’s New in Python 3.7: dict insertion order
- PEP 372: Adding an ordered dictionary to collections
- PEP 468: Preserving keyword argument order
- functools.lru_cache (Python 3.14 docs)