re:re:actable
Урок 013 минуты чтения

Задача: LRU-кеш

На этой странице
Кратко

LRU (Least Recently Used) — кеш ограниченного размера, который при переполнении удаляет давно не использованный элемент. Операции get и put должны работать за O(1). В JavaScript самое короткое решение — Map: он хранит ключи в порядке вставки, поэтому «использование» = удалить ключ и вставить заново в конец, а самый старый ключ — первый в map.keys(). Классическое решение на любом языке — хеш-таблица + двусвязный список.

Вопрос

Реализуйте класс LRUCache(capacity) с методами get(key) (вернуть значение или undefined и отметить как использованное) и put(key, value) (добавить или обновить; при превышении capacity удалить самый давно использованный). Обе операции — O(1).

Решение на Map

class LRUCache {
  #map = new Map();
 
  constructor(capacity) {
    if (capacity <= 0) throw new RangeError("capacity должен быть больше 0");
    this.capacity = capacity;
  }
 
  get(key) {
    if (!this.#map.has(key)) return undefined;
    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);
    this.#map.set(key, value);
    if (this.#map.size > this.capacity) {
      const oldestKey = this.#map.keys().next().value;   // первый — самый старый
      this.#map.delete(oldestKey);
    }
  }
 
  get size() {
    return this.#map.size;
  }
}

Проверка

const cache = new LRUCache(2);
cache.put("a", 1);
cache.put("b", 2);
cache.get("a");          // 1 — теперь "a" свежее "b"
cache.put("c", 3);       // переполнение: удаляется "b"
cache.get("b");          // undefined
cache.get("a");          // 1
cache.get("c");          // 3

Решение на двусвязном списке

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}
 
class LRUCacheList {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();                  // key → Node
    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 undefined;
    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;
    }
    const node = new Node(key, value);
    this.map.set(key, node);
    this.#addToFront(node);
    if (this.map.size > this.capacity) {
      const lru = this.tail.prev;          // самый старый — перед хвостом
      this.#remove(lru);
      this.map.delete(lru.key);
    }
  }
}

Голова списка — самые свежие элементы, хвост — самые старые; Map дает доступ к узлу за O(1), список — перемещение и удаление за O(1).

Доп. вопросы интервьюера

  • Почему Map, а не объект? Map гарантирует порядок вставки для любых ключей и имеет size; у объекта числовые ключи сортируются.
  • Как добавить TTL? хранить { value, expiresAt } и проверять время в get.
  • Где используется? кеш запросов и изображений, мемоизация с ограничением, кеш страниц в браузере, кеш в Redis (allkeys-lru).
  • LRU vs LFU? LFU удаляет наименее часто используемый элемент — нужен счетчик обращений.

Что важно помнить

  • get тоже обновляет «свежесть» элемента.
  • Обновление существующего ключа не должно увеличивать размер.
  • В решении на Map удаление и повторная вставка — O(1).
  • Теория: hash table, linked list.

Мини-шпаргалка

Map в порядке вставки: get → delete + set (в конец), put → delete + set, переполнение → удалить keys().next().value. Классика: Map key → узел двусвязного списка, голова — свежие, хвост — старые, фиктивные head/tail. O(1).

Документация

MDN: Map, LeetCode 146: LRU Cache, Wikipedia: Cache replacement policies.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам