Краткий ответ

Используйте LinkedHashMap в режиме порядка доступа и переопределите removeEldestEntry. При обращении к существующей записи она перемещается в конец внутреннего двусвязного списка, а после добавления новой записи карта может удалить элемент из его начала.

Исторический контекст

Обычная HashMap оптимизирована для поиска по ключу, но не хранит пригодный для кэширования порядок давности использования. LinkedHashMap добавляет к хеш-таблице связный список записей, чтобы поддерживать предсказуемый порядок обхода.

Такое сочетание позволяет реализовать простые кэши без отдельной структуры для отслеживания обращений. Идея решает задачу автоматического вытеснения старых записей при ограниченном размере памяти.

Постановка проблемы

Если кэш удаляет произвольную или только самую старую добавленную запись, он может вытеснить элемент, который недавно использовался. Это снижает hit rate и приводит к лишним обращениям к медленному источнику данных.

Нужно различать порядок вставки и порядок доступа. Кроме того, обычный LinkedHashMap не является потокобезопасным, поэтому конкурентные операции могут нарушить корректность кэша.

Подробное решение

У LinkedHashMap есть режим access-order. В нём успешный доступ к существующей записи, например через get, перемещает её в конец списка. Начало списка содержит наименее недавно использованный элемент.

Метод removeEldestEntry вызывается после добавления новой записи. Если он возвращает true, самая старая запись удаляется. Поэтому ограничение размера обычно задают проверкой size().

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

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int limit;

    LruCache(int limit) {
        super(16, 0.75f, true);
        this.limit = limit;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > limit;
    }
}

Третий аргумент конструктора true включает порядок доступа. Средняя сложность get и put остаётся близкой к O(1), а перемещение записи в связном списке выполняется за постоянное время.

Ограничение проверяется после вставки, поэтому на короткий момент размер может превысить лимит внутри операции. Механизм не предоставляет статистику попаданий, время жизни записей или защиту от одновременного доступа.

Синхронизация внешней обёрткой возможна, но увеличивает конкуренцию за общий монитор. Для высоконагруженного приложения обычно рассматривают специализированные кэши, например Caffeine, которые предоставляют более развитую политику вытеснения и конкурентную работу.

Ситуация из практики

Сервис получает профили пользователей из удалённого хранилища. Память ограничена, а недавно запрошенные профили с высокой вероятностью понадобятся снова.

Первый вариант — HashMap с ручным списком обращений. Он даёт контроль, но требует синхронно обновлять две структуры и удалять записи из обеих; ошибка в согласовании приводит к утечкам или неправильному вытеснению.

Второй вариант — LinkedHashMap в access-order. Он прост, даёт ожидаемую LRU-семантику и подходит для небольшого однопоточного или внешне синхронизированного кэша, но все операции могут конкурировать за одну блокировку.

Третий вариант — специализированный конкурентный кэш. Он сложнее как зависимость и настройка, зато лучше подходит для большого числа потоков, поддерживает дополнительные политики и обычно эффективнее масштабируется.

Для небольшого кэша внутри одного рабочего потока выбран LinkedHashMap: требовались минимальная зависимость и прозрачное поведение. Для общего кэша веб-приложения выбран был бы специализированный потокобезопасный кэш, поскольку одной стандартной карты недостаточно для требуемой пропускной способности.

Что кандидаты часто упускают

Обновляет ли containsKey позицию записи в access-order?

Нет. containsKey проверяет наличие ключа, но не считается обращением, перемещающим запись в конец списка. Поэтому проверка существования без чтения значения не продлевает элементу жизнь в LRU-кэше.

Напротив, операции, фактически обращающиеся к отображению, например get, обычно меняют порядок доступа. При проектировании кэша важно понимать, какие вызовы действительно считаются использованием записи.

Что произойдёт при повторном put уже существующего ключа?

Новая запись не создаётся: значение существующего отображения заменяется, а в access-order соответствующая запись перемещается в конец списка. Размер карты при этом не увеличивается.

Проверка removeEldestEntry предназначена для контроля добавления новой записи. Поэтому замена существующего значения сама по себе не должна рассматриваться как появление нового элемента, хотя конкретную логику вытеснения всё равно следует проверять на тестах для используемой версии JDK.

Может ли get вызвать проблемы при итерации access-order LinkedHashMap?

Да. В режиме порядка доступа перемещение записи может считаться структурным изменением связного списка. Если один поток итерирует карту, а другой вызывает get, итератор может завершиться ConcurrentModificationException, даже если количество отображений не изменилось.

Следовательно, access-order карта требует координации не только операций вставки и удаления, но и чтения. Для конкурентного кэша нужны единая стратегия синхронизации либо специализированная реализация; простое объявление ссылки volatile эту проблему не решает.