Java LinkedHashMap

LinkedHashMap<K, V> — это HashMap<K, V> с двусвязным списком, пронизывающим каждую запись. Хэш-таблица выполняет свою обычную работу — O(1) для put, get, remove — а связный список обеспечивает гарантированный и предсказуемый порядок итерации. По умолчанию этот порядок — порядок вставки; один флаг конструктора меняет его на порядок доступа — строительный блок кэша вытеснения наименее используемых элементов (LRU).

Два порядка, один класс

Конструкторы повторяют HashMap, плюс ещё один:

new LinkedHashMap<>();                              // insertion order
new LinkedHashMap<>(16, 0.75f, false);              // insertion order, explicit
new LinkedHashMap<>(16, 0.75f, true);               // ACCESS order

Третий boolean — это флаг accessOrder. При значении false (по умолчанию) каждый put нового ключа добавляет запись в конец связного списка, а повторный put существующего ключа не меняет его позицию. При значении true каждый get, put или getOrDefault, затрагивающий ключ, перемещает эту запись в конец списка — последний элемент всегда самый недавно использованный, первый — наименее используемый.

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

Итерация в порядке вставки — наиболее распространённый случай

В 90% случаев вы используете LinkedHashMap потому, что хотите стабильный вывод. Примеры:

• Возврат Map<String, Object> из конечной точки сериализации JSON с полями в порядке вставки.
• Логирование содержимого map в детерминированном порядке для сравнения.
• Построение конфигурации, в которой порядок важен (например: цепочка middleware, порядок заголовков, конвейер валидации).
• Возврат Map из публичного API без риска, что вызывающий код будет зависеть от произвольного порядка HashMap.

Дополнительные расходы по сравнению с HashMap — две дополнительные ссылки на запись (указатели before и after). Для map конфигурационного размера это несущественно; при итерации в узких циклах по очень большим map можно предпочесть HashMap, если порядок не важен.

Итерация пропорциональна размеру

Дополнительное преимущество: итерация по LinkedHashMap проходит по связному списку, который содержит ровно size записей. Итерация по HashMap проходит по всем слотам корзин — включая пустые. Для разреженных map разница ощутима.

Построение LRU-кэша

Ключевая возможность режима доступа — защищённый хук removeEldestEntry. Он вызывается после каждого put, и если возвращает true, map удаляет свою первую (самую старую) запись. Объединяя оба механизма:

class LruCache<K, V> extends LinkedHashMap<K, V> {
  private final int max;
  LruCache(int max) { super(16, 0.75f, true); this.max = max; }
  @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() > max;
  }
}

Двенадцать строк для нитебезопасного, но полностью функционального LRU-кэша. Каждый get перемещает запись в конец; каждый put вызывает removeEldestEntry; как только размер превышает max, запись в начале (наименее недавно использованная) вытесняется.

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

Null-значения и прочие правила

То же, что и в HashMap: один null-ключ, любое количество null-значений. Не потокобезопасен. Равенство определяется структурным равенством, описанным в Map — LinkedHashMap и HashMap с одинаковыми записями являются equals. Порядок итерации не является частью равенства; это просто то, что вы получаете при итерации.

Рабочий пример: порядок вставки, порядок доступа и LRU-кэш

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

Что следует извлечь из запуска:

• Конвейер итерируется в порядке log → auth → rateLimit → handler — именно в том порядке, в котором был вставлен. Обычный HashMap содержал бы все четыре записи, но порядок был бы произвольным.
• HashMap и LinkedHashMap с одинаковыми данными выводят в разном порядке; LinkedHashMap совпадает с keys, а HashMap — нет.
• LRU-кэш изменил порядок при вызове get(\"a\") — a перешёл в конец списка, сделав b новым старейшим элементом. Следующий put(\"d\", \"D\") вызвал вытеснение b, а не a. Вот правило порядка доступа в действии.

Что дальше

Третья стандартная реализация Map даёт то, чего не могут дать ни одна из хэш-основанных: итерацию в отсортированном порядке по ключу и запросы диапазонов (subMap, headMap, tailMap, firstKey, lastKey). TreeMap — следующая тема; её структура идентична TreeSet внутри — это буквально один и тот же код красно-чёрного дерева.

Практика