LinkedHashMap

LinkedHashMap is a direct subclass of HashMap that was added to the Java Collections Framework in JDK 1.4.

LinkedHashMap is a direct subclass of HashMap that was added to the Java Collections Framework in JDK 1.4.
While a HashMap delivers excellent performance, its iteration order is completely arbitrary.
LinkedHashMap keeps the same O(1) average‑time operations of a hash table but adds a doubly‑linked list that connects every entry.
That list guarantees a predictable traversal order without sacrificing the speed of key‑based lookups.

How the underlying structure works

Each entry in a LinkedHashMap extends the normal hash‑table node with two extra pointers: before and after.
The map also maintains two references, head and tail, that mark the ends of the list.
When a node is inserted, removed, or accessed, the list is updated through a set of callback hooks (afterNodeInsertion, afterNodeAccess, etc.).
This “template‑method” style lets the core hash logic stay unchanged while the ordering logic is layered on top.

  • Lookup / Insertion / Deletion – still resolved by hashing, so the average complexity remains O(1).
  • Iteration – follows the linked list, so the time is proportional to the number of entries and independent of the table’s capacity.

Two traversal modes

LinkedHashMap can operate in either of two modes, controlled by the accessOrder flag:

Mode Default Behaviour
Insertion order false Iteration follows the order in which keys were first inserted. Re‑inserting an existing key does not change its position.
Access order true Every get, getOrDefault, or containsKey moves the accessed entry to the tail of the list. The head always holds the least recently used entry.

The access‑order mode is the foundation of many LRU cache implementations.

Quick example

Map<String, Integer> scores = new LinkedHashMap<>();
scores.put("Chinese", 92);
scores.put("Math", 98);
scores.put("English", 95);

for (Map.Entry<String, Integer> e : scores.entrySet()) {
    System.out.println(e.getKey() + " = " + e.getValue());
}

The output will be in the same order as the put calls.
If the same map were a plain HashMap, the order would be essentially random and should not be relied upon.

Building an LRU cache

By enabling access order and overriding removeEldestEntry, a lightweight LRU cache can be created in a handful of lines:

public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LruCache(int maxSize) {
        super(16, 0.75f, true);   // true → access order
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;  // evict the oldest entry
    }
}

Each read operation moves the entry to the tail, and when the size exceeds maxSize, the head entry (the least recently used) is automatically removed.

The same technique can produce a FIFO cache by using the default insertion order and the same removeEldestEntry logic.

Comparing with other Map implementations

Implementation Underlying data structure Ordering Typical use‑case Null keys
HashMap Array + linked list / red‑black tree Unordered Fast lookups, no ordering needed Allowed
LinkedHashMap Hash table + doubly‑linked list Insertion / access Preserving insertion order or LRU behaviour Allowed
TreeMap Red‑black tree Sorted by key Range queries, natural ordering Not allowed
  • Against HashMap – The extra list adds a small memory overhead and a slight insertion cost, but iteration becomes deterministic and can be faster when the table is sparsely populated.
  • Against TreeMap – TreeMap offers key‑based ordering and efficient range operations (e.g., headMap, tailMap). LinkedHashMap does not sort keys; it only preserves the order of operations.
  • Thread safety – None of these maps are thread‑safe. Wrap them with Collections.synchronizedMap or use ConcurrentHashMap for concurrent scenarios (note that ConcurrentHashMap does not guarantee any order).

Practical guidelines

  • When you need predictable iteration (e.g., maintaining the order of configuration properties, form fields, or output columns), choose LinkedHashMap.
  • When you need sorted keys or range queries, TreeMap is the natural choice.
  • When order is irrelevant and you want the absolute best performance, stick with HashMap.
  • If you enable access order, remember that every get mutates the internal structure. In a multi‑threaded environment you must provide external synchronization, and you should avoid modifying the map while iterating to prevent ConcurrentModificationException.
  • Memory trade‑off – The linked list consumes roughly two additional references per entry. For millions of entries, this can be noticeable, but the deterministic order often justifies the cost.

Bottom line

LinkedHashMap offers a sweet spot between the raw speed of a hash table and the convenience of a predictable order.
With minimal extra memory and a tiny performance hit, it gives you:

  • O(1) average‑time operations for lookup, insertion, and deletion.
  • Deterministic iteration that follows either insertion or access order.
  • Built‑in eviction hooks that make LRU or FIFO caches trivial to implement.

For most applications that require a stable iteration order without sacrificing hash‑table performance, LinkedHashMap is the go‑to solution.