Java Map: How to Preserve Insertion Order

Java provides a set of classes that implement the Map interface. The map interface defines how to map keys with values. This is the basic functionality, but there are several different ways to obtain this behavior. In fact, many different classes implement the Map interface. One of the nuances in the key/value essential feature regards how the map returns its entries:

• Are the returned keys ordered?

• Are they ordered in the same way they were inserted or are they sorted using a natural or specified order?

In this article, we will quickly describe the choices available for the above scenarios, and we will then focus on describing the available implementation for preserving the insertion order.

You can find the code fragments used in this post in the following GitHub project: java miscellaneous tips.

Java Map: Preserve Insertion Order with LinkedHashMap 

Regarding the order in which we can extract the keys of a Map object we have these three choices:

• For non-ordered keys, the HashMap class is provided by Java. The HashMap class is basically implemented as a hash table data structure and does not preserve order.
• For keys sorted in a natural order, or by using a specific Comparator object, an implementation is provided by the TreeMap class. The TreeMap class is implemented internally as a red-black tree data structure to optimize the sorting process.
• Finally, if we want to preserve the order of the keys as they were inserted, the natural choice is the LinkedHashMap class.

The LinkedHashMap class internally uses a doubly-linked list and the keys can be extracted in the same order they were inserted. As with all the implementations of the Map interface, it does not allow duplicates. It can store a single null key but at the same time multiple null values. The following snippet shows an example of its basic usage:

   LinkedHashMap<Integer, String> preserveOrderMap = new LinkedHashMap<Integer, String>();  
   preserveOrderMap.put(1,"First");  
   preserveOrderMap.put(2,"Second");  
   preserveOrderMap.put(3,"Third");
   preserveOrderMap.put(4,"Fourth");

   for(Map.Entry mapEntry: preserveOrderMap.entrySet()){  
        System.out.println(mapEntry.getKey() + " - " + mapEntry.getValue());  
   }  

In the example above the loop on the LinkedHashMap entries prints the keys and related values in the same order in which they were put into the map.