Chapter 6 · Senior Developer

LRU cache and data-structure choice

LRU cache · OrderedDict · eviction policy · data-structure trade-offsDEV-50643 of 84

A cache can't grow forever, so when it's full it has to throw something out — that decision is its eviction policy. LRU (Least Recently Used) is the common one: keep what you've touched recently, evict the item nobody has used for the longest. It bets that recently-used things will be wanted again soon, which holds for web pages, query results, and CPU caches alike.

The interesting part is the data-structure choice. You want two things to be fast: looking up a value by key, *and* evicting the oldest item. A plain dict gives O(1) lookup but no notion of order. A list keeps order but evicting from the front is O(n). The answer is collections.OrderedDict, which remembers insertion order and adds two O(1) tricks: move_to_end(key) shuffles a key to the 'most recent' end, and popitem(last=False) removes the *oldest* item.

So the algorithm is: on every access, move_to_end the key (mark it recently used); on insert past capacity, popitem(last=False) to evict the front. Both stay O(1) — that constant-time-for-both reasoning is exactly the kind of trade-off senior engineers weigh.

In real code you rarely hand-roll this: functools.lru_cache is the batteries-included version — a decorator that memoizes a function with an LRU eviction policy and a maxsize. Knowing how it works underneath is what lets you reason about its limits.

Syntax

from collections import OrderedDict

store = OrderedDict()
store["a"] = 1                    # newest goes to the end
store.move_to_end("a")           # mark 'a' as most-recently-used (O(1))
store.popitem(last=False)        # evict the OLDEST item (O(1))

# Batteries-included version:
import functools
@functools.lru_cache(maxsize=128)
def expensive(n): ...

Worked examples

A hand-rolled LRU cache on OrderedDict

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.store = OrderedDict()

    def get(self, key):
        if key not in self.store:
            return -1
        self.store.move_to_end(key)      # now most-recently-used
        return self.store[key]

    def put(self, key, value):
        self.store[key] = value
        self.store.move_to_end(key)
        if len(self.store) > self.capacity:
            self.store.popitem(last=False)  # evict oldest

c = LRUCache(2)
c.put("a", 1)
c.put("b", 2)
c.get("a")          # touch 'a' — 'b' is now the oldest
c.put("c", 3)       # over capacity -> evict 'b'
print(c.get("b"))   # -1  (gone)
print(c.get("a"))   # 1   (kept)
# Output:
# -1
# 1

move_to_end / popitem keep eviction order correct

from collections import OrderedDict

od = OrderedDict([("a", 1), ("b", 2), ("c", 3)])
od.move_to_end("a")              # 'a' jumps to the newest end
print(list(od.keys()))           # ['b', 'c', 'a']
od.popitem(last=False)           # remove the oldest (front)
print(list(od.keys()))           # ['c', 'a']
# Output:
# ['b', 'c', 'a']
# ['c', 'a']

functools.lru_cache — the batteries-included version

import functools

@functools.lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(30))                   # 832040  (fast — memoized)
print(fib.cache_info().hits > 0) # True
# Output:
# 832040
# True

Common mistakes & gotchas

popitem(last=False) vs the default

popitem() defaults to last=True — it removes the *newest* item, which is the wrong end for LRU and would evict what you just added. You must pass last=False to drop the oldest. One keyword is the whole difference between a working cache and a broken one.

Forgetting to move_to_end on a read

If get() doesn't move_to_end the key, reads don't count as 'recent use' — so a frequently-read item can still be evicted as if it were stale. The recency-update on access is the defining behaviour of LRU; skip it and you've built a plain insertion-order cache.

lru_cache needs hashable arguments and can leak memory

functools.lru_cache keys on the arguments, so they must be hashable — a list argument raises TypeError: unhashable type. And maxsize=None means unbounded: it never evicts, so a long-lived function can quietly grow the cache forever. Set a real maxsize for anything long-running.

Why it matters

Caching is one of the highest-leverage performance tools there is, and 'which structure makes both lookup and eviction O(1)?' is a textbook senior interview question precisely because it tests whether you reason about trade-offs or just memorise APIs. Picking the right data structure for the access pattern is the difference between code that scales and code that quietly degrades.