¿Qué tipo de estructura de datos Map garantiza mantener el orden de inserción de los elementos?

En Java, la estructura de datos Map que mantiene el orden de inserción de los elementos es LinkedHashMap. Hereda las propiedades de HashMap, pero además soporta una lista enlazada de los elementos en el orden en que fueron añadidos.

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

De esta forma, LinkedHashMap garantiza que al recorrer los elementos, estos serán devueltos en el orden de inserción.