LinkedHashMap и LRU-кэш

Порядок вставки против порядка доступа, связанный список поверх HashMap и реализация LRU через removeEldestEntry.

Что добавляет к HashMap

LinkedHashMap наследует всю механику HashMap (бакеты, treeify, resize), но дополнительно связывает все записи в двусвязный список в порядке их появления. Поэтому итерация идёт в предсказуемом порядке, в отличие от HashMap, где порядок не определён.

Цена — немного больше памяти (две ссылки на запись) и чуть дороже вставка/удаление из-за поддержки списка.

Порядок вставки и порядок доступа

По умолчанию порядок — вставки (insertion-order). Но в конструкторе можно включить accessOrder=true: тогда get/put перемещают запись в конец списка, и итерация идёт от наименее недавно использованных к самым свежим.

Именно accessOrder делает LinkedHashMap естественной основой для LRU-кэша.

LRU за несколько строк

Достаточно включить accessOrder и переопределить removeEldestEntry, чтобы карта сама выбрасывала самый старый по обращению элемент при превышении ёмкости.

Это рабочий однопоточный LRU; для конкурентного нужны другие средства (например, Caffeine), но идея та же.

Map<K, V> lru = new LinkedHashMap<>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > CAPACITY; // удаляем самый давно используемый
    }
};

Как устроен порядок

Список не лежит рядом с картой — им становятся сами записи. LinkedHashMap.Entry расширяет узел HashMap двумя полями, before и after, а карта дополнительно держит ссылки на голову и хвост. Никакой второй структуры данных нет, поэтому накладные расходы — ровно две ссылки на запись.

Встраивается это через хуки, которые HashMap оставил пустыми специально для наследника: afterNodeInsertion, afterNodeAccess и afterNodeRemoval. HashMap вызывает их в нужных местах, а LinkedHashMap в них перестраивает список — приём, который стоит помнить как пример расширения без переписывания.

У этого есть неочевидный бонус: итерация идёт по списку, а не по таблице бакетов. Обход LinkedHashMap стоит O(размер), тогда как у HashMap — O(ёмкость + размер). Если карту создали с большой начальной ёмкостью, а положили в неё десяток записей, HashMap будет честно перебирать пустые бакеты, а LinkedHashMap пройдёт ровно по своим записям.

// упрощённо изнутри LinkedHashMap:
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;   // связи порядка живут прямо в записи
}
transient Entry<K,V> head, tail;

// HashMap оставил эти методы пустыми — наследник их и переопределяет
void afterNodeAccess(Node<K,V> p) { /* в access-order переносит p в хвост */ }
void afterNodeInsertion(boolean evict) { /* спрашивает removeEldestEntry */ }

accessOrder меняет правила

Флаг accessOrder выглядит безобидной галочкой, но он превращает чтение в изменение. В этом режиме get переставляет запись в хвост списка, то есть выполняет структурную модификацию и увеличивает modCount.

Первое следствие: обычный for-each по такой карте, внутри которого вызывается get по этой же карте, упадёт с ConcurrentModificationException — в одном потоке, без всякой конкурентности.

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

Map<String, User> cache = new LinkedHashMap<>(16, 0.75f, true);
// ...
for (String key : cache.keySet()) {
    User u = cache.get(key);   // get в access-order = структурная модификация
    // ConcurrentModificationException на следующей итерации
}

Границы самодельного LRU

LRU на LinkedHashMap — отличный ответ на собеседовании и посредственный кэш в проде, и полезно понимать, где именно он заканчивается.

removeEldestEntry опрашивается только после вставки. Значит карта, в которую перестали писать, не уменьшится, сколько бы её ни читали, — вытеснение по времени тут отсутствует как класс. Нет ни TTL, ни обновления по истечении срока, ни метрик попаданий, а без hit rate невозможно понять, помогает ли кэш вообще.

Есть и алгоритмическая слабость: чистый LRU уязвим к сканированию. Один проход по большому набору холодных ключей вымывает из кэша всё горячее, потому что каждый новый ключ считается «самым свежим». Поэтому в проде берут готовую библиотеку вроде Caffeine с политикой W-TinyLFU, которая учитывает частоту обращений, умеет TTL и отдаёт метрики, — а LinkedHashMap оставляют для случаев, когда кэш локальный, маленький и живёт внутри одного вызова.

Как отвечать на собеседовании

Сильный ответ: LinkedHashMap = HashMap + двусвязный список записей; insertion-order по умолчанию, access-order по флагу; LRU реализуется accessOrder + removeEldestEntry. Уточните, что это однопоточное решение.