Understanding LRU Cache Design with HashMap and Doubly Linked List
This article explains the fundamental data structures behind an LRU (Least Recently Used) cache: a HashMap for O(1) lookups and a Doubly Linked List for maintaining access order. It highlights how these two structures work in conjunction to achieve efficient cache operations, which is critical for performance in many system designs.
Read original on Medium #system-designThe Core Components of an LRU Cache
An LRU cache is a widely used caching strategy that evicts the least recently used items when the cache reaches its capacity. The efficiency of an LRU cache, particularly its O(1) time complexity for `get` and `put` operations, stems from its intelligent combination of two fundamental data structures: a HashMap and a Doubly Linked List.
HashMap for O(1) Lookups
The HashMap (or hash table) is crucial for providing fast access to cached items. When a request comes for an item, the HashMap allows for direct lookup of the item's value or, more specifically in an LRU cache implementation, a reference to its corresponding node in the Doubly Linked List. This ensures that checking for an item's existence and retrieving its value is achieved in average O(1) time complexity.
Doubly Linked List for Order and Eviction
The Doubly Linked List is used to maintain the order of items based on their recency of use. The head of the list typically represents the most recently used (MRU) item, while the tail represents the least recently used (LRU) item. When an item is accessed or added, its corresponding node is moved to the head of the list. When the cache is full and a new item needs to be added, the item at the tail (LRU) is evicted.
Why a Doubly Linked List?
A doubly linked list is preferred over a singly linked list because it allows for O(1) removal of an arbitrary node. If we only had a singly linked list, removing an item from the middle would require traversing from the beginning, resulting in O(N) complexity. With a doubly linked list, given a reference to the node (which the HashMap provides), we can update its previous and next pointers directly.
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
self.head = Node(0, 0) # Dummy head
self.tail = Node(0, 0) # Dummy tail
self.head.next = self.tail
self.tail.prev = self.head
def _add_node(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _remove_node(self, node):
prev = node.prev
next = node.next
prev.next = next
next.prev = prev
def _move_to_head(self, node):
self._remove_node(node)
self._add_node(node)
def get(self, key: int) -> int:
if key in self.cache:
node = self.cache[key]
self._move_to_head(node)
return node.value
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
node = self.cache[key]
node.value = value
self._move_to_head(node)
else:
node = Node(key, value)
self.cache[key] = node
self._add_node(node)
if len(self.cache) > self.capacity:
# Remove LRU item from tail
lru = self.tail.prev
self._remove_node(lru)
del self.cache[lru.key]