LRU Cache & Caching Structures

A cache keeps a small number of recently used results close at hand so you do not have to fetch or compute them again. Your browser caches images, a database caches pages of disk, a food delivery app caches the restaurant menu it showed you a minute ago. A cache has limited space, so it needs an eviction policy: when it is full, which item goes?

Least recently used (LRU) is the most common answer, and "design an LRU cache with O(1) get and put" is a very common interview question at product companies. In this lesson you will build it two ways, measure why it works, use Python's built-in version, and see the harder LFU variant.

Words you need

• Hit: the item is in the cache. Miss: it is not, so you fetch it from the slow source and usually store it.
• Hit rate: hits divided by total requests. A higher hit rate means fewer slow fetches.
• Capacity: the maximum number of items the cache holds.

LRU with OrderedDict

An LRU cache needs two things in O(1): find an item by key, and know the order of use. Python's collections.OrderedDict remembers insertion order and has two methods made for this job: move_to_end(key) marks an item as most recent, and popitem(last=False) removes the oldest.

from collections import OrderedDict

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

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)          # now the most recently used
        return self.data[key]

    def put(self, key, value):
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.capacity:
            old, _ = self.data.popitem(last=False)   # least recently used
            print("evicted", old)

menus = LRUCache(3)
menus.put("Haldiram's", "menu A")
menus.put("Bikanervala", "menu B")
menus.put("Saravana Bhavan", "menu C")
menus.get("Haldiram's")                  # used again, so it is fresh
menus.put("Paradise", "menu D")          # full: who goes?
print(list(menus.data))

evicted Bikanervala
['Saravana Bhavan', "Haldiram's", 'Paradise']

Bikanervala was evicted, not Haldiram's, because Haldiram's was read again after being added. All operations are O(1).

LRU from scratch: hash map plus doubly linked list

Interviewers usually want you to build what OrderedDict does inside. You need:

• A dict from key to node, for O(1) lookup.
• A doubly linked list of nodes in order of use, for O(1) unlink and append (see Linked Lists). Two sentinel nodes, head and tail, remove all the empty-list special cases. The node after head is the least recently used.

class Node:
    __slots__ = ("key", "value", "prev", "next")
    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = None

class LRU:
    def __init__(self, capacity):
        self.capacity, self.map = capacity, {}
        self.head, self.tail = Node(), Node()
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _append(self, node):                 # insert just before tail = most recent
        node.prev, node.next = self.tail.prev, self.tail
        self.tail.prev.next = node
        self.tail.prev = node

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return None
        self._unlink(node)
        self._append(node)
        return node.value

    def put(self, key, value):
        if key in self.map:
            self._unlink(self.map[key])
        node = Node(key, value)
        self.map[key] = node
        self._append(node)
        if len(self.map) > self.capacity:
            oldest = self.head.next
            self._unlink(oldest)
            del self.map[oldest.key]         # the node stores its key for this line

    def order(self):
        out, n = [], self.head.next
        while n is not self.tail:
            out.append(n.key)
            n = n.next
        return out

c = LRU(2)
c.put("otp:9876", "4821"); c.put("otp:9123", "1180")
print(c.get("otp:9876"), c.order())
c.put("otp:9555", "7302")
print(c.get("otp:9123"), c.order())

4821 ['otp:9123', 'otp:9876']
None ['otp:9876', 'otp:9555']

The node keeps its own key so that eviction can delete the right dict entry; forgetting this is the classic bug. Every operation touches a constant number of links, so get and put are O(1).

Why LRU works: measure the hit rate

Real traffic is skewed: a few items are requested very often, and recent requests predict near-future ones. The simulation below sends 20,000 requests where a small set of "popular" restaurants gets most of the traffic, and compares LRU with FIFO at the same capacity.

import random
from collections import OrderedDict, deque

def hit_rate_lru(requests, capacity):
    cache, hits = OrderedDict(), 0
    for key in requests:
        if key in cache:
            hits += 1
            cache.move_to_end(key)
        else:
            cache[key] = True
            if len(cache) > capacity:
                cache.popitem(last=False)
    return hits / len(requests)

def hit_rate_fifo(requests, capacity):
    cache, order, hits = set(), deque(), 0
    for key in requests:
        if key in cache:
            hits += 1                        # FIFO does not refresh on a hit
        else:
            cache.add(key)
            order.append(key)
            if len(cache) > capacity:
                cache.discard(order.popleft())
    return hits / len(requests)

