Skip to content

Python OrderedDict: Reordering and LRU Caches

  • Why OrderedDict existed, and what changed when dict started keeping insertion order.
  • The operations only OrderedDict offers: move_to_end, popitem(last=False) and order-sensitive equality.
  • How to build a small LRU cache, and when functools.lru_cache is the better tool.
  • The costs and surprises: memory, equality rules, update semantics and JSON round trips.

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.

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: OK
oldest = next(iter(viewed)) # peek at the oldest
viewed.pop(oldest) # evict it
print(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 recent
viewed.move_to_end("ORD-3", last=False) # pin to the front
print(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'})

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 with last=False. It raises KeyError for a missing key.
  • popitem(last=True) removes and returns a pair: last-in first-out by default, first-in first-out with last=False. A plain dict.popitem() takes no argument and always removes the last item.
  • Equality between two OrderedDict objects is order-sensitive, roughly list(a.items()) == list(b.items()). Equality between an OrderedDict and any other mapping ignores order, like a normal dict.
  • reversed() works on the mapping and on its keys(), values() and items() views.
  • The | and |= merge operators (Python 3.9, PEP 584) return and update an OrderedDict.
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 matters
print(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: LIFO
a["ORD_3"] = "pending"
a["ORD_1"] = "refunded" # updating a key keeps its position
print(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:

False
True 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).

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 OrderedDict
from 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-101
C-101 -> standard
loading C-207
C-207 -> gold
C-101 -> standard
loading C-315
C-315 -> standard
loading C-427
evicted C-207
C-427 -> gold
C-101 -> standard
loading C-207
evicted C-315
C-207 -> gold
order: ['C-427', 'C-101', 'C-207']
hits=2 misses=5

C-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).

  • Using OrderedDict only to keep insertion order. On Python 3.7 and later a dict already does that, with less memory and faster iteration. Keep OrderedDict for reordering or order-sensitive equality.
  • Expecting == to always respect order. It does only when both sides are OrderedDict. OrderedDict(...) == dict(...) ignores order.
  • Expecting an update to move the key. od[k] = v on an existing key keeps its position. Call move_to_end(k) if recency matters.
  • Calling popitem(last=False) on a plain dict. It fails with TypeError: dict.popitem() takes no keyword arguments. Use (k := next(iter(d)), d.pop(k)) or switch to OrderedDict.
  • Losing the type through JSON. json.loads returns a plain dict. Order survives, but if you need OrderedDict behavior again pass object_pairs_hook=OrderedDict.
  • Writing your own LRU for a pure function. functools.lru_cache is tested, thread-safe for its own bookkeeping and exposes cache_info().
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.

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 `

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.

  • Since Python 3.7, dict keeps insertion order; use it by default.
  • OrderedDict is 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_cache beats a hand-written LRU.
  • Dictionaries: the built-in mapping and its ordering guarantee.
  • collections module: OrderedDict alongside Counter, defaultdict, deque and namedtuple.
  • 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() returned OrderedDict before Python 3.8.