LRU Cache

Least Recently Used Cache

Pronunciation: el-ar-YOO KASH

Updated October 3, 20262 min read

In short

An LRU (least recently used) cache holds a fixed number of items and, when full, evicts the one unused the longest, betting that recent data will be reused.

What is an LRU cache?

Caches are small by design, so they need an eviction policy for when they fill up. LRU assumes recency predicts the future: something read a second ago is more likely to be read again than something untouched for an hour. Every time an item is read or written, it becomes the most recently used; when space is needed, the least recently used item is removed.

The classic implementation combines two structures to make both lookups and updates O(1). A hash map finds an item by key instantly, and a doubly linked list keeps items in order of use: moving an item to the front and removing the item at the back are both constant-time pointer changes. This exact design is a well-known interview question.

LRU is everywhere. Python offers it as the functools.lru_cache decorator, Java's LinkedHashMap can be configured as one, Redis can evict keys with an approximate LRU policy, and operating systems and CPUs use LRU-like rules to decide which memory pages and cache lines to keep.

A common misconception is that LRU is always the best policy. A one-off scan of a large dataset can push out all the genuinely popular items, and workloads where some items are steadily popular may do better with LFU (least frequently used) or newer policies that combine recency and frequency. Measuring the hit rate on real traffic is the way to choose.

Key takeaways

An LRU cache evicts the item unused for the longest time when it is full.
It assumes recently used data will be needed again soon.
A hash map plus a doubly linked list gives O(1) get and put.
Python's lru_cache, Java's LinkedHashMap and Redis offer LRU eviction.
Large scans can flush it; LFU and hybrid policies suit some workloads better.

Example

An LRU cache with O(1) operations (Python)python

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.items = OrderedDict()        # a hash map that remembers order

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

    def put(self, key, value):
        self.items[key] = value
        self.items.move_to_end(key)
        if len(self.items) > self.capacity:
            self.items.popitem(last=False)   # evict the least recently used

cache = LRUCache(2)
cache.put("a", 1); cache.put("b", 2); cache.get("a"); cache.put("c", 3)
print(list(cache.items))   # ['a', 'c']: "b" was evicted

Readers ask

How is an LRU cache implemented?

Usually with a hash map from keys to nodes of a doubly linked list. The list keeps items in order of use, so moving an item to the front and removing the oldest are both O(1).

What is the difference between LRU and LFU?

LRU evicts the item that was used least recently. LFU evicts the item used least often overall. LRU adapts quickly to changing patterns; LFU better protects items that are consistently popular.

What does Python's lru_cache do?

functools.lru_cache is a decorator that memoizes a function's results by its arguments, keeping up to a set number of results and evicting the least recently used when full.