LinkedHashMap: Insertion Order, Access Order, and a Real LRU

A packing slip must print line items in the order they were scanned, not in hash-bin order. A tiny in-process cache must drop the order nobody has touched, not the one that arrived first. Both jobs are a HashMap plus a well-defined encounter order.

LinkedHashMap is HashMap with a doubly linked list through the entries. The HashMap post owns spreading, treeify, and resize. The LRU cache post owns the two-layout idea (map finds the node, list ranks recency). This page is the JDK type: insertion order by default, accessOrder when recency matters, and removeEldestEntry for a bounded LRU in about ten lines.

HashMap plus a list of entries

Each entry is still in a hash bin. Each entry also has before / after pointers. Iteration walks that list, not the bucket array. Lookup is still expected O(1) with a decent hash — same table as HashMap.

table (hash bins):     [ i ] -> E("SKU-1") -> …     same spreading / treeify / resize

list (encounter):      head <-> SKU-1 <-> SKU-2 <-> SKU-3 <-> tail
                       first / eldest                         last / newest (or MRU)

You pay two extra references per entry. That is the memory tax versus HashMap. Nulls match HashMap (one null key, null values). Iterators are still fail-fast. Still not thread-safe. Program to Map — or to SequencedMap on Java 21 — and new LinkedHashMap<>().

Constructor / method	Job
`new LinkedHashMap<>()`	Insertion order (`accessOrder = false`)
`new LinkedHashMap<>(n)`	Capacity hint, still insertion order
`new LinkedHashMap<>(n, loadFactor, accessOrder)`	`true` → recency order; `get` moves to last
`removeEldestEntry(eldest)`	Override; return `true` to drop the list head after a new `put`
`get` / `put` / `remove`	Expected `O(1)` hash lookup; `get` splices only if `accessOrder`
`firstEntry` / `lastEntry` / `reversed`	SequencedMap on Java 21
`keySet` / `values` / `entrySet`	Fail-fast views in encounter order

The lab key is still Order.id or LineItem.sku:

Map<String, LineItem> scanned = new LinkedHashMap<>();
scanned.put("SKU-1", new LineItem("SKU-1", 1, new BigDecimal("4.00")));
scanned.put("SKU-2", new LineItem("SKU-2", 2, new BigDecimal("1.50")));
scanned.put("SKU-1", new LineItem("SKU-1", 3, new BigDecimal("4.00")));

for (String sku : scanned.keySet()) {
    // SKU-1, then SKU-2 — first insert of SKU-1 stays first; put of an
    // existing key updates the value and does not move the node (insertion order)
}

Replacing a value in insertion-order mode does not reshuffle. The key keeps its original place. That is why a packing slip survives a quantity edit.

A checkout walk makes the list visible. Three scans, then a quantity correction on the first SKU:

Map<String, LineItem> slip = new LinkedHashMap<>();
slip.put("SKU-1", new LineItem("SKU-1", 1, new BigDecimal("4.00")));
slip.put("SKU-2", new LineItem("SKU-2", 2, new BigDecimal("1.50")));
slip.put("SKU-3", new LineItem("SKU-3", 1, new BigDecimal("9.00")));
slip.put("SKU-1", new LineItem("SKU-1", 4, new BigDecimal("4.00")));

slip.forEach((sku, item) ->
        System.out.println(sku + " x" + item.quantity()));

SKU-1 x4
SKU-2 x2
SKU-3 x1

SKU-1 stays first. A HashMap would not let you print that promise; a TreeMap would reprint as SKU-1, SKU-2, SKU-3 only because the strings sort that way — add SKU-10 and the tree order diverges from scan order.

Insertion order is the default

The no-arg constructor is accessOrder = false. First put of a key goes to the tail. Iteration is oldest-insert to newest-insert.

Map<String, Order> byId = new LinkedHashMap<>();
byId.put("ORD-1001", a);
byId.put("ORD-1002", b);
byId.put("ORD-1003", c);

List<String> ids = new ArrayList<>(byId.keySet());
// [ORD-1001, ORD-1002, ORD-1003]

