LRU Cache: HashMap + Doubly Linked List, Cache Thrashing, and Production Issues

The O(1) LRU implementation

LRU requires two operations in O(1): look up a key and move the accessed item to the front of the usage order. A doubly linked list maintains order (O(1) node removal and insertion); a hashmap provides O(1) key lookup with direct pointers to list nodes.

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

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}          # key → Node
        self.head = Node(0, 0)   # dummy head (most recent)
        self.tail = Node(0, 0)   # dummy tail (least recent)
        self.head.next = self.tail
        self.tail.prev = self.head

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

    def _add(self, node: Node):
        """Add right after head (most recently used position)."""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add(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._remove(node)
            self._add(node)
        else:
            if len(self.cache) >= self.capacity:
                lru = self.tail.prev   # least recently used is before dummy tail
                self._remove(lru)
                del self.cache[lru.key]
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._add(new_node)

The dummy head and tail nodes eliminate edge cases (empty list, single element). Eviction always removes tail.prev. Insertion always adds after head.

Python shortcut: OrderedDict

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)   # mark as most recently used
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)   # evict LRU (first item)

OrderedDict.move_to_end() is O(1). popitem(last=False) removes the oldest item. This is cleaner for most use cases — use the manual implementation when you need more control (e.g., custom eviction hooks).

Cache thrashing

Thrashing occurs when the working set (all data needed in a time window) exceeds the cache size. Every access misses:

Working set = {A, B, C, D, E}  (5 items)
Cache size  = 3

Access sequence: A B C D E A B C D E ...

Time 1: get A → miss, cache=[A]
Time 2: get B → miss, cache=[B,A]
Time 3: get C → miss, cache=[C,B,A]
Time 4: get D → miss, evict A, cache=[D,C,B]
Time 5: get E → miss, evict B, cache=[E,D,C]
Time 6: get A → miss, evict C, cache=[A,E,D]  (A was just evicted!)
...

Hit rate = 0%. Every item is evicted before it's reused. Solutions:

• Increase cache size to cover the working set
• Partition the cache (hot vs warm segments) using Segmented LRU (SLRU)
• Switch to LFU for workloads where frequency matters more than recency

import threading

class ThreadSafeLRUCache:
    def __init__(self, capacity: int):
        self._cache = LRUCache(capacity)
        self._lock = threading.Lock()

    def get(self, key: int) -> int:
        with self._lock:
            return self._cache.get(key)

    def put(self, key: int, value: int) -> None:
        with self._lock:
            self._cache.put(key, value)