Краткий ответ

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

Исторический контекст

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

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

Постановка проблемы

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

Неверный выбор коллекции приводит к нестабильных результатам сериализации, непредсказуемому порядке отображения данных и трудно воспроизводимым тестам. Если порядок действительно является требованием, он должен обеспечиваться контрактом выбранной реализации, а не наблюдением за текущим поведением.

Подробное решение

При добавлении записи LinkedHashMap помещает её в хеш-таблицу и одновременно подключает к двусвязному списку. Итератор проходит по связям этого списка, поэтому порядок обхода не зависит от расположения бакетов в таблице.

По умолчанию используется порядок вставки: повторная запись уже существующего ключа не перемещает его в конец. Конструктор с режимом порядка доступа позволяет организовать access-order: успешно найденные или обновлённые записи перемещаются в конец списка. Это удобно для простого LRU-кэша.

Ожидаемая сложность get, put и remove обычно составляет O(1), как у HashMap, при корректных equals и hashCode. Итерация по LinkedHashMap имеет сложность O(n) по числу записей и не требует последовательно просматривать пустые бакеты; за это реализация платит дополнительной памятью на ссылки списка.

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

Map<String, Integer> map = new LinkedHashMap<>();
map.put("B", 2);
map.put("A", 1);
map.put("C", 3);

for (String key : map.keySet()) {
    System.out.print(key + " "); // B A C
}

В многопоточном коде LinkedHashMap сам по себе не является потокобезопасным. Особенно важно, что операция чтения может изменять структуру списка в режиме порядка доступа, поэтому для общего доступа нужна внешняя синхронизация или другая подходящая коллекция.

Ситуация из практики

Сервис формирует JSON-ответ с полями в порядке, заданном конфигурацией. Использование HashMap иногда давало другой порядок после изменения набора полей, из-за чего возникали нестабильные снимки ответов и сложные для анализа различия.

Рассматривались три варианта: сортировать ключи перед каждой сериализацией, хранить порядок отдельно в списке или использовать LinkedHashMap. Сортировка давала детерминированный, но не обязательно конфигурационный порядок и добавляла стоимость O(n log n); отдельный список требовал синхронно поддерживать две структуры.

Выбрали LinkedHashMap, потому что порядок добавления совпадал с требованием, а операции доступа оставались ожидаемо постоянными. Если бы требовался алфавитный порядок, вместо него следовало бы рассмотреть TreeMap, поскольку это уже другая гарантия и другая сложность операций — обычно O(log n).

Что кандидаты часто упускают

Перемещается ли существующий ключ в конец при повторном put в режиме порядка вставки?

Нет. Обновление значения для уже присутствующего ключа не меняет его позицию в списке. Это отличает порядок вставки от порядка доступа и важно, если карта используется для воспроизведения последовательности поступления ключей.

Можно ли считать порядок HashMap стабильным, если он не меняется в конкретном запуске?

Нет. Наблюдаемая стабильность не является гарантией контракта. На порядок могут повлиять хеш-коды ключей, изменение ёмкости таблицы, удаление записей и детали реализации; код должен опираться только на гарантии типа коллекции.

Почему режим порядка доступа может сделать даже чтение структурным изменением?

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