LinkedHashMap в Java и LRU-кэш - Java программирование Вопросы - 5 вопросов

1.

Как устроена LinkedHashMap и чем она отличается от HashMap?

LinkedHashMap расширяет HashMap: поиск по ключу идёт через ту же хеш-таблицу, но каждая запись дополнительно хранит ссылки before и after на соседей в двусвязном списке, а карта помнит его начало (head) и конец (tail). Обход идёт по списку, поэтому порядок предсказуем: по умолчанию — порядок вставки, с флагом accessOrder = true — порядок последнего обращения.

Повторный put() существующего ключа меняет только значение, позиция остаётся прежней; после remove() и новой вставки ключ уходит в конец. get() и put() остаются O(1) в среднем, а обход зависит только от size(), а не от ёмкости таблицы, как у HashMap. Цена — две лишние ссылки на запись и чуть более медленные put()/remove(). Сортировки LinkedHashMap не даёт — для неё нужен TreeMap.

2.

Что делает флаг accessOrder в LinkedHashMap и какие операции считаются доступом?

Флаг включается только конструктором new LinkedHashMap<>(initialCapacity, loadFactor, true). В этом режиме каждое обращение к существующему ключу переносит его запись в конец списка, а в начале остаётся пара, к которой дольше всех не обращались.

Доступом считаются get() и getOrDefault() (если ключ найден), put() и putIfAbsent(), compute*() и merge(), replace() (если значение заменено) и putAll(). Не считаются — containsKey(), containsValue() и обход keySet(), values(), entrySet(), включая entry.setValue().

В этом режиме get() — структурное изменение: он увеличивает modCount, поэтому get() внутри обхода keySet() бросает ConcurrentModificationException (обходите entrySet()), а в многопоточном коде синхронизировать нужно даже чтение.

3.

Как реализовать LRU-кэш на LinkedHashMap?

Нужно создать карту с accessOrder = true и переопределить защищённый метод removeEldestEntry(), чтобы он возвращал true, когда размер превысил лимит. После вставки нового ключа карта сама удалит самую давно использованную пару — первую запись списка:

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

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

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

Без флага accessOrder (конструктор super()) получится FIFO-кэш: вытесняется самая давно добавленная пара, а get() на порядок не влияет.

4.

Когда LinkedHashMap вызывает removeEldestEntry() и какие ограничения у LRU-кэша на её основе?

Метод removeEldestEntry(eldest) вызывают put(), putAll(), putIfAbsent(), computeIfAbsent(), compute() и merge() — но только когда в карту добавлен новый ключ. Параметр eldest — первая запись списка. По умолчанию метод возвращает false и ничего не удаляет. Обновление существующего ключа новую пару не добавляет, поэтому вытеснения не происходит.

Ограничения такого кэша: он не потокобезопасен (оборачивают в Collections.synchronizedMap(), причём синхронизировать нужно и чтение — get() меняет порядок); лимит задаётся в штуках, а не в байтах; нет срока жизни записей (TTL); наследование открывает весь API LinkedHashMap. Для нагруженных кэшей с TTL и конкурентным доступом используют библиотеку Caffeine.

5.

Какие методы SequencedMap появились у LinkedHashMap в Java 21?

С Java 21 (JEP 431) LinkedHashMap реализует интерфейс SequencedMap и получила методы для работы с концами карты: firstEntry() и lastEntry() возвращают первую и последнюю пару без удаления, pollFirstEntry() и pollLastEntry() — с удалением (на пустой карте все четыре возвращают null), putFirst() и putLast() вставляют пару в начало или конец (существующий ключ переезжает), reversed() возвращает живое представление в обратном порядке, а sequencedKeySet(), sequencedValues() и sequencedEntrySet() — упорядоченные представления.

До Java 21 последнюю пару можно было получить только полным обходом. Методы объявлены в SequencedMap, поэтому переменная должна иметь тип SequencedMap или LinkedHashMap: с типом Map вызов firstEntry() не скомпилируется.

LinkedHashMap в Java и LRU-кэш - Вопросы