LRU-кэш: как устроен и как написать его за O(1)

Что такое LRU и зачем его спрашивают

Кэш ограничен по размеру. Рано или поздно он заполняется, и приходится решать, что выбросить, чтобы освободить место. LRU (Least Recently Used) отвечает на этот вопрос просто: выбрасываем то, к чему дольше всего не обращались.

Логика опирается на принцип временной локальности — если к данным обращались недавно, скорее всего обратятся снова. Работает не всегда, но в среднем достаточно хорошо, поэтому LRU используют повсеместно: в кэше страниц операционной системы, в Redis, в браузерах, в ORM.

На собеседовании эту задачу дают очень часто, и вот почему: она не требует хитрой математики, но проверяет сразу три вещи — знание структур данных, умение их комбинировать и внимание к деталям. Решение «в лоб» работает за O(n), а требуется O(1) на обе операции.

Требования

Нужен объект с двумя методами:

• get(key) — вернуть значение или −1, если ключа нет. Обращение считается использованием, элемент становится самым свежим.
• put(key, value) — записать значение. Если ключ уже есть, обновить и освежить. Если кэш переполнен, выбросить самый давний элемент.

Обе операции должны работать за O(1).

Почему очевидные решения не подходят

Массив. Держим элементы в порядке использования: свежие в конце, старые в начале. Поиск ключа — O(n), удаление из середины со сдвигом — O(n). Не проходит.

Только хеш-таблица. Поиск O(1), но она не хранит порядок. Чтобы найти самый давний элемент, придётся перебрать всё — снова O(n).

Хеш-таблица + метка времени. Храним рядом со значением время последнего доступа. get и put становятся O(1), но вытеснение требует найти минимум по всем меткам — O(n).

Вывод: нужна структура, которая одновременно даёт быстрый поиск по ключу и быстрое перемещение элемента в конец очереди.

Правильная комбинация

Ответ — двусвязный список плюс хеш-таблица.

Двусвязный список хранит порядок использования: голова — самый свежий элемент, хвост — кандидат на вылет. Удаление узла из середины стоит O(1), если у нас есть ссылка на сам узел, — именно поэтому список двусвязный. В односвязном пришлось бы искать предыдущий узел, а это O(n).

Хеш-таблица отображает ключ прямо в узел списка. Это даёт ту самую ссылку на узел за O(1).

Хеш-таблица              Двусвязный список
  "a" ──────────┐    head ⇄ [b] ⇄ [a] ⇄ [c] ⇄ tail
  "b" ────────┐ │           свежий        давний
  "c" ──────┐ │ │
            └─┴─┴──── указывают на узлы

Когда обращаемся к элементу, мы находим узел через таблицу, вырываем его из списка и вставляем в голову. Обе операции — O(1).

Реализация на JavaScript

Ключевой приём — фиктивные узлы head и tail. Без них пришлось бы отдельно обрабатывать вставку в пустой список и удаление последнего элемента, а это самый частый источник ошибок.

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // ключ → узел

    // фиктивные границы: реальные узлы всегда между ними
    this.head = new Node(null, null);
    this.tail = new Node(null, null);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  _addToFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }

  get(key) {
    const node = this.map.get(key);
    if (!node) return -1;

    // обращение освежает элемент
    this._remove(node);
    this._addToFront(node);

    return node.value;
  }

  put(key, value) {
    const existing = this.map.get(key);

    if (existing) {
      existing.value = value;
      this._remove(existing);
      this._addToFront(existing);
      return;
    }

    if (this.map.size === this.capacity) {
      // вытесняем самый давний — он перед хвостом
      const lru = this.tail.prev;
      this._remove(lru);
      this.map.delete(lru.key);
    }

    const node = new Node(key, value);
    this.map.set(key, node);
    this._addToFront(node);
  }
}

Проверим:

const cache = new LRUCache(2);

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);      // 1 → теперь свежий ключ 1, давний ключ 2
cache.put(3, 3);   // переполнение → вытесняем ключ 2
cache.get(2);      // -1
cache.put(4, 4);   // вытесняем ключ 1
cache.get(1);      // -1
cache.get(3);      // 3
cache.get(4);      // 4

Зачем в узле хранится ключ. Кажется избыточным — ключ ведь уже есть в хеш-таблице. Но при вытеснении мы находим узел через список и должны удалить соответствующую запись из таблицы. Без ключа внутри узла сделать это невозможно. Это самая частая ошибка в этой задаче, и интервьюеры про неё знают.

Короткое решение через Map

В JavaScript Map гарантирует порядок вставки ключей, и это позволяет написать LRU в несколько строк:

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
  }

  get(key) {
    if (!this.map.has(key)) return -1;

    const value = this.map.get(key);
    // переустановка перемещает ключ в конец
    this.map.delete(key);
    this.map.set(key, value);

    return value;
  }

  put(key, value) {
    if (this.map.has(key)) {
      this.map.delete(key);
    } else if (this.map.size === this.capacity) {
      // первый ключ итератора — самый давний
      const oldest = this.map.keys().next().value;
      this.map.delete(oldest);
    }

    this.map.set(key, value);
  }
}

Работает и тоже за O(1). Но на собеседовании этот вариант стоит показывать после развёрнутого — сначала покажите, что понимаете механику, потом упомяните, что в проде написали бы короче. Если начать с него, интервьюер почти наверняка попросит реализовать список руками.

Python: два варианта

В стандартной библиотеке есть OrderedDict с методом move_to_end, который делает ровно то, что нужно:

from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.cache: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        elif len(self.cache) == self.capacity:
            self.cache.popitem(last=False)  # убираем самый давний
        self.cache[key] = value

А если LRU нужен просто для мемоизации функции, писать вообще ничего не надо:

from functools import lru_cache


@lru_cache(maxsize=128)
def fib(n: int) -> int:
    return n if n < 2 else fib(n - 1) + fib(n - 2)

Другие стратегии вытеснения

Стоит понимать, чем LRU отличается от соседей — про это часто спрашивают следом.

FIFO выбрасывает то, что положили раньше всех, независимо от обращений. Проще в реализации, но заметно хуже по попаданиям: часто используемый элемент вылетит просто потому, что он старый.

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

Random выбрасывает случайный элемент. Звучит несерьёзно, но при большом кэше работает на удивление прилично и стоит почти ничего.

Слабое место LRU — последовательное сканирование. Если пройти по большому набору данных один раз, он вытеснит из кэша всё полезное, хотя эти данные больше не понадобятся. Из-за этого в реальных системах чаще встречаются гибриды: сегментированный LRU, ARC, W-TinyLFU.

О чём спрашивают дальше

Готовьтесь к продолжению разговора.

«Как сделать потокобезопасным?» Простой вариант — общий мьютекс на все операции, но он убивает параллелизм. Дальше идут шардирование кэша на несколько независимых сегментов со своими блокировками и неблокирующие реализации на CAS.

«Как добавить TTL?» Хранить в узле время истечения и проверять его при чтении. Просроченные записи удалять лениво (при обращении) либо фоновым процессом. Ленивый способ дешевле, но просроченные данные занимают память до следующего обращения.

«Как измерить эффективность?» Основная метрика — hit rate, доля попаданий. Смотреть надо не на абсолютное число, а на динамику и на то, как оно меняется с размером кэша.

Что запомнить

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

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→