random.seed(2026)
popular = [f"R{i}" for i in range(20)]
rare = [f"R{i}" for i in range(20, 2000)]
requests = [random.choice(popular) if random.random() < 0.8 else random.choice(rare)
            for _ in range(20000)]
for cap in [10, 25, 50]:
    print(f"capacity {cap:>2}: LRU {hit_rate_lru(requests, cap):.1%}  FIFO {hit_rate_fifo(requests, cap):.1%}")

capacity 10: LRU 30.3%  FIFO 29.0%
capacity 25: LRU 66.1%  FIFO 56.2%
capacity 50: LRU 80.2%  FIFO 70.3%

LRU wins because a popular item keeps getting refreshed and is rarely evicted, while FIFO throws it out on schedule even if it was used a moment ago. The gap depends on the workload, so production teams measure hit rates on real traffic before choosing a policy and capacity.

functools.lru_cache: caching function results

For caching a pure function's results, Python has a decorator. @functools.lru_cache(maxsize=128) (128 is the default) keeps the most recent results; @functools.cache is the same with no size limit. cache_info() reports hits and misses.

from functools import lru_cache

@lru_cache(maxsize=2)
def fare(source, destination):
    print(f"  computing {source} -> {destination}")
    return 10 * (len(source) + len(destination))

for trip in [("Rohtak", "Delhi"), ("Rohtak", "Delhi"), ("Pune", "Mumbai"),
             ("Kochi", "Kollam"), ("Rohtak", "Delhi")]:
    print(trip, fare(*trip))
print(fare.cache_info())

  computing Rohtak -> Delhi
('Rohtak', 'Delhi') 110
('Rohtak', 'Delhi') 110
  computing Pune -> Mumbai
('Pune', 'Mumbai') 100
  computing Kochi -> Kollam
('Kochi', 'Kollam') 110
  computing Rohtak -> Delhi
('Rohtak', 'Delhi') 110
CacheInfo(hits=1, misses=4, maxsize=2, currsize=2)

With room for only two results, Rohtak to Delhi was evicted and computed again. The arguments must be hashable (no lists), and the function should have no side effects that callers rely on, because a cached call does not run the body at all.

LFU in O(1): an overview

Least frequently used evicts the item with the fewest uses, breaking ties by least recent. An O(1) design keeps:

• key_to_value_and_count: a dict from key to its value and use count.
• buckets: a dict from count to an OrderedDict of keys with that count, oldest first.
• min_count: the smallest count present.

On every use, move the key from buckets[c] to buckets[c + 1], and if buckets[min_count] became empty, add 1 to min_count. To evict, pop the oldest key from buckets[min_count]. A new key always gets count 1, so min_count becomes 1. Pure LFU has a weakness: an item that was hugely popular last week can sit in the cache for ever. Real systems often add aging, or use hybrid policies.

Common mistakes

• Not storing the key in the node, so the evicted node's dict entry cannot be deleted.
• Forgetting to refresh on get. A read is a use; it must move the item to the most recent end.
• Updating an existing key without unlinking the old node, leaving a stale node in the list.
• Using a plain list for order, which makes remove() O(n).
• Caching functions with side effects or unhashable arguments with lru_cache.

Key points

• A cache trades memory for speed; the eviction policy decides what to drop when full.
• LRU evicts the item unused for the longest time and suits most real workloads.
• OrderedDict with move_to_end and popitem(last=False) gives an O(1) LRU in a few lines.
• From scratch: a dict for lookup plus a doubly linked list with sentinels for order.
• functools.lru_cache caches function results; check cache_info().
• LFU in O(1) uses count buckets and a min_count pointer.

from collections import OrderedDict

class TTLLRUCache:
    def __init__(self, capacity, ttl):
        self.capacity, self.ttl = capacity, ttl
        self.data = OrderedDict()            # key -> (value, stored_at)

    def get(self, key, now):
        if key not in self.data:
            return None
        value, stored_at = self.data[key]
        if now - stored_at > self.ttl:
            del self.data[key]               # expired
            return None
        self.data.move_to_end(key)
        return value

    def put(self, key, value, now):
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = (value, now)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)

prices = TTLLRUCache(capacity=2, ttl=30)
prices.put("onion", 40, now=0)
print(prices.get("onion", now=20))       # still fresh
print(prices.get("onion", now=45))       # 45 seconds old: expired
prices.put("tomato", 30, now=50)
prices.put("potato", 25, now=51)
prices.put("ginger", 120, now=52)        # evicts tomato (least recently used)
print(list(prices.data))

40
None
['potato', 'ginger']