LinkedHashMap в Java и LRU-кэш

Что выведет этот код? Map<String, Integer> m = new LinkedHashMap<>(16, 0.75f, true);, три вызова put() и обычный цикл for (String k : m.keySet()) System.out.println(k + "=" + m.get(k));. Программа напечатает первую пару и упадёт с ConcurrentModificationException: в режиме порядка доступа даже get() перестраивает карту. Почему так происходит и как на этом поведении строится LRU-кэш, разберём в уроке.

LinkedHashMap (linked hash map) — это реализация интерфейса Map из пакета java.util, которая расширяет HashMap и дополнительно связывает все записи двусвязным списком. Благодаря списку LinkedHashMap обходит пары в предсказуемом порядке: по умолчанию — в порядке вставки, а с флагом accessOrder = true — в порядке последнего обращения. Операции get() и put() при этом остаются O(1) в среднем, как у HashMap.

Как устроена LinkedHashMap внутри

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

Внутренний класс записи выглядит так (упрощённо, по исходникам JDK):

static class Entry<K, V> extends HashMap.Node<K, V> {
    Entry<K, V> before, after;   // соседи в двусвязном списке
    // hash, key, value, next унаследованы от HashMap.Node
}

transient LinkedHashMap.Entry<K, V> head;  // самая «старая» запись
transient LinkedHashMap.Entry<K, V> tail;  // самая «новая» запись
final boolean accessOrder;                  // false — порядок вставки, true — порядок доступа

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

Пример: порядок вставки сохраняется, повторный put() существующего ключа меняет только значение, а после remove() ключ при новой вставке уходит в конец.

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

public class LinkedHashMapExample {
    public static void main(String[] args) {
        Map<String, Double> salaries = new LinkedHashMap<>();

        salaries.put("Петров", 123.22);
        salaries.put("Сидоров", 1378.00);
        salaries.put("Иванов", 3434.34);
        salaries.forEach((key, value) -> System.out.println(key + ": " + value));

        salaries.put("Петров", 200.0);      // ключ уже есть: значение заменится, позиция — нет
        System.out.println(salaries);

        salaries.remove("Сидоров");
        salaries.put("Сидоров", 1500.0);    // после удаления — снова в конец
        System.out.println(salaries);
    }
}

Вывод:

Петров: 123.22
Сидоров: 1378.0
Иванов: 3434.34
{Петров=200.0, Сидоров=1378.0, Иванов=3434.34}
{Петров=200.0, Иванов=3434.34, Сидоров=1500.0}

Цена списка — память: две лишние ссылки на каждую запись и немного более медленные put()/remove(), потому что нужно поддерживать связи. Тот же приём использует LinkedHashSet: внутри него лежит LinkedHashMap (подробнее — в уроке Set, HashSet, LinkedHashSet).

Порядок: HashMap, LinkedHashMap и TreeMap

Три основные реализации Map по-разному отвечают на вопрос «в каком порядке я получу пары при обходе»: HashMap порядок не гарантирует, LinkedHashMap возвращает пары в порядке вставки (или доступа), TreeMap сортирует их по ключам. Выбирать между ними стоит именно по этому признаку.

import java.util.*;

public class OrderCompare {
    public static void main(String[] args) {
        Map<Integer, String> hash = new HashMap<>();
        Map<Integer, String> linked = new LinkedHashMap<>();
        Map<Integer, String> tree = new TreeMap<>();

        for (Map<Integer, String> m : List.of(hash, linked, tree)) {
            m.put(30, "a");
            m.put(5, "b");
            m.put(17, "c");
        }
        System.out.println("HashMap:       " + hash);
        System.out.println("LinkedHashMap: " + linked);
        System.out.println("TreeMap:       " + tree);
    }
}

Вывод:

HashMap:       {17=c, 5=b, 30=a}
LinkedHashMap: {30=a, 5=b, 17=c}
TreeMap:       {5=b, 17=c, 30=a}

Порядок HashMap здесь определяется номерами бакетов (17 → 1, 5 → 5, 30 → 14 при ёмкости 16) — это деталь реализации текущих JDK, а не гарантия: после resize или на другой версии он может измениться.

Если нужна именно сортировка, а не сохранение порядка, — это задача TreeMap: см. урок TreeMap, SortedMap и NavigableMap. Остальные реализации (Hashtable, ConcurrentHashMap, EnumMap и др.) сравниваются в уроке Интерфейс Map.

Конструкторы LinkedHashMap

У LinkedHashMap пять конструкторов и, начиная с Java 19, статическая фабрика newLinkedHashMap(int). Четыре конструктора повторяют HashMap, а пятый принимает флаг accessOrder — только через него включается порядок доступа, нужный для LRU-кэша.

Копирующий конструктор удобен, чтобы «заморозить» текущий порядок произвольной карты: new LinkedHashMap<>(treeMap) сохранит отсортированный порядок TreeMap, но дальнейшие вставки пойдут в конец, без сортировки.

Порядок доступа: accessOrder = true

В режиме порядка доступа (accessOrder = true) LinkedHashMap при каждом обращении к существующему ключу переносит его запись в конец списка. В начале остаётся пара, к которой дольше всех не обращались, — именно её вытесняет LRU-кэш (Least Recently Used, «давно не использованный»).

Map<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);
System.out.println(map);   // {a=1, b=2, c=3}

map.get("a");              // доступ: "a" уходит в конец
System.out.println(map);   // {b=2, c=3, a=1}

map.containsKey("b");      // НЕ доступ: порядок не меняется
System.out.println(map);   // {b=2, c=3, a=1}

