LRU cache explained: how it works, code and complexity

What problem an LRU cache solves

A cache keeps the results of slow operations, such as database queries, web requests or expensive computations, so repeated requests are answered quickly. Memory is limited, so the cache must decide what to throw away when it is full. LRU bets that data used recently will be used again soon, and data not touched for a long time probably will not. This bet works well for many real workloads, which is why LRU and its approximations appear in CPU caches, operating system page caches, databases, web servers and CDNs.

The idea: two structures working together

We need two things to be fast: finding a key, and knowing which key is the least recently used. A hash map alone has no order. A list alone is slow to search. Together they do both:

On get(key), look up the node in the map, move it to the front, and return its value. On put(key, value), update or create the node at the front; if the cache is now over capacity, remove the node at the back and delete its key from the map.

Worked example with capacity 2

Python implementation from scratch

Sentinel head and tail nodes remove the special cases for an empty list: every real node always has a node before and after it.

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 LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.head, self.tail = Node(), Node()   # sentinels
        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 _push_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

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

    def put(self, key, value):
        if key in self.map:
            self._unlink(self.map[key])
        node = self.map[key] = Node(key, value)
        self._push_front(node)
        if len(self.map) > self.capacity:
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]

cache = LRUCache(2)
cache.put(1, "a")
cache.put(2, "b")
print(cache.get(1))   # a
cache.put(3, "c")     # evicts key 2
print(cache.get(2))   # None
cache.put(1, "A")
cache.put(4, "d")     # evicts key 3
print(cache.get(3), cache.get(1), cache.get(4))  # None A d

The short version with OrderedDict

collections.OrderedDict is itself a hash map combined with a doubly linked list, and move_to_end and popitem(last=False) are O(1). That makes it the idiomatic choice in Python when you need an LRU cache as an object.

from collections import OrderedDict

class LRU:
    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)          # mark as most recent
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)   # drop least recent

c = LRU(2)
c.put("x", 1)
c.put("y", 2)
c.get("x")
c.put("z", 3)
print(list(c.data))  # ['x', 'z']

Caching function results with functools.lru_cache

To cache the return values of a function, use the functools.lru_cache decorator. Arguments must be hashable, because they become dictionary keys. cache_info() shows hits, misses and the current size.

from functools import lru_cache

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

print(fib(80))           # 23416728348467685
print(fib.cache_info())
# CacheInfo(hits=78, misses=81, maxsize=128, currsize=81)

maxsize=None gives an unbounded cache, which is what functools.cache (Python 3.9 and later) does. Call fib.cache_clear() to empty it.

Time and space complexity

Variants, mistakes and when to use LRU

• LFU (least frequently used) evicts the item with the fewest accesses; it protects popular items from one-off scans but is more complex.
• Approximate LRU: systems such as Redis sample a few keys and evict the oldest among them instead of keeping an exact list, which saves memory.
• TTL caches expire entries after a fixed time, often combined with a size limit.
• Forgetting to move an entry to the front on get, or on put of an existing key, turns LRU into FIFO.
• Forgetting to delete the evicted key from the hash map leaves dangling entries and leaks memory.
• Sharing an LRU cache between threads needs a lock around each operation; functools.lru_cache is safe to call from multiple threads.

LRU is a good default when recent use predicts future use. It does poorly when a large one-time scan pushes out frequently used data; workloads like that benefit from LFU or scan-resistant policies. Designing an LRU cache with O(1) operations is also one of the most common coding interview questions, because it tests hash maps and linked lists together.