skip to content

What is LinkedHashMap and how does its iteration order differ from HashMap?

level: juniorimportance: must knowfreq 70%

answer

  1. HashMap + doubly-linked list
  2. Default = insertion order
  3. Re-put does not reorder
  4. Lookups still O(1)
  5. TreeMap = sorted, LinkedHashMap = insertion

basics

~10 s

LinkedHashMap is a HashMap that also remembers the order you put entries in, so iterating returns them in insertion order. A plain HashMap gives no order guarantee and can appear random.

solid answer

~40 s

LinkedHashMap extends HashMap and adds a doubly-linked list running through all entries, so iteration is predictable. By default it iterates in insertion order (the order keys were first added; re-putting an existing key does not move it). A plain HashMap makes no ordering promise: its iteration order depends on hash codes and bucket layout and can change between runs or after resizing. LinkedHashMap keeps HashMap's O(1) average get/put because lookups still use the hash table; the linked list only governs iteration. The trade-off is a slightly larger memory footprint (two extra pointers per entry) and marginally slower iteration-unrelated mutations. Use it when you need a map with stable, human-meaningful ordering — for example preserving the order of parsed config keys or building an ordered response.

code

java · 10 lines
java
Map<String, Integer> lhm = new LinkedHashMap<>();
lhm.put("b", 1);
lhm.put("a", 2);
lhm.put("c", 3);
lhm.put("a", 9); // re-put: updates value, does NOT move 'a'
System.out.println(lhm); // {b=1, a=9, c=3} -- insertion order preserved

Map<String, Integer> hm = new HashMap<>();
hm.put("b", 1); hm.put("a", 2); hm.put("c", 3);
System.out.println(hm); // order unspecified, e.g. {a=2, b=1, c=3}

go deeper

for a junior

Knows LinkedHashMap iterates in insertion order while HashMap does not guarantee any order.

for a middle

Explains the doubly-linked list mechanism, that lookups stay O(1), and that re-put does not reorder.

for a senior

Compares memory/perf trade-offs vs HashMap and TreeMap and picks the right map per use case (determinism, ordered output).

for a principal

Reasons about when ordering guarantees matter for API contracts, test determinism, and serialization, and weighs the per-entry memory overhead at scale.

## What a Map is A **Map** stores key → value pairs and lets you look a value up by its key. **HashMap** is the most common implementation: it uses an array of *buckets*; a key's `hashCode()` decides which bucket it lands in, giving average O(1) (constant-time) `get`/`put`. ## The ordering problem Because HashMap places keys by hash value, the order you get when you iterate (`for (var e : map.entrySet())`) has **no relationship** to the order you inserted them. It can even differ between two runs of the same program and changes when the map *resizes* (grows its bucket array). For many tasks that is fine; sometimes you need a predictable order. ## What LinkedHashMap adds **LinkedHashMap** `extends HashMap`. It keeps the exact same hash-table machinery (so lookups stay O(1)), but it *also* threads a **doubly-linked list** through every entry. "Doubly-linked" means each entry holds a `before` pointer and an `after` pointer to its neighbours in that list. This list defines iteration order, independent of which bucket an entry physically sits in. By default the list is maintained in **insertion order**: when you add a brand-new key, its entry is appended to the end of the list. Re-`put`-ting a key that already exists only updates the value — it does **not** move the entry — so the position reflects *first* insertion. ## Cost The price is two extra reference fields per entry (more memory) and a tiny bit of work to splice entries into the list on insert/remove. Average get/put remain O(1). ## When to use it Reach for LinkedHashMap whenever you want a map whose iteration order is meaningful and stable: preserving the order of fields parsed from JSON/config, producing deterministic output for tests, or (with access-order mode) building an LRU cache. If you need *sorted* order instead, use `TreeMap` (O(log n), sorted by key), not LinkedHashMap.

  • Does re-inserting an existing key change its position in a default LinkedHashMap?
    No. In insertion-order mode only the *first* insertion sets the position; a later put with the same key just replaces the value. (In access-order mode it would move to the end.)
  • If you need keys sorted alphabetically, which map should you use?
    TreeMap, which keeps keys in their natural (or comparator) order at O(log n) per operation. LinkedHashMap only preserves insertion or access order, not sorted order.

HashMap is a bag of labeled items you pull out in no particular order; LinkedHashMap is the same bag but with a string tied through them in the order you dropped them in, so you can walk the string and visit them in sequence.

saying these in an interview costs you the question

  • Claiming HashMap preserves insertion order (it does not; that confuses it with LinkedHashMap).
  • Saying LinkedHashMap is sorted — it is not; sorting is TreeMap's job.
  • Thinking the linked list slows lookups to O(n) — get/put stay O(1); the list only drives iteration.
  • Believing re-putting an existing key moves it to the end in the default mode.

context

resolving links…