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

Для реализации in-memory LRU-кэша оптимально использовать LinkedHashMap в Java, так как он объединяет хеш-таблицу для доступа O(1) и двусвязный список для отслеживания порядка использования.

Реализация:

import java.util.LinkedHashMap;
import java.util.Map;

public class SimpleLRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public SimpleLRUCache(int capacity) {
        // Вызов конструктора с accessOrder = true для включения LRU-порядка
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // Удаляет самый старый элемент при превышении емкости
        return size() > capacity;
    }
}

// Использование
SimpleLRUCache<Integer, String> cache = new SimpleLRUCache<>(3);
cache.put(1, "A");
cache.put(2, "B");
cache.put(3, "C");
cache.get(1);      // Делает ключ 1 "недавно использованным"
cache.put(4, "D"); // Вытеснит ключ 2 (самый давно неиспользуемый)

Ключевые моменты:

• accessOrder = true в конструкторе — ключевой параметр, включающий LRU-логику.
• removeEldestEntry — переопределяется для автоматического вытеснения при заполнении.
• Производительность: Все основные операции (get, put, containsKey) выполняются за O(1).
• Потокобезопасность: Базовая реализация не потокобезопасна. Для многопоточного использования необходим внешний synchronized или использование Collections.synchronizedMap(). Для высоконагруженных сценариев лучше рассмотреть ConcurrentHashMap с более сложной реализацией порядка.