Released · improving
Algorithm
An LRU cache evicts the least recently used entry when full, using a hash map and a doubly linked list to make get and put O(1).
An LRU (least recently used) cache is a fixed-capacity cache that, when it is full, evicts the entry that has gone unused for the longest time. It relies on temporal locality, the observation that recently used data tends to be used again soon, and unlike FIFO it refreshes an entry's position on every read. The standard implementation pairs a hash map, which finds a key's node, with a doubly linked list, which keeps entries in recency order, so both get and put run in O(1) average time.
LRU, exactly or in approximate form, appears at almost every layer of a system: CPU caches, the operating system page cache, database buffer pools, Redis eviction policies, CDNs and browser caches. Standard libraries ship it too, as Python's functools.lru_cache and OrderedDict or Java's LinkedHashMap. Because it combines a hash map and a linked list in one design, it is also a classic coding interview question.
Start with the differences between eviction policies such as FIFO, LRU, LFU and TTL and with the idea of hit ratio, then trace a short request sequence by hand. Next, implement the cache yourself with a dictionary and a doubly linked list with sentinel nodes, and compare it with library versions such as OrderedDict and LinkedHashMap. Finally, work through practical problems: thread safety, cache invalidation and combining LRU with expiry.
Every successful get or put moves the entry to the most recent end; when space runs out, the entry at the other end is evicted.
The map finds a key's node directly, and the list unlinks and re-inserts nodes in O(1) to keep the order.
get and put change only a constant number of pointers, so both take constant average time; space grows with capacity.
Real systems often use CLOCK, pseudo-LRU, sampled LRU, 2Q or W-TinyLFU to cut overhead or resist large scans.
A dict maps keys to nodes, and a doubly linked list between the sentinels head and tail keeps the recency order. get moves the node to the front; put evicts the node just before tail when the cache is full. Running python lru_cache.py evicts "b" and prints None 1 3.
lru_cache.py
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 = {} # key -> Node
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, default=None):
node = self.map.get(key)
if node is None:
return default
self._unlink(node) # touch: move to the front
self._push_front(node)
return node.value
def put(self, key, value):
if self.capacity <= 0:
return
node = self.map.get(key)
if node is not None:
node.value = value
self._unlink(node)
self._push_front(node)
return
if len(self.map) >= self.capacity: # evict the least recently used
lru = self.tail.prev
self._unlink(lru)
del self.map[lru.key]
node = Node(key, value)
self.map[key] = node
self._push_front(node)
cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a") # "a" is now the most recent
cache.put("c", 3) # full: evicts "b"
print(cache.get("b"), cache.get("a"), cache.get("c")) # None 1 3
python lru_cache.pySix chapters that take you from installation to the core ideas of LRU cache.
Ask questions, share experience and trade opinions about LRU cache.
No discussions yet. Start the first one.
0 comments
Sign in · Sign in to leave a comment.
Be the first to comment.