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

Для простого кэширования с ограничением размера и политикой вытеснения LRU (Least Recently Used) лучше всего подходит LinkedHashMap. Он сочетает хеш-таблицу для быстрого доступа и двусвязный список для поддержания порядка элементов.

Пример реализации:

public class SimpleCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;
    
    public SimpleCache(int maxSize) {
        super(maxSize, 0.75f, true);
        this.maxSize = maxSize;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

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

• accessOrder=true в конструкторе включает LRU-порядок
• Переопределение removeEldestEntry автоматически удаляет старые записи при превышении размера
• O(1) для операций get/put
• Потоконебезопасно - для многопоточности нужна синхронизация