Qual tipo de estrutura de dados Map garante a preservação da ordem de inserção dos elementos?

Em Java, a estrutura de dados Map que mantém a ordem de inserção dos elementos é o LinkedHashMap. Ele herda as propriedades do HashMap, mas também suporta uma lista ligada de elementos na ordem em que foram adicionados.

Exemplo de uso:

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);
}
// Vai mostrar:
// one
two
// three

Assim, o LinkedHashMap garante que ao percorrer os elementos, eles serão retornados na ordem de inserção.