How does LinkedHashMap work internally: what does its Entry add to HashMap's Node, and what do the afterNode hooks do?
answer
- one node, two kinds of link
- a subclass of the bin node
- methods HashMap calls on itself
- who links, who moves, who evicts
- the mode flag guards the move
basics
~20 sLinkedHashMap is a HashMap whose nodes also carry before and after links, threading all entries into one doubly-linked list. Overridden package-private methods maintain it: newNode and newTreeNode link, afterNodeAccess moves, afterNodeInsertion may evict, afterNodeRemoval unlinks.
solid answer
~40 s`LinkedHashMap` extends `HashMap` and keeps its table for lookups, while iteration follows a doubly-linked list running through every entry. The package-private `Entry` extends `HashMap.Node` and adds `before` and `after`, and the map holds `head` and `tail`. `HashMap` never touches those links itself: it creates nodes through overridable package-private methods, so `newNode` or `newTreeNode` links a new entry at the tail, and `transferLinks` carries the links across when a bin converts to or from a tree. Of the hooks, `afterNodeRemoval` unlinks, `afterNodeInsertion` offers the eldest entry to `removeEldestEntry`, and `afterNodeAccess` moves an entry to the tail in access-order mode, which makes `get` a structural modification there. In insertion-order mode a `get` or a re-`put` leaves the list alone.
code
java · 19 linesimport java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class ListOrder {
public static void main(String[] args) {
Map<String, Integer> insertion = new LinkedHashMap<>();
Map<String, Integer> access = new LinkedHashMap<>(16, 0.75f, true);
for (Map<String, Integer> map : List.of(insertion, access)) {
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);
map.get("a");
map.put("b", 20);
map.containsKey("c");
System.out.println(map.keySet());
}
}
}go deeper
Recall the picture: a LinkedHashMap is a HashMap plus a doubly-linked list through all its entries, and that list sets the iteration order.
Explain the before and after fields, how newNode links at the tail, and what each afterNode hook does in insertion-order and in access-order mode.
Show the production consequence: in access-order mode a read rewrites links and bumps modCount, so reads need the same exclusive lock as writes and can break a running iterator.
Weigh the design: extending HashMap through package-private hooks keeps one table implementation, at the price of unused link fields on plain tree nodes and a coupling the source itself says complicates tree transitions.
## Two structures over one set of nodes `LinkedHashMap` extends `HashMap`, so it keeps the same hash table for lookups: `get` finds a node through `HashMap`'s `getNode`. A table slot is a **bin**, holding the nodes whose hash maps to it. On top of the table, a **doubly-linked list** runs through every entry and defines the **encounter order**, the order iteration sees. Each entry sits in both structures at once. Forward iterators start at the `head` field and follow `after`, and the reversed views since Java 21 start at `tail` and follow `before`, which is why iterating takes time proportional to the map's size, regardless of its capacity. The source quoted here is JDK 27, and `LinkedHashMap.java` is byte-identical at JDK 25. ## What Entry adds to Node `HashMap.Node` holds `hash`, `key`, `value` and `next`. The package-private subclass adds two references: ```java static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; // constructor omitted } ``` | Field | Declared on | Job | |---|---|---| | `next` | `HashMap.Node` | Chains nodes within one bin | | `before`, `after` | `LinkedHashMap.Entry` | Thread every entry into encounter order | | `head`, `tail` | `LinkedHashMap` | Point at the eldest and the youngest entry | | `accessOrder` | `LinkedHashMap` | `true` for access order, `false` for insertion order | The two kinds of link are independent: neighbours in a bin can sit far apart in the list. `HashMap.TreeNode`, the node of a tree bin, extends `LinkedHashMap.Entry` too, so one tree class works in either map, and `HashMap`'s own code never touches `before` or `after`. ## How the links stay in step with the table `HashMap` creates and swaps nodes through package-private methods that `LinkedHashMap` overrides: - **`newNode`, `newTreeNode`** build the node and call the private `linkNodeAtEnd`, which links it at the tail, or at the head during `putFirst`. - **`replacementTreeNode`, `replacementNode`** run when a bin converts to a tree or back. Each builds a node of the other type and calls the private `transferLinks`, so the neighbours point at the replacement and the list position is kept. Two other paths need less: - **`resize()`** is final, so `LinkedHashMap` does not override it, and it has no need to: it moves the same node objects between plain bins by rewriting `next`, leaving `before` and `after` alone. - **`clear()` and `reinitialize()`** are overridden to reset `head` and `tail` to `null` as well. `clear()` is public, `reinitialize()` is package-private, and neither creates or swaps a node. Put twelve same-hash keys in one bin on JDK 27. It becomes a `TreeNode` bin, then a plain `Entry` bin after removals, and iteration order holds throughout. Once the table exists, inserting a new key with `put` runs in a fixed order inside `putVal`: 1. `newNode`, or `newTreeNode` in a tree bin, creates the entry and links it into the list, and the result goes into the bin. 2. If a plain bin was already crowded, `treeifyBin` runs. 3. If `size` passes `threshold`, `resize()` runs. 4. `afterNodeInsertion(evict)` runs. ## The three afterNode hooks `HashMap` declares these as empty package-private methods, under the comment "Callbacks to allow LinkedHashMap post-actions". None of them links a new entry, because `newNode` or `newTreeNode` already did. | Hook | Called from | What `LinkedHashMap` does | |---|---|---| | `afterNodeAccess(e)` | `put`, `replace`, `merge` and the compute family on an existing key; `get` and `getOrDefault` in access order | Moves `e` if the mode says so | | `afterNodeInsertion(evict)` | `put` and friends after adding a new key | If `evict` is true, offers `head` to `removeEldestEntry` and removes it on `true` | | `afterNodeRemoval(e)` | `removeNode` | Unlinks `e` from the list | ## Insertion order against access order - **Insertion order, the default.** `get` does not call the hook. `put` on an existing key does, but with `accessOrder` false and no positioning call running, nothing moves, so re-inserting a key leaves it where it was. - **Access order.** The three-argument constructor with `true` selects it. Unless the entry is already the tail, `afterNodeAccess` moves it there and increments `modCount`, the counter iterators compare to detect changes. So the head is the least recently accessed entry, the documentation calls `get` a structural modification in this mode, and a running iterator can throw `ConcurrentModificationException`. - **What is not an access.** `containsKey` and operations on the collection views generate none. - **Explicit moves.** `putFirst` and `putLast`, since Java 21, set a package-private `putMode` field around `put`, and `afterNodeAccess` reads it to relocate an existing key in either mode. - **Eviction.** `evict` is false in the copy constructor, `clone` and deserialization, so those never call `removeEldestEntry`. `put`, `putAll` and the compute family pass true. The contract of `removeEldestEntry` and the LRU cache recipe built on it are topics of their own.
- Why can a get on an access-order LinkedHashMap sometimes leave a running iterator working?afterNodeAccess moves an entry and increments modCount only when that entry is not already the tail, so getting the current tail changes nothing. A get during the last pass also goes unnoticed, because no further nextNode call happens. The documentation still treats get as a structural modification in this mode, so rely on neither.
- Why does LinkedHashMap's copy constructor never trigger removeEldestEntry?The constructor calls putMapEntries with evict set to false, and afterNodeInsertion checks evict before anything else. clone and deserialization pass false as well. putAll passes true, so a subclass capped at two entries holds all three after the copy constructor but only two after putAll on JDK 27.
- Why does HashMap's internal TreeNode extend LinkedHashMap.Entry rather than HashMap.Node directly?The source says this lets a tree node serve as an extension of either a regular or a linked node. One tree class then works in both maps, and a LinkedHashMap bin can convert without losing its list position. In a plain HashMap the two inherited links go unused on tree nodes.
- LinkedHashMap replaces HashMap's table with a linked list, so get walks that list.
- The before and after links chain the entries within a single bucket.
- afterNodeAccess moves entries on every get and put, in insertion-order mode as well.
- Treeifying a bin loses insertion order because tree nodes have no list links.
- A resize rebuilds the doubly-linked list by re-inserting every entry.
- afterNodeInsertion is the method that appends a new entry to the list.
- LinkedHashMap
- Java 1.4
- LinkedHashMap afterNode hooks and tree bins
- Java 1.8
- LinkedHashMap.putFirst and putLast
- Java 21
Assumes JDK 27; LinkedHashMap.java is byte-identical at JDK 25, and putFirst and putLast, which the access hook also serves, are since Java 21.
context
- LinkedHashMap (Java SE 27 & JDK 27)docs.oracle.com
- LinkedHashMap.java at jdk-27-gagithub.com