Java LinkedHashMap

LinkedHashMap<K, V> is HashMap<K, V> with a doubly-linked list threaded through every entry. The hash table does its usual job — O(1) put, get, remove — and the linked list gives you a guaranteed, predictable iteration order. By default that order is insertion order; flip one constructor flag and it becomes access order, the building block of a least-recently-used (LRU) cache.

Two orderings, one class

The constructors mirror HashMap, plus one more:

new LinkedHashMap<>();                              // insertion order
new LinkedHashMap<>(16, 0.75f, false);              // insertion order, explicit
new LinkedHashMap<>(16, 0.75f, true);               // ACCESS order

That third boolean is the accessOrder flag. With it set to false (the default), each put of a new key appends the entry to the end of the linked list and re-puts of an existing key leave its position alone. With it set to true, every get, put, or getOrDefault that touches a key moves that entry to the end of the list — the most-recently-accessed entry is always last; the least-recently-accessed is always first.

That second mode is rare in application code but the only place you ever see it is exactly the place you need it most: implementing a cache.

Insertion-order iteration is the common use

90% of the time you reach for LinkedHashMap because you want stable output. Examples:

• Returning a Map<String, Object> from a JSON-serializing endpoint and wanting the fields to appear in the order you inserted them.
• Logging a map's contents in a deterministic order for diffs.
• Building configuration where order matters (think: middleware chain, header order, validation pipeline).
• Returning a Map from a public API and not wanting callers to depend on HashMap's arbitrary order.

The cost over HashMap is two extra references per entry (the before and after pointers). For configuration-sized maps it doesn't matter; for tight loops over very large maps you might prefer a HashMap if you can.

Iteration is proportional to size

A side benefit: iterating a LinkedHashMap walks the linked list, which contains exactly size entries. Iterating a HashMap walks every bucket slot — including empties. For a sparsely populated map the difference is meaningful.

Building an LRU cache

The killer feature of access-order is the protected removeEldestEntry hook. It's called after every put, and if it returns true, the map removes its first (eldest) entry. Combining the two:

class LruCache<K, V> extends LinkedHashMap<K, V> {
  private final int max;
  LruCache(int max) { super(16, 0.75f, true); this.max = max; }
  @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() > max;
  }
}

Twelve lines for a thread-unsafe but fully functional LRU cache. Every get re-orders the entry to the end; every put calls removeEldestEntry; once the size exceeds max, the entry at the front (the least-recently-accessed) is evicted.

For thread-safe LRU you wrap with Collections.synchronizedMap or — better — use a real cache library (Caffeine), because the access-order updates make every get a write under the hood and the simple synchronized wrapper serialises all reads. But for single-threaded code, this is the textbook trick and it's worth knowing.

Nulls and the rest of the rules

Same as HashMap: one null key, any number of null values. Not thread-safe. Equality is the structural equality Map defines — a LinkedHashMap and a HashMap with the same entries are equals. The iteration order is not part of equality; it's just what you get if you iterate.

A worked example: insertion order, access order, and an LRU cache

The program below builds a small middleware chain in insertion order, contrasts the iteration of HashMap vs LinkedHashMap on the same data, then implements a tiny LRU cache and watches it evict.

What to take from the run:

• The pipeline iterates in the order log → auth → rateLimit → handler — exactly the order it was inserted. A plain HashMap would still have all four entries but the order would be arbitrary.
• HashMap and LinkedHashMap containing the same data print in different orders; the LinkedHashMap matches keys and the HashMap doesn't.
• The LRU cache reordered when get(\"a\") was called — a went to the end of the list, making b the new eldest. The next put(\"d\", \"D\") triggered eviction of b, not a. That's the access-order rule in action.

What's next

The third standard Map implementation gives you something neither hash-based one can: sorted iteration by key and range queries (subMap, headMap, tailMap, firstKey, lastKey). TreeMap is up next; the structure is identical to TreeSet underneath — they're literally the same red-black tree code.

Practice