LRU-кэш

Вытесняет то, к чему дольше всего не обращались.

время O(1) get/putпамять O(capacity)уровень: начальный

Что происходит сейчас0/0

Нажмите Play, чтобы запустить сценарий

TypeScript — активная строка подсвечена шагом

1class LRUCache {
2  private map = new Map<string, number>()
3 
4  constructor(private capacity: number) {}
5 
6  get(key: string): number | undefined {
7    if (!this.map.has(key)) return undefined
8    const value = this.map.get(key)!
9    this.map.delete(key)
10    this.map.set(key, value) // переустановка = «недавно использован»
11    return value
12  }
13 
14  put(key: string, value: number): void {
15    this.map.delete(key)
16    this.map.set(key, value)
17    if (this.map.size > this.capacity) {
18      const oldest = this.map.keys().next().value
19      this.map.delete(oldest)
20    }
21  }
22}

Проблема

Кэш с ограничением: что выбросить, когда место кончилось? Выбрасывать «старые по времени» нечестно — старый, но часто читаемый ключ ценнее свежего, но мёртвого.

Что вы видите

Ряд ключей: get поднимает ключ в «свежие», переполнение выталкивает хвост.

Как это работает

Map с переустановкой: свежие всегда в конце, старые — в начале. get-хит переустанавливает ключ (теперь «недавно использован»), переполнение выталкивает первый. O(1) на операцию. На паре Map + двусвязный список построены кэши страниц и DNS.

Пошаговый разбор

01
get HIT
Ключ переустанавливается — свежий.
02
Переполнение
Выталкивается самый старый.
03
O(1)
Map + двусвязный список.

Complexity и ограничения

time

O(1) get/put

space

O(capacity)

См. complexity в шапке страницы.

Edge cases

get несуществующего ключа
MISS без перестройки порядка.
put в полный кэш
Вытесняется ключ с самым давним обращением.
Повторный put существующего ключа
Обновление значения = «недавно использован», ключ всплывает.

Где встречается в реальности

Продукт

Классический приём в реальных системах.

Собеседования

Стандартный вопрос на понимание структуры.

Связанные алгоритмы

Хеш-таблица Двусвязный список

Shorts

«Почему кэш помнит последнее, а не частое»

Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.

Shorts 9:16

Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.

Почему кэш помнит последнее, а не частое

Нажмите Play

Бит 1/6 · 0–2 с

Hook

script-setup.ru/algorithms/lru-cache