Почему для реализации LRU-кэша хорошо подходит структура данных Map?

Почему Map подходит для LRU-кэша

LRU-кэш (Least Recently Used) требует отслеживать порядок использования элементов: самый старый по времени последнего доступа должен удаляться при переполнении. В JavaScript объект Map гарантирует порядок вставки ключей при итерации. Это ключевое свойство позволяет реализовать LRU-логику простыми операциями: при доступе к элементу удаляем его и вставляем заново, тем самым перемещая в конец. Самый старый элемент всегда находится в начале Map.

Как это работает на практике

Рассмотрим пример реализации LRU-кэша с ограниченной ёмкостью. Используем Map, где ключ — идентификатор, значение — данные. При получении элемента проверяем его наличие, удаляем и снова добавляем, чтобы обновить позицию. При добавлении нового элемента, если размер превышает лимит, удаляем первый ключ через map.keys().next().value.

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);
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
      const oldestKey = this.map.keys().next().value;
      this.map.delete(oldestKey);
    }
  }
}

Преимущества и ограничения

Map обеспечивает среднюю сложность операций O(1) для вставки, удаления и поиска, что идеально для кэша. В отличие от обычного объекта, Map не имеет прототипа и позволяет использовать любые типы ключей. Однако для очень больших кэшей может потребоваться более сложная структура, например, двусвязный список с хеш-таблицей, но для большинства задач Map достаточно.

Итог: Map — отличный выбор для реализации LRU-кэша в JavaScript благодаря гарантированному порядку вставки и эффективным операциям. Используйте его, когда нужен простой и надёжный кэш с ограниченной ёмкостью без внешних зависимостей.