HashMap would not promise that list. Tests that assert JSON field order, audit trails, and “print in the order we saw them” are the reason this class exists.

Iteration of n entries is O(n) and follows the list. You do not walk empty bins. That walk is insert order (or access order, below). Yes: iteration is O(n) in insertion order.

Access order: the third constructor argument

Map<String, Order> recent = new LinkedHashMap<>(16, 0.75f, true);

true means access order. get, getOrDefault, and a successful put of an existing key move that entry to the last (most-recent) position. Eldest / first is the least recently used.

recent.put("ORD-1001", a);
recent.put("ORD-1002", b);
recent.put("ORD-1003", c);
recent.get("ORD-1001");          // 1001 moves to last

List<String> ids = new ArrayList<>(recent.keySet());
// [ORD-1002, ORD-1003, ORD-1001]  — 1001 was touched last

Note: containsKey does not move the entry. It is inherited from HashMap and is not an access. A cache that only calls containsKey is not an LRU. get is the access. In access-order mode, get is a structural modification — a fail-fast iterator running on another view of the same map will see it.

Map<String, Order> recent = new LinkedHashMap<>(16, 0.75f, true);
recent.put("ORD-1001", a);
recent.put("ORD-1002", b);
for (String id : recent.keySet()) {
    recent.get("ORD-1001");        // CME — get moved a node
}

The first constructor argument is initial table capacity, not a max size. 0.75f is the same load factor as HashMap. The boolean is the whole policy switch.

removeEldestEntry: an LRU in a subclass

Override one method. After put inserts, if you return true, the eldest entry is removed. In access order, eldest is the least recently used. That is the JDK LRU.

public final class RecentOrders extends LinkedHashMap<String, Order> {
    private final int maxEntries;

    public RecentOrders(int maxEntries) {
        super(maxEntries, 0.75f, true); // accessOrder
        this.maxEntries = maxEntries;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<String, Order> eldest) {
        return size() > maxEntries;
    }
}

RecentOrders cache = new RecentOrders(2);
cache.put("ORD-1001", a);
cache.put("ORD-1002", b);
cache.get("ORD-1001");          // 1001 is MRU; 1002 is eldest
cache.put("ORD-1003", c);       // size 3 → drop 1002
System.out.println(cache.keySet()); // [ORD-1001, ORD-1003]
System.out.println(cache.containsKey("ORD-1002")); // false

That is the whole cache for a single-threaded bound. removeEldestEntry runs after insertion, not after get. Returning true removes eldest. You can inspect eldest.getValue() if eviction needs a listener; the default implementation returns false (never evict).

Capacity in super(maxEntries, …) sizes the hash table so warm-up does not resize immediately. The bound is the size() > maxEntries check. They are not the same number conceptually — one is buckets, one is entries you keep.

Hand-rolled list-plus-HashMap vs this type

The layout post already showed why a list alone cannot find and a map alone cannot rank. The hand-rolled version is two structures you must keep in lockstep:

Map<String, Order> byId = new HashMap<>();
Deque<String> recency = new ArrayDeque<>(); // ids, MRU at the end — easy to desync

void touch(String id, Order order) {
    byId.put(id, order);
    recency.remove(id);          // O(n) unless you also store nodes
    recency.addLast(id);
    if (byId.size() > MAX) {
        String victim = recency.removeFirst();
        byId.remove(victim);
    }
}

recency.remove(id) walks the deque. The real machine stores before / after on the map’s own entry so splice is O(1) once you hold the node. LinkedHashMap is that machine. LRU Cache draws the sentinels and the three pointer edits. Reach for this class unless you are teaching those pointers or you need a hook this type does not have (TTL index, weighted size, stats).

Do not synchronize a LinkedHashMap and call it a concurrent cache. get mutates order. A production shared cache is a different product — same warning as the layout post.

SequencedMap on Java 21

LinkedHashMap implements SequencedMap. First and last follow the encounter list: in insertion order, first is the oldest insert; in access order, first is LRU. The sequenced API — firstEntry, lastEntry, putFirst, putLast, reversed — is Sequenced Collections, not a second copy of that table.

