Расскажите про LRU (Least Recently Used) кэш?

LRU (Least Recently Used) кэш — это структура данных с фиксированной ёмкостью: когда она заполнена, вытесняется элемент, к которому обращались давнее всех. Гугл, Редис, процессорные кэши — везде LRU.

Классическая реализация — HashMap + Doubly Linked List. Зачем? HashMap даёт доступ к элементу за O(1), список — перемещение узла в начало за O(1) и удаление с конца за O(1).

Вот как это выглядит на Python (упрощённо, без OrderedDict специально, чтобы показать суть):

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

class LRUCache:
    def __init__(self, capacity):
        self.cap = 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(self, node):
        # вставить после head
        nxt = self.head.next
        self.head.next = node
        node.prev = self.head
        node.next = nxt
        nxt.prev = node

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

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

    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._remove(node)
            self._add(node)
        else:
            if len(self.cache) >= self.cap:
                # удаляем хвостовой элемент (настоящий, не dummy)
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._add(new_node)

Почему это работает?

• get: нашли по ключу, выдёргиваем узел из текущей позиции и вставляем сразу за head (самый недавний).
• put: если ключ уже есть — обновляем значение и двигаем в начало; если нет — создаём узел и вставляем, но перед этим проверяем, не превышен ли лимит. Если превышен — удаляем узел перед tail (это и есть LRU).
• Все операции — O(1).

На реальных проектах часто хватает collections.OrderedDict в Python или std::list с итераторами в C++. Но понимание голой реализации — фильтр для middle: проверяет, умеет ли человек комбинировать базовые структуры.

Нюансы:

• Работа в многопоточном окружении — нужен мьютекс или шардирование.
• LRU не всегда оптимален: если есть проход по всем элементам раз в N секунд, кэш засоряется; тогда смотрят на LFU или гибриды.