How to preserve insertion order in HashMap?

java

hashmap

collections

best-practices

byAnton Shumikhin·Sep 20, 2024

Switch from HashMap to LinkedHashMap to maintain insertion order. Differing from HashMap, which doesn't commit to any specific order of entries, LinkedHashMap logs the order in which keys are initially added.

Here is a quick example:

Map<Integer, String> orderedMap = new LinkedHashMap<>();
orderedMap.put(1, "One");   // inserted first
orderedMap.put(2, "Two");   // inserted second
orderedMap.put(3, "Three"); // you guessed it, third!
orderedMap.values().forEach(System.out::println); // Outputs: One, Two, Three

Iterating over it reflects the insertion sequence, making sure the output order mirrors the insertion order.

Detailed breakdown of LinkedHashMap

LinkedHashMap is a subclass of HashMap, with a doubly-inked list that preserves the entry order embedded within it. This class offers two specific modes:

Insertion order (default mode): Preserves the original entry sequence.
Access order: Entry order rearranges when an entry is accessed, which is triggered through the constructor.

Navigating special use cases

If you need a cache functionality that operates under the least-recently-used policy, LinkedHashMap is the key, thanks to its unique access order mode.

Although TreeMap preserves a sorted ordering of keys, it doesn't retain the insertion order. Alternatively, an ArrayList of Pair objects or Map.Entry objects can be a good substitute when insertion order isn't a deal-breaker.

Unpacking performance notes

LinkedHashMap upholds O(1) performance for addition, removal, and access operations in general, not deviating from HashMap, but it ensures a predictable iteration order.

Further understanding with advanced hints

Here's some extra ammo for your LinkedHashMap arsenal:

Custom eviction policy: Override removeEldestEntry() for a size-limited cache that lets go of the eldest (classic eldest child syndrome, right?).
Serialization: Keep in mind, if serialization is on the cards, remember to factor in the additional overhead the linked list brings.
Null keys & values: Yes, LinkedHashMap, like HashMap, allows null keys and values. Yet, bear in mind to tread carefully with these in multi-threaded contexts.