SequencedMap<String, Order> byId = new LinkedHashMap<>();
byId.put("ORD-1001", a);
byId.put("ORD-1002", b);
byId.put("ORD-1003", c);

Map.Entry<String, Order> first = byId.firstEntry(); // ORD-1001
Map.Entry<String, Order> last  = byId.lastEntry();  // ORD-1003
byId.pollFirstEntry();                              // drops 1001

reversed() is a live view. HashMap has none of this: it is not sequenced. TreeMap is sequenced by key sort, which is a different order.

putFirst / putLast reposition an existing key to that end. That is a sequenced write, not “sort this key into place.” Use them when the encounter list is the API; do not use them to fake a TreeMap.

When not to use LinkedHashMap

Skip this class when order is not the requirement, or when the order you want is a different order:

You only look up by id. HashMap is smaller. The extra two pointers never get walked.
You need sorted keys. TreeMap. Insertion order of "ORD-1002" then "ORD-1001" will not become lexicographic order because you picked LinkedHashMap.
Another thread shares the cache. Not this type. get mutates the list. A concurrent cache (Caffeine, or a design with its own segments) is the product; Collections.synchronizedMap serializes every call and still makes get a write under the lock.
LFU or TTL-only. Recency is not frequency, and it is not a wall clock. removeEldestEntry does not know about hit counts or expiry.

Tiny n with a scan on eviction can stay a HashMap. Constant-time splices start to matter when the scan would show up.

Same fail-fast, same threads, slightly more RAM

Map<String, Order> byId = new LinkedHashMap<>();
byId.put(order.id(), order);
byId.put(null, order);                 // still one null key

Writers from two threads are still a bug. Iterators still throw ConcurrentModificationException on a structural change, and in access-order mode get is structural. Empty-bin walks are skipped; you still pay O(n) to visit n entries, just in a meaningful order.

Use LinkedHashMap when that order is the requirement. Use HashMap when it is not — the extra pointers are waste.

vs HashMap and vs TreeMap

	`HashMap`	`LinkedHashMap`	`TreeMap`
Lookup	expected `O(1)`	expected `O(1)`	`O(log n)`
Iteration order	unspecified	insertion or access	sorted keys
Sequenced (21)	no	yes	yes (sorted)
Extra memory	table + nodes	+ `before`/`after`	tree nodes
LRU hook	no	`removeEldestEntry`	no
Null key	one	one	no (natural order)

LinkedHashMap does not sort keys. "ORD-1002" can print before "ORD-1001" if that is the insert (or access) order. Sorted ids are TreeMap and a Comparator, in Navigable Collections.

Interview lens

They want insertion vs access, the ten-line LRU, and a clear “not TreeMap.”

Complexity.

get / put / remove     expected O(1)     same hash table as HashMap
                       plus O(1) splice  when accessOrder moves the entry
iteration              O(n)              in insertion or access order (the list)
removeEldestEntry      O(1)              after put; drops the list head if you ask
space                  O(n)              two extra refs per entry vs HashMap

What to draw. A HashMap table, then a separate doubly linked list through the same entries. Label the list “insertion order” or “MRU at tail, LRU at head.” removeEldestEntry after put cuts the head when size > cap.

bins:    [h("ORD-1002")] -> E1002
         [h("ORD-1001")] -> E1001

list:    head <-> E1002 <-> E1001 <-> tail
         LRU/first           MRU/last     (accessOrder = true)

get(1002)  →  splice E1002 to last
put extra  →  if size > max, remove head (eldest)

Typical questions:

