LRU-кеш

Коротко: LRU-кеш («least recently used», давно не использовавшийся) хранит лишь ограниченное число записей и при нехватке места вытесняет запись, не использовавшуюся дольше всего.

Подробнее: Идея: то, что использовалось недавно, вероятно, скоро понадобится снова. Для быстрых операций хеш-таблицу (доступ за O(1)) сочетают с двусвязным списком (порядок использования).