LRU cache design with hash map and doubly linked list in Data Structures Theory - Full Explanation

Introduction

Imagine you have limited space to store your favorite books, but you want to keep the most recently read ones handy. The problem is deciding which book to remove when the space is full. This is the challenge that an LRU cache solves by remembering the order of use and quickly accessing stored items.

Explanation

Purpose of LRU Cache

An LRU (Least Recently Used) cache keeps track of the most recently accessed items and removes the least recently used ones when it reaches its capacity. This helps in managing limited storage efficiently by prioritizing recent data.

LRU cache removes the oldest unused items to make space for new ones.

Role of Hash Map

The hash map stores keys and points directly to nodes in the doubly linked list. This allows quick lookup of cache items in constant time, avoiding slow searches through the list.

Hash map enables fast access to cache items by key.

Role of Doubly Linked List

The doubly linked list keeps the order of items from most recently used at the front to least recently used at the back. When an item is accessed or added, it moves to the front. When the cache is full, the item at the back is removed.

Doubly linked list maintains usage order for quick updates.

How Both Structures Work Together

When accessing or adding an item, the hash map finds the node quickly, and the doubly linked list moves it to the front. If the cache is full, the list removes the last node, and the hash map deletes its key. This combination keeps operations fast and efficient.

Hash map and doubly linked list together provide fast access and update of cache items.

Real World Analogy

Imagine a desk with a small stack of papers you use often. When you read a paper, you put it on top of the stack. If the desk is full, you remove the paper at the bottom, which you haven't used recently. You also have a quick index that tells you where each paper is in the stack.

LRU Cache → The desk with limited space for papers

Hash Map → The quick index that tells where each paper is

Doubly Linked List → The stack of papers ordered by recent use

Removing least recently used → Taking the paper at the bottom of the stack off the desk

Diagram

Diagram

┌───────────────┐
│   Hash Map    │
│  Key → Node   │
└──────┬────────┘
       │
       ▼
┌─────────────────────────────┐
│ Doubly Linked List (Cache)  │
│ ┌─────┐ ┌─────┐ ┌─────┐     │
│ │ MRU │→│ ... │→│ LRU │     │
│ └─────┘ ←└─────┘ ←└─────┘     │
└─────────────────────────────┘

Diagram showing hash map pointing to nodes in a doubly linked list ordered from most recently used (MRU) to least recently used (LRU).

Key Facts

LRU Cache → A cache that removes the least recently used item when full.

Hash Map → A data structure that provides fast key-based access to values.

Doubly Linked List → A list where each node points to both its previous and next nodes.

Most Recently Used (MRU) → The item accessed or added most recently in the cache.

Least Recently Used (LRU) → The item that has not been accessed for the longest time in the cache.

Code Example

Data Structures Theory

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

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> node
        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 _remove(self, node):
        prev = node.prev
        nxt = node.next
        prev.next = nxt
        nxt.prev = prev

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

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

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

Common Confusions

Believing a simple list alone can provide fast access and update for LRU cache.

Believing a simple list alone can provide fast access and update for LRU cache. A simple list requires searching through all items, which is slow; combining a hash map with a doubly linked list allows both fast lookup and quick updates.

Thinking the hash map stores the order of usage.

Thinking the hash map stores the order of usage. The hash map only stores keys and pointers; the doubly linked list maintains the order of usage.

Summary

An LRU cache efficiently manages limited storage by removing the least recently used items first.

A hash map provides fast access to cache items by key, while a doubly linked list maintains the order of usage.

Together, these structures allow quick updates and lookups, keeping the cache fast and organized.