Question	Honest answer
Insertion vs access order?	Default constructor: first `put` of a key wins its place; later `put` of the same key updates the value and stays put. `new LinkedHashMap<>(n, 0.75f, true)`: `get` / re-`put` move the entry to last (MRU).
How is LRU ten lines?	Subclass, `super(cap, 0.75f, true)`, override `removeEldestEntry` to `return size() > max`. Eldest in access order is LRU.
Is iteration `O(n)` in insert order?	Yes. It walks the entry list. That list is insert order (or access order). Not a sort.
vs `HashMap`?	Same expected `O(1)` lookup. Extra pointers, specified encounter order, sequenced on 21. Use HashMap when you do not need the order.
vs `TreeMap`?	TreeMap iterates by sorted keys, `O(log n)` per op, no null key under natural order. LinkedHashMap iterates by insert/access, expected `O(1)` lookup. They answer different questions.
Does `containsKey` refresh LRU?	No. `get` does. `containsKey` is not an access.
Is `get` structural in access order?	Yes. Fail-fast iterators notice. Single-threaded cache, not a shared map.
Why not `List` + `HashMap` by hand?	Easy to desync, and `List.remove(key)` is `O(n)`. This type splices the node the table already found. Layout: LRU Cache.

Wrong answer: “LinkedHashMap sorts keys.” It preserves insertion order (or recency). Sorted keys are TreeMap.

Cheat sheet

Shape          HashMap table + doubly linked list of entries
Default        insertion order (accessOrder = false)
Access order   new LinkedHashMap<>(n, 0.75f, true)
get            moves to last iff accessOrder; containsKey does not
LRU            subclass + removeEldestEntry → size() > max
removeEldest   after put, not after get; eldest = list head
Iteration      O(n) in that encounter order
SequencedMap   Java 21 — firstEntry / lastEntry / reversed
Nulls / CME    same as HashMap; get is structural in access order
Threads        not safe
vs TreeMap     insert/access order, not sorted keys
vs HashMap     pay two refs per entry for a specified order
vs hand-roll   do not keep a List and a HashMap in sync yourself

Do:

Reach for LinkedHashMap when a test or a slip of paper needs first-seen order.
Flip accessOrder and override removeEldestEntry for a single-threaded bounded cache.
Iterate the map and trust the list — that walk is the order.

Don’t:

Use it as a sorted map.
Call containsKey and think you refreshed LRU.
Share it across threads, or treat Collections.synchronizedMap as a concurrent cache.

Wrap-up

LinkedHashMap is the default map plus a doubly linked list that is the encounter order. Leave the boolean false for insertion order. Pass true so get moves an entry to the most-recent end. Override removeEldestEntry and you have a bounded LRU without gluing a List to a HashMap. Slightly more memory than HashMap, same nulls, same fail-fast, still not for two threads. It does not sort keys.

When the job is “next best,” not “keep this sequence,” you want a heap, not a linked hash map.

Next optional step in the series When the job is next-best, not a full sort. PriorityQueue: Next-Best Without Sorting the Whole List

LinkedHashMap:Insertion Order, Access Order, and a Real LRU

HashMap plus a list of entries

Insertion order is the default

Access order: the third constructor argument

removeEldestEntry: an LRU in a subclass

Hand-rolled list-plus-HashMap vs this type

SequencedMap on Java 21

When not to use LinkedHashMap

Same fail-fast, same threads, slightly more RAM

vs HashMap and vs TreeMap

Interview lens

Cheat sheet

Wrap-up

Pick the Collection:Nulls, Order, Threads, and the Hot Operation

Sequenced Collections:First, Last, and Reversed Without the Ceremony

Stream Gatherers:Custom Intermediate Ops Without Breaking the Pipeline

Java Streams:Filter, Map, and Collect Without the Nested Loop Soup

HashMap plus a list of entries

Insertion order is the default

Access order: the third constructor argument

removeEldestEntry: an LRU in a subclass

Hand-rolled list-plus-HashMap vs this type

SequencedMap on Java 21

When not to use LinkedHashMap

Same fail-fast, same threads, slightly more RAM

vs HashMap and vs TreeMap

Interview lens

Cheat sheet

Wrap-up

Related posts

Pick the Collection:Nulls, Order, Threads, and the Hot Operation

Sequenced Collections:First, Last, and Reversed Without the Ceremony

Stream Gatherers:Custom Intermediate Ops Without Breaking the Pipeline

Java Streams:Filter, Map, and Collect Without the Nested Loop Soup