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

LRU-кэш вытесняет давно не использованный элемент; чтобы все операции были O(1), его строят из двусвязного списка, задающего порядок свежести, плюс хеш-таблицы «ключ → узел».

Почему нужна комбинация

• Хеш-таблица даёт поиск за O(1), но не знает порядка использования.
• Список знает порядок, но поиск в нём O(n). Вместе они закрывают оба требования.

Как работают операции

• get(key): нашли узел в таблице → перенесли его в голову списка (пометили свежим) → вернули значение.
• put(key, value): обновили или создали узел и поставили в голову; при переполнении удалили хвост (самый старый) и его запись из таблицы.

map:  {a → node1, b → node2}
list: head ↔ b ↔ a ↔ tail   // b использовался позже a

Нюансы реализации

• Фиктивные узлы head и tail убирают проверки на null при перестановке.
• В многопоточном коде нужны блокировки: пара «таблица + список» не атомарна.

Коротко для собеседования

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