map.put("b", 20);          // put существующего ключа — тоже доступ
System.out.println(map);   // {c=3, a=1, b=20}

Какие операции считаются «доступом», описано в Javadoc класса:

removeEldestEntry и LRU-кэш

LRU-кэш на LinkedHashMap пишется в десяток строк: создайте карту с accessOrder = true и переопределите защищённый метод removeEldestEntry(), чтобы он возвращал true, когда размер превысил лимит. Тогда после каждой вставки нового ключа карта сама удалит самую давно использованную пару.

Сигнатура метода:

protected boolean removeEldestEntry(Map.Entry<K, V> eldest)

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

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

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

    public LruCache(int capacity) {
        super(16, 0.75f, true);          // true — порядок доступа
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;        // превысили лимит — удалить самую старую пару
    }

    public static void main(String[] args) {
        LruCache<Integer, String> cache = new LruCache<>(3);
        cache.put(1, "один");
        cache.put(2, "два");
        cache.put(3, "три");
        System.out.println(cache);

        cache.get(1);                    // 1 стал самым свежим
        cache.put(4, "четыре");          // вытесняется 2 — к нему дольше всех не обращались
        System.out.println(cache);

        cache.put(3, "ТРИ");             // существующий ключ: обновление + доступ, без вытеснения
        System.out.println(cache);

        cache.put(5, "пять");            // вытесняется 1
        System.out.println(cache);
        System.out.println(cache.get(2)); // 2 уже вытеснен
    }
}

Вывод:

{1=один, 2=два, 3=три}
{3=три, 1=один, 4=четыре}
{1=один, 4=четыре, 3=ТРИ}
{4=четыре, 3=ТРИ, 5=пять}
null

Если создать ту же карту без флага (super(16, 0.75f, false) или просто super()), получится FIFO-кэш: вытесняется не давно использованная, а давно добавленная пара, и get() на порядок не влияет.

Ограничения такого кэша

• Не потокобезопасен. Для общего доступа оберните его: Map<K, V> safe = Collections.synchronizedMap(new LruCache<>(100));. Синхронизация нужна и на чтение, потому что get() меняет порядок. Обход такой обёртки всё равно заключают в synchronized (safe) { ... }.
• Лимит — в штуках, а не в байтах, и нет срока жизни записей (TTL). Для нагруженных кэшей с TTL, статистикой и конкурентным доступом используют библиотеку Caffeine.
• Наследование открывает весь API LinkedHashMap. Если это нежелательно, храните карту в приватном поле класса-кэша и наружу отдавайте только get()/put().

Общий обзор потокобезопасных коллекций (ConcurrentHashMap, ConcurrentSkipListMap и др.) — в уроке Коллекции в Java.

LinkedHashMap и SequencedMap (Java 21)

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

import java.util.LinkedHashMap;

public class SequencedMapExample {
    public static void main(String[] args) {
        LinkedHashMap<String, Integer> steps = new LinkedHashMap<>();
        steps.put("build", 1);
        steps.put("test", 2);
        steps.put("deploy", 3);

        System.out.println(steps.firstEntry());      // build=1
        System.out.println(steps.lastEntry());       // deploy=3

        steps.putFirst("checkout", 0);
        System.out.println(steps);                   // {checkout=0, build=1, test=2, deploy=3}

        steps.putLast("build", 1);                   // существующий ключ переезжает в конец
        System.out.println(steps);                   // {checkout=0, test=2, deploy=3, build=1}

        System.out.println(steps.reversed());        // {build=1, deploy=3, test=2, checkout=0}
        System.out.println(steps.pollFirstEntry());  // checkout=0
        System.out.println(steps);                   // {test=2, deploy=3, build=1}
    }
}

На чём чаще всего ошибаются

Самая частая ошибка с LinkedHashMap — вызывать get() внутри обхода карты в режиме accessOrder = true: это структурное изменение, и итератор бросает ConcurrentModificationException. Остальные промахи связаны с ожиданием сортировки и с тем, когда именно срабатывает removeEldestEntry().

Что выведет этот код?

Map<String, Integer> m = new LinkedHashMap<>(16, 0.75f, true);
m.put("a", 1);
m.put("b", 2);
m.put("c", 3);

for (String k : m.keySet()) {
    System.out.println(k + "=" + m.get(k));
}

a=1
Exception in thread "main" java.util.ConcurrentModificationException

m.get("a") переносит «a» в конец и увеличивает modCount; на следующем шаге итератор замечает изменение и бросает исключение. Исправление — обходить entrySet(): значение берётся из самой записи, порядок не меняется.

for (Map.Entry<String, Integer> e : m.entrySet()) {
    System.out.println(e.getKey() + "=" + e.getValue());
}
// Вывод:
// a=1
// b=2
// c=3

Подробнее о том, как итераторы отслеживают изменения, — в уроке Iterator. Другие типичные промахи:

• Ждут сортировки. LinkedHashMap только запоминает порядок вставки; ключи 30, 5, 17 так и останутся в этом порядке. Для сортировки нужен TreeMap.
• Создают карту через конструктор без флага и удивляются, что LRU-кэш вытесняет «горячие» ключи. Без accessOrder = true получается FIFO.
• Ждут вытеснения при обновлении. put() существующего ключа не добавляет новую пару, поэтому removeEldestEntry() не вызывается и размер не растёт.
• Сравнивают карты с учётом порядка. equals() у Map порядок не учитывает: LinkedHashMap {a=1, b=2} равна LinkedHashMap {b=2, a=1} и даже HashMap с теми же парами.