Зачем при get в LRU-кэше удалять ключ и затем добавлять его снова?

Зачем обновлять позицию при get в LRU-кэше?

LRU (Least Recently Used) кэш хранит ограниченное количество элементов и при переполнении удаляет тот, к которому обращались давнее всего. Чтобы эффективно определять такой элемент, необходимо поддерживать порядок использования. Когда мы вызываем get для ключа, это означает, что элемент был использован сейчас, поэтому его нужно пометить как самый свежий. Если просто вернуть значение, не меняя позицию, то порядок останется прежним, и кэш не сможет корректно определить, какой элемент удалить при нехватке места.

Как это реализовано?

Обычно LRU-кэш строится на основе двусвязного списка и хеш-таблицы. Список хранит элементы в порядке использования: голова — самый свежий, хвост — самый старый. Хеш-таблица позволяет быстро найти узел списка по ключу. При операции get мы находим узел, удаляем его из текущей позиции и вставляем в голову. Это операция O(1), так как у нас есть ссылки на соседние узлы.

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = { prev: null, next: null };
    this.tail = { prev: null, next: null };
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    // удаляем из текущей позиции
    node.prev.next = node.next;
    node.next.prev = node.prev;
    // добавляем в голову
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
    return node.value;
  }
}

В этом примере при каждом get мы перемещаем узел в начало списка. Если этого не делать, то после нескольких обращений порядок не будет отражать реальную частоту использования, и кэш может удалить не тот элемент.

Практическое применение

LRU-кэш широко используется в базах данных, операционных системах, браузерах для кэширования страниц, а также в системах кэширования типа Redis. Понимание этого механизма важно для оптимизации производительности приложений, где доступ к данным может быть дорогим.

Итог: Обновление позиции при get — ключевая часть алгоритма LRU, обеспечивающая корректное вытеснение старых элементов. Без этого кэш не сможет эффективно использовать ограниченную память, поэтому данная операция обязательна.