Что такое LRU-кэш?

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

Принцип работы:

• Каждый раз при доступе к элементу (чтение или запись), этот элемент помечается как "недавно использованный" и перемещается в начало списка или структуры, представляющей порядок использования.
• При переполнении кэша удаляется элемент из "хвоста" — тот, к которому обращались дольше всего.

Реализация часто использует комбинацию словаря (для быстрого доступа по ключу) и двусвязного списк