LinkedHashMap

In short: A Map implementation that — unlike the regular HashMap — preserves the insertion order (or, optionally, the access order) of the keys.

In more detail: Internally, LinkedHashMap combines a hash table for fast access with a linked list that tracks the order of the entries. With the access-order mode (accessOrder = true), this can, for example, be used to simply build an LRU cache (least recently used entries last).

In Depth

Map<String, Integer> normal = new HashMap<>();
Map<String, Integer> ordered = new LinkedHashMap<>();
 
for (Map<String, Integer> map : List.of(normal, ordered)) {
    map.put("Zebra", 1);
    map.put("Anna", 2);
    map.put("Middle", 3);
}
 
System.out.println(normal);   // order NOT guaranteed, e.g. {Anna=2, Middle=3, Zebra=1}
System.out.println(ordered); // ALWAYS insertion order: {Zebra=1, Anna=2, Middle=3}
 
// LRU cache with fixed size: oldest entry automatically evicted
Map<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true) { // true = access order
    protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
        return size() > 3; // keep at most 3 entries
    }
};

LinkedHashMap costs somewhat more memory than HashMap (for the extra linked list that tracks the order) and is minimally slower when inserting — but access via get() stays just as fast (O(1) on average), because internally the same hash table is still used for the actual lookup. The combination of access-order mode and an overridden removeEldestEntry() (as in the LRU example) is a classic, compact pattern for building a simple fixed-capacity cache without having to write a custom data structure from scratch.

Which map implementation when?

Java offers three common Map implementations with different order guarantees, analogous to the three Set variants:

• HashMap: fastest access, NO guaranteed order — default choice when order doesn’t matter.
• LinkedHashMap: insertion order (or access order), minimally slower than HashMap.
• TreeMap: always sorted by key (natural order or a custom Comparator), slower (O(log n) instead of O(1)).

Practical example: word frequencies in insertion order

A use case where order actually matters: the order in which different words first appear should be preserved, while still counting quickly:

Map<String, Integer> frequency = new LinkedHashMap<>();
for (String word : text.split("\\s+")) {
    frequency.merge(word, 1, Integer::sum); // counts up, without a prior containsKey()
}
// output happens in the order in which words first appeared
frequency.forEach((word, count) -> System.out.println(word + ": " + count));

With a normal HashMap, the output order here would be unpredictable — for reproducible, traceable output (e.g. in tests or logs), LinkedHashMap is therefore often the better choice, even when the actual order wouldn’t necessarily matter for the domain logic.

See also: HashSet, Collections