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

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

Пример:

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

// Выведет в порядке добавления: z=3, a=1, b=2
System.out.println(orderedMap);

Также LinkedHashMap может поддерживать порядок доступа (access-order) при использовании специального конструктора с параметром accessOrder=true. В этом случае при обращении к элементу он перемещается в конец.