Какой тип структуры данных Map обеспечивает сохранение порядка вставки элементов?

В Java структура данных Map, которая сохраняет порядок вставки элементов, — это LinkedHashMap. Она наследует свойства HashMap, но дополнительно поддерживает связный список элементов в порядке их добавления.

Пример использования:

Map<String, Integer> map = new LinkedHashMap<>();
map.put("one", 1);
map.put("two", 2);
map.put("three", 3);

for (String key : map.keySet()) {
    System.out.println(key);
}
// Выведет:
// one
two
// three

Таким образом, LinkedHashMap гарантирует, что при обходе элементов они будут возвращены в порядке вставки.