Forge Learn/Algorithms Behind Caching

Browsing as a guest. Sign in to save your progress and earn XP as you complete chapters.

From Hashing to LRU Caches

6 min read

You'll learn to

-Explain why a hashmap alone cannot implement a recency-based eviction policy
-Describe how pairing a hashmap with a doubly-linked list gives O(1) get, put, and evict
-Trace through an LRU cache's internal state across a sequence of operations
-Know the OrderedDict shortcut, and why interviews still ask for the linked-list version

Back in the hashing tier you built a hashmap that gives O(1) average-case lookup by key. That answered where is this value? but said nothing about how recently was it used?

Real production caches, such as page caches, connection pools and the query cache in front of a database, have to answer both, because memory is finite. When the cache is full and a new item needs a slot, something must be evicted, and evicting the wrong thing, the item you are about to need again, wrecks your hit ratio. The LRU Cache level asks you to build the algorithm that almost every real cache uses for that decision: Least Recently Used, or LRU.

An Analogy: A Pile of Papers With Sticky Tabs

Picture a pile of papers on your desk, the one you used last on top. Whenever you use a paper, you pull it out and put it back on top. When the pile gets too tall, you throw away the paper at the bottom, the one you have gone longest without touching. The trouble is finding a paper in the middle of the pile: you would have to leaf through it. So every paper gets a sticky tab in an index beside the desk that says exactly where it sits in the pile.

-The pile is a doubly-linked list, ordered from most recently used at the head to least recently used at the tail.
-The index with the sticky tabs is the hashmap, from each key straight to its node in the list.
-Pulling a paper out and putting it on top is splicing a node out of the list and adding it at the head.
-Throwing away the bottom paper is evicting the tail node, and removing its key from the index too.

The Problem: Hashmaps Have No Sense of Time

A plain dict stores unordered key-value pairs. Nothing about it tells you which key was touched first versus a millisecond ago. You could scan every entry and check a "last used" timestamp on eviction, but that is O(n) per eviction, unacceptable when a cache is evicting thousands of times per second under load. You need a structure that keeps entries ordered by recency and lets you jump straight to any entry by key. That is two different data structures doing two different jobs, wired together.

The Fix: A Doubly-Linked List Ordered by Recency

A doubly-linked list can keep items ordered from most recently used (the head) to least recently used (the tail). Because each node has both a prev and a next pointer, you can splice any node out of the middle in O(1), as long as you already hold a reference to it.

That reference is exactly what the hashmap supplies: it maps each key to its node in the list. Wired together, the two structures give you every operation in O(1):

-get(key): look the node up in the hashmap, move it to the head, and return its value.
-put(key, value) for an existing key: update the node and move it to the head.
-put(key, value) for a new key: create a node at the head and add it to the hashmap.
-If the cache is now over capacity: evict the node at the tail, the true least recently used, and delete its key from the hashmap.

An LRU cache. Sentinel head/tail nodes mean every real node always has both neighbors, so no special-casing the ends.

class _Node:
    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}  # key -> _Node
        # Sentinel head/tail so every real node always has a prev and next
        self.head = _Node()
        self.tail = _Node()
        self.head.next = self.tail
        self.tail.prev = self.head

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

    def _add_to_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_to_front(node)
        return node.value

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

class _Node:
    __slots__ = ("key", "value", "prev", "next")

def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}  # key -> _Node
        # Sentinel head/tail so every real node always has a prev and next
        self.head = _Node()
        self.tail = _Node()
        self.head.next = self.tail
        self.tail.prev = self.head

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

def _add_to_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_to_front(node)
        return node.value

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

Tracing a Capacity-2 Cache

Here is the list after each operation, with the most recently used key first:

-put(1, A): the list is [1].
-put(2, B): the list is [2, 1].
-get(1) returns A, and 1 moves to the front: [1, 2].
-put(3, C): the list would be [3, 1, 2], which is over capacity, so the tail, key 2, is evicted: [3, 1].
-get(2) returns -1, because key 2 is gone. get(3) returns C and leaves [3, 1].
-put(4, D): the list would be [4, 3, 1], so the tail, key 1, is evicted: [4, 3].

Notice that get(1) is what saved key 1 on the fourth step: using an item counts as recent use. Without that get, key 1 would have been the oldest and would have gone instead of key 2.

The Shortcut, and Why Interviews Still Ask for the Long Way

Python's OrderedDict already remembers insertion order and can move a key to the end in O(1), so a working LRU cache is only a few lines. And for caching the results of a function call, functools.lru_cache does it with a decorator. In production code, use those.

An LRU cache in a few lines with OrderedDict. The cache is the same, but the linked list is hidden inside

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.items = OrderedDict()           # least recent first, most recent last

    def get(self, key):
        if key not in self.items:
            return -1
        self.items.move_to_end(key)          # mark as 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(1, "A")
cache.put(2, "B")
cache.get(1)
cache.put(3, "C")                            # evicts key 2
print(cache.get(2), list(cache.items))       # -1 [1, 3]

Interviewers still ask you to build it from a hashmap and a linked list, because that shows you understand why each operation is O(1). The OrderedDict version hides exactly the part they want to see.

Every operation here, hashmap lookup, linked-list splice, is O(1). That is the whole point: an LRU cache has to make an eviction decision on nearly every request without ever becoming the bottleneck itself.

Interview Signal is part of Pro

See a real weak answer next to a real strong one for this exact topic.

Quiz is part of Pro

Test what you just read with a short quiz, and bank the XP.

Ready to Build This?

The LRU Cache level asks you to build exactly this data structure from scratch, a hashmap plus a doubly-linked list working together to give O(1) get, put, and eviction. No OrderedDict, no functools.lru_cache: wire up the node class and the pointer surgery yourself so the mechanism is not a black box the next time you reach for one.

Composing Data Structures Into One System Consistent Hashing: Scaling a Cache Across Many Servers

Discussion0

Join the Discussion

No comments yet. Be the first to start the thread!