Which type of Map data structure ensures the preservation of insertion order?

In Java, the data structure Map that preserves the order of element insertion is LinkedHashMap. It inherits properties from HashMap but additionally maintains a linked list of elements in the order they were added.

Example of usage:

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

Thus, LinkedHashMap guarantees that during iteration, elements will be returned in the order they were inserted.