Реализуйте LRU-кэш на заданное число элементов на основе LinkedHashMap
Проверила команда Сопровод · Обновлено
Короткий ответ
LinkedHashMap умеет хранить порядок доступа: передайте третьим аргументом конструктора true, это флаг accessOrder, и каждый get или put перенесет запись в конец. Переопределите removeEldestEntry, чтобы он возвращал size() > capacity: после вставки карта сама удалит самую давнюю запись. Чтение и запись идут за O(1). Класс не потокобезопасен, для общего кэша нужна синхронизация.
Почему этот вопрос задают
LRU-кэш проверяет, знаете ли вы стандартную библиотеку глубже HashMap и можете ли объяснить сложность операций. От senior после кода ждут разговора о потоках, готовых кэшах вроде Caffeine и вытеснении с учетом частоты.
Условие задачи
Приложение электронной библиотеки показывает обложки книг и держит последние открытые в памяти. Реализуйте LRU-кэш на заданное число элементов на основе LinkedHashMap: при переполнении удаляется обложка, к которой дольше всего не обращались. Проверьте кэш емкостью 2 на операциях из таблицы и после шагов 2, 3 и 4 выводите ключи от самого давнего к самому свежему.
Как подойти к решению
- Создайте наследника
LinkedHashMap, например анонимный класс в фабричном методе - Передайте третьим аргументом конструктора
true: флагaccessOrderзаставитgetпереносить запись в конец - Переопределите
removeEldestEntryи возвращайтеtrue, когда размер превысил емкость - Прогоните шаги из условия и убедитесь, что вытеснена Аэлита
Решение
Внутри LinkedHashMap — хеш-таблица и двусвязный список записей. В режиме доступа get и put перецепляют запись в хвост за O(1), голова списка — самая давняя запись. removeEldestEntry вызывается после каждой вставки нового ключа, и true удаляет голову. Число 16 в конструкторе — начальный размер таблицы, лимит кэша задает capacity.
public class Main {
public static void main(String[] args) {
Map<String, String> covers = lru(2);
covers.put("Дюна", "dune.jpg");
covers.put("Аэлита", "aelita.jpg");
System.out.println("put Аэлита: " + covers.keySet());
covers.get("Дюна");
System.out.println("get Дюна: " + covers.keySet());
covers.put("Солярис", "solaris.jpg");
System.out.println("put Солярис: " + covers.keySet());
}
static <K, V> Map<K, V> lru(int capacity) {
return new LinkedHashMap<>(16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
};
}
}put Аэлита: [Дюна, Аэлита] get Дюна: [Аэлита, Дюна] put Солярис: [Дюна, Солярис]
Что спросят следом
Как сделать этот кэш потокобезопасным?
Как написать LRU без
LinkedHashMap?Какие методы считаются обращением к записи?
Доступно по подписке
Ответы на эти вопросы
Частые ошибки
«Создам
new LinkedHashMap<>()и буду удалять первый ключ при переполнении»Конструктор по умолчанию хранит порядок вставки, и получится очередь FIFO: часто открываемая обложка вылетит первой. Включите режим доступа третьим аргументом конструктора
«Проверю емкость перед
putи удалю старую запись сам»Ручная проверка дублирует
removeEldestEntry, и ее придется повторить вputAll,mergeиcompute. Переопределите этот метод: карта вызывает его после каждой вставки нового ключа«
super(capacity)задаст лимит кэша»Первый аргумент конструктора — начальная емкость хеш-таблицы, при росте она расширяется. Лимит живет только в
removeEldestEntry: сохраните его в поле класса или в захваченной переменной, как в решении«Повторный
putтого же ключа увеличит размер, и что-то вытеснится»Повторный
putзаменяет значение и переносит запись в конец, размер не меняется. Вытеснение случается только при новом ключе, когда записей становится больше емкости
Сигналы для интервьюера
Сильный ответ
Объясняет, почему обе операции идут за O(1), и сам спрашивает, будут ли кэшем пользоваться несколько потоков
Тревожный сигнал
Собирает кэш из HashMap и ArrayList и ищет давнюю запись перебором за O(n)
Красный флаг
Путает LRU с вытеснением по времени жизни и предлагает чистить кэш таймером раз в минуту
Как еще могут спросить
- Как реализовать LRU-кэш в Java?
- Для чего нужен параметр
accessOrderуLinkedHashMap? - Как сделать кэш фиксированного размера, который вытесняет давно неиспользуемые записи?
- Напишите кэш с политикой вытеснения LRU











