Какая реализация Map в Java сохраняет порядок вставки элементов?

LinkedHashMap<K, V> — реализация Map, которая сохраняет порядок вставки пар ключ-значение (или порядок доступа, если настроено).

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

Пример (порядок вставки):

Map<String, Integer> map = new LinkedHashMap<>();
map.put("z", 3);
map.put("a", 1);
map.put("b", 2);

for (String key : map.keySet()) {
    System.out.println(key); // Гарантированный вывод: z, a, b
}

Ключевые особенности:

• Порядок по умолчанию: Порядок вставки (insertion-order).
• Порядок доступа: Можно создать с флагом accessOrder = true, тогда при каждом обращении (get, put) элемент перемещается в конец, реализуя основу для LRU-кэша.
• Производительность: Немного медленнее HashMap из-за накладных расходов на поддержание списка, но быстрее TreeMap.
• Итерация: Итерация по LinkedHashMap выполняется за O(n) и предсказуема.