LinkedHashMap源码解析：从双向链表到LRU缓存实现-平芜编程栈

说到 LinkedHashMap，很多人的第一反应是“不就是 HashMap 加了个链表嘛”，但真让你讲讲它底层怎么维护顺序、怎么实现 LRU 缓存、为什么迭代顺序能稳定不变，估计不少人会卡壳。这篇就从 JDK 源码层面把 LinkedHashMap 剥开揉碎，从结构设计、回调钩子、迭代器实现到 LRU 实战手写，一条线串下来，看完你不仅能应付面试，还能在项目里放心用它做缓存淘汰。

1. LinkedHashMap 的结构设计：到底在 HashMap 之上加了什么

1.1 继承关系与新增字段

LinkedHashMap 的类声明很简单：

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

关键不是它继承了 HashMap，而是它利用 HashMap 预留的扩展点，在不动 HashMap 核心逻辑的前提下，叠加了一条双向链表。这条链表是干什么用的？一句话：记录节点的插入顺序或访问顺序。HashMap 本身是无序的，因为元素存到数组里之后，位置由hash & (n-1)决定，跟插入顺序没关系。而 LinkedHashMap 在每次 put、get 成功之后，都把对应节点“串”到一条双向链表上，遍历的时候沿着链表走，顺序就固定下来了。

字段只有三个：

transient LinkedHashMap.Entry<K,V> head; transient LinkedHashMap.Entry<K,V> tail; final boolean accessOrder;

head和tail分别是双向链表的头尾节点，accessOrder决定链表维护的是“插入顺序”还是“访问顺序”。默认是false，也就是插入顺序；构造时传true，就能实现 LRU 那种“最近访问的排到尾部”的效果。

节点结构也和 HashMap 的 Node 不同：

static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } }

注意Entry继承了HashMap.Node，也就是说它在原来next单链表指针的基础上，多了before和after两个指针，用来串成双向链表。next还是用来解决哈希冲突的，before/after纯粹用来记录顺序，两者互不干扰。

这里有个新手容易混淆的点：LinkedHashMap 的节点可以同时存在于两条“链”上。一条是哈希桶里的单链表（或者红黑树），负责快速查找；另一条是贯穿所有节点的双向链表，负责顺序遍历。你可以把它想象成一张表既有“按姓名索引”的目录，又有“按时间排序”的流水账，各干各的活。

1.2 模板方法模式：HashMap 留给子类的三个钩子

先说一个很多人忽略的细节：HashMap 源码里其实有三个空方法，LinkedHashMap 的整个顺序逻辑全靠覆写它们来实现。这三个方法在 HashMap 中长这样：

// Callbacks to allow LinkedHashMap post-actions void afterNodeAccess(Node<K,V> p) { } void afterNodeInsertion(boolean evict) { } void afterNodeRemoval(Node<K,V> p) { }

名字里的after说明它们都是在操作完成之后被回调的。HashMap 内部实现并不关心这三个方法做什么，它只负责在合适的时机调用。这就是典型的模板方法模式：父类定义流程框架，子类通过覆写钩子方法改变局部行为。

LinkedHashMap 重写这三个钩子后，在节点被访问、插入、删除时，同步维护双向链表结构。这也是为什么 LinkedHashMap 的 put、get 逻辑能和 HashMap 完全复用——它不需要改动 HashMap 的哈希逻辑，只需要在“操作完成后”补一刀，把链表关系理顺。

2. 三个核心钩子方法源码逐行拆解

2.1 afterNodeAccess：把节点移动到链表尾部

这个方法在get或者put覆盖已有 key 时会被调用。如果accessOrder为false，它什么都不做；如果为true，就把访问到的节点移动到链表的tail。源码如下：

void afterNodeAccess(Node<K,V> e) { LinkedHashMap.Entry<K,V> last; if (accessOrder && (last = tail) != e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>) e, b = p.before, a = p.after; p.after = null; if (b == null) head = a; else b.after = a; if (a != null) a.before = b; else last = b; if (last == null) head = p; else { p.before = last; last.after = p; } tail = p; ++modCount; } }

拆开来看：

第一步判断accessOrder && tail != e，意思是只有开启了访问顺序模式，并且这个节点不是尾节点时，才有必要移动。
第二步把节点p从链表中断开。b是前驱，a是后继，把b.after直接指向a，同时a.before指回b。如果p是头节点，那head就要换成a。
第三步把p接到链表末尾。注意这里用last变量接住了断开前链表的尾节点，然后p.before = last; last.after = p; tail = p;完成尾插。

之所以要多一个last去接“断开后的尾部”，是因为节点可能原本就在尾部，只是被我们手动断开了，中间状态不能丢。

2.2 afterNodeInsertion：插入新节点后的回调

这个方法是 LRU 能实现的另一个关键。源码：

void afterNodeInsertion(boolean evict) { LinkedHashMap.Entry<K,V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } }

evict是“是否允许驱逐”的标志，在 HashMap 的 putVal 里，插入新节点后调用的是afterNodeInsertion(evict)，而这个evict参数来自 put 的入参，普通调用都是true。

真正干活的条件是removeEldestEntry(first)：

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; }

这又是一个钩子，默认返回false，表示永远不移除最老的节点。但你要是想实现 LRU，覆写这个方法，让它返回size() > MAX_SIZE，那么每次插入新元素后，如果容量超了，就会把链表的头节点（也就是最久没被访问的节点）删掉。

我在实际项目中就手写过这样一个 LRU 缓存，核心就两行：

LinkedHashMap<String, Object> cache = new LinkedHashMap<String, Object>(16, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry<String, Object> eldest) { return size() > 100; } };

这一段代码比任何理论讲解都有说服力。accessOrder = true让每次get都把节点移到尾部；removeEldestEntry保证容量超出 100 时自动淘汰头节点。一个线程不安全的简易 LRU 缓存就这么完成了。

2.3 afterNodeRemoval：删除节点后修正链表指针

这个方法和 HashMap 的 removeNode 配对，删除节点后把双向链表中的节点摘除：

void afterNodeRemoval(Node<K,V> e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>) e, b = p.before, a = p.after; p.before = p.after = null; if (b == null) head = a; else b.after = a; if (a == null) tail = b; else a.before = b; }

代码很直接：把p的前后指针都置空（方便 GC），然后让前驱的after指向后继，后继的before指向前驱。如果删的是头节点，就更新head；删的是尾节点，就更新tail。这个操作的时间复杂度是 O(1)，比 ArrayList 删除元素后还要移动后续元素快得多。

3. 插入顺序 vs 访问顺序：两种模式的区别与理解

3.1 插入顺序模式：稳定的迭代顺序

当accessOrder = false时，LinkedHashMap 的行为最接近普通人的直觉：你 put 了哪些 key，遍历的时候就按 put 的顺序出来。但这里有个细节：用 put 覆盖已有 key 时，不会改变这个 key 的链表位置。

举个例子：

Map<String, Integer> map = new LinkedHashMap<>(); map.put("A", 1); map.put("B", 2); map.put("C", 3); map.put("A", 100); // 遍历顺序：A, B, C

A 虽然被重新 put 了一次，但它仍然在链表的最前面。为什么？因为在putVal中，如果找到相同 key，只需要替换 value，然后调用afterNodeAccess(e)。而accessOrder为false时，afterNodeAccess什么都不做，所以节点位置不变。

更细一步说，删除节点再重新 put 同一个 key，它就会被放到尾部：

map.remove("B"); map.put("B", 200); // 遍历顺序：A, C, B

因为先删除，链表里 B 已经被摘除；再插入，走的是新节点插入逻辑linkNodeLast，自然被放到尾部。这个差别很多人在实际编码时会踩坑，尤其是拿 LinkedHashMap 做“按最近插入排序”的列表时，容易出现“覆盖没上移，删除再插入却上移”的怪异行为。

3.2 访问顺序模式：为 LRU 而生

当accessOrder = true时，每次get或者put命中已有 key，都会把节点移动到链表尾部。头部自然就成了“最久没被访问”的节点。这个设计完美契合 LRU（Least Recently Used）淘汰算法：最近用过的靠后，最久没用过的靠前，容量不够就从头删。

我之前测试过一个典型场景：

LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(4, 0.75f, true); map.put(1, 10); map.put(2, 20); map.put(3, 30); map.get(1); // 访问 1，1 被移到尾部 map.put(4, 40); // 长度 4, 再插入新节点会触发淘汰 // 此时 head 是 2，因为 1 被访问过挪走了

这里有个有意思的点：初始容量设成 4，但实际存储的元素还是 4 个，不是 5 个。removeEldestEntry判断的是size() > 4，所以插入第 5 个时才会淘汰最老的，容量上限实际是 4。如果你想让初始容量和最大容量一致，算准了就行，不用特意扩大。

3.3 扩容（resize）时的链表保持

LinkedHashMap 扩容时复用 HashMap 的 resize 逻辑，但有个细节需要注意：HashMap 在扩容时会把旧桶中的节点分成“低位链表”和“高位链表”，然后重新散列。对 LinkedHashMap 来说，这个过程中节点的 before/after 关系不会被打乱，只是节点在哈希桶数组中的位置变了，双向链表的整体顺序保持不变。

这也意味着：即使经历了多次扩容，只要你没有删除再插入节点，LinkedHashMap 的遍历顺序始终是稳定的。这在实际业务中很有用，尤其是做数据导出、报表统计时，用一个 LinkedHashMap 接住数据库查询结果，顺序就是插入顺序，不会因为中间哈希变化而乱掉。

4. 迭代器机制：为什么 LinkedHashMap 的迭代顺序稳定

4.1 迭代器源码实现

LinkedHashMap 的迭代器是在LinkedHashIterator基础上完成的。这个迭代器和 HashMap 的迭代器最大的区别是：HashMap 的迭代器需要遍历哈希桶数组，再顺着桶内的链表逐个访问，而 LinkedHashMap 的迭代器只沿着head到tail的双向链表走，完全不关心桶数组：

abstract class LinkedHashIterator { LinkedHashMap.Entry<K,V> next; LinkedHashMap.Entry<K,V> current; int expectedModCount; LinkedHashIterator() { next = head; expectedModCount = modCount; current = null; } public final boolean hasNext() { return next != null; } final LinkedHashMap.Entry<K,V> nextNode() { LinkedHashMap.Entry<K,V> e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); current = e; next = e.after; return e; } public final void remove() { Node<K,V> p = current; if (p == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); current = null; removeNode(p.hash, p.key, null, false, false); expectedModCount = modCount; } }

核心就是next = e.after，直接拿当前节点的后继作为下一次要返回的节点。这也是为什么 LinkedHashMap 的迭代在集合元素多、哈希冲突严重时，性能比 HashMap 更稳定——不管桶数组怎么乱，链表顺序从头走到尾就完了，不需要在某个桶里浪费太多时间。

expectedModCount是快速失败机制的体现。所有会改变链表结构的操作（put、get 命中、remove）都会++modCount（注意，accessOrder = true时，get 操作也会自增 modCount）。迭代过程中如果检测到 modCount 变了，会立刻抛出ConcurrentModificationException，防止迭代器拿到不一致的数据。这个机制是保证安全性的，不是 bug，别试图关掉它。

4.2 keySet、values、entrySet 的视图迭代

LinkedHashMap 的keySet()、values()和entrySet()方法返回的视图，迭代时走的是同一个LinkedHashIterator。这带来一个额外好处：迭代集合类视图时的顺序永远一致，不会出现 keySet 的顺序和 entrySet 的顺序对不上的情况。

实际编码中，这个特性经常被忽略但很好用。比如前端配合后端返回一个“固定顺序”的字段列表，用 LinkedHashMap 存字段键值对，再用keySet()去遍历，顺序永远是后端塞进去的顺序。HashMap 做不到这一点，TreeMap 虽然有序但又要你实现比较器，而且它是按 key 排序不是按插入排序。

5. LRU 缓存手写实战：从理论到落地

5.1 一个可复用的 LRU 缓存类

直接上代码，这是我项目里用的一个简化版本：

import java.util.LinkedHashMap; import java.util.Map; public class LRUCache<K, V> extends LinkedHashMap<K, V> { private final int maxCapacity; public LRUCache(int maxCapacity) { // 初始容量、负载因子、accessOrder=true super(maxCapacity, 0.75f, true); this.maxCapacity = maxCapacity; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxCapacity; } }

使用示例：

LRUCache<Integer, String> cache = new LRUCache<>(3); cache.put(1, "A"); cache.put(2, "B"); cache.put(3, "C"); System.out.println(cache.keySet()); // [1, 2, 3] cache.get(1); // 访问 1，1 移到尾部 System.out.println(cache.keySet()); // [2, 3, 1] cache.put(4, "D"); // 容量超标，淘汰头节点 2 System.out.println(cache.keySet()); // [3, 1, 4]

这个类就完成了 LRU 缓存的核心功能。如果你需要线程安全，加一把锁或者用Collections.synchronizedMap包一下；如果你需要自动过期，再加一个定时清理线程即可。

5.2 性能权衡：不是所有场景都适合 LinkedHashMap

很多文章把 LinkedHashMap 吹得很神，但实际使用时要清楚它的代价。相比 HashMap，LinkedHashMap 每个节点多了before和after两个引用，内存占用更高。这一点在大量缓存对象时尤其明显——如果缓存的是大对象，节点引用开销可能微不足道；但如果缓存的是 Integer 这种小对象，额外的两个指针可能会让内存膨胀不少。

另外，accessOrder = true模式下，每次get或put命中都需要做一次链表摘除和尾插操作。虽然都是 O(1)，但多了一次指针操作和一次modCount++，在高并发、高频读取的场景下，锁竞争和指针操作的开销还是需要评估的。简单说：读多写少且数据量小的场景用 LinkedHashMap 很舒服，数据量动辄几十万甚至上百万，又想严格限制容量，建议专门评估一下缓存组件。

5.3 替代方案选型

我在项目中遇到过缓存需求时，会先问三个问题：

缓存的数据最大能到多少条？
读的频率高还是写的频率高？
需要线程安全吗？

如果数据量几千到几万，读写均衡，可以无脑用 LinkedHashMap。如果数据量大、并发高，优先考虑自带淘汰策略的缓存框架或者队列方案。LinkedHashMap 最大的价值是让你理解 LRU 的本质，而工程上它最适合轻量级场景，别硬塞到重负载系统里。

6. 易错点与排查经验

6.1 构造方法里 accessOrder 没生效

最常见的坑是把accessOrder理解成“按访问次数排序”。它其实只维护“最近一次被访问”这个信息——访问一个节点，它就被移到尾部，后边的节点前移一位，但不会记录累加访问次数。所以如果你需要“访问次数最多的排最前面”，LinkedHashMap 干不了这活，你得自己维护计数器并用别的容器排序，或者用序列化方案自己控制。

6.2 覆写 removeEldestEntry 时别用 ==

下面这个写法很容易出现在新手教程里，但有问题：

protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxCapacity; // OK }

有问题的写法是：

protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() == maxCapacity + 1; // 逻辑容易出偏差 }

因为size()是实时变化的，如果先插入一批元素再批量删除，判断条件可能无法准确反映“容量是否超限”。最稳妥的写法就是size() > maxCapacity，简单直观，也不会因为边界条件踩坑。

6.3 序列化顺序一致性

LinkedHashMap 默认通过writeObject和readObject实现序列化。它的序列化逻辑是把双向链表从头到尾全部写出去，反序列化时再按顺序插回去。所以序列化前后遍历顺序能保持一致。但你如果自定义了序列化方式，比如只序列化字段数组，那就得自己保证顺序恢复，否则顺序就丢了。

我之前处理过一个线上数据导出问题：从 Redis 里取回的数据本身是无序的，我用 LinkedHashMap 手动维护插入顺序，导出时数据顺序正确，但第二天系统升级后，某同学改成先序列化到 JSON 再反序列化回内存，结果导出顺序乱掉。查了半天才发现，JSON 反序列化并不会自动恢复 LinkedHashMap 的链表顺序，除非你用的是专门的类型信息保留方案。

6.4 并发环境下的安全隐患

LinkedHashMap 非线程安全。它的链表指针更新不是原子的，两个线程同时写同一个 LinkedHashMap，轻则数据错乱，重则链表成环、死循环、CPU 飙升。最典型的场景是：多个线程同时 put 不同的 key，恰好触发了扩容，两个线程都在 resize，链表指针被反复改写，最终可能导致 JVM 直接卡死。

解决办法有三条路：

全程加锁，最简单，但并发性能一般。
用Collections.synchronizedMap(new LinkedHashMap<>())，适合读写比较均衡的场景。
用支持并发的ConcurrentHashMap替代，但要牺牲顺序特性。如果你的业务需要 LRU 又需要高并发，建议直接用一个线程安全的缓存框架，而不是自己硬造轮子。

6.5 遍历时删除

迭代器方法remove()是安全删除的唯一方式。如果你在for-each循环里直接调用map.remove(key)，因为此时走的是 iterator 的快速失败机制，modCount不一致，会立刻抛出ConcurrentModificationException。

正确写法是：

Iterator<Integer> iterator = cache.keySet().iterator(); while (iterator.hasNext()) { Integer key = iterator.next(); if (key % 2 == 0) { iterator.remove(); // 安全，内部会更新 expectedModCount } }

或者干脆不迭代，先记录要删除的 key，最后统一用removeAll或removeIf一次性处理。

6.6 初始容量为什么常常要加一

如果你用accessOrder = true实现 LRU，且构造时容量参数等于你所期望的最大容量，那么注意：LinkedHashMap 的初始容量不是“最大容量”，它和 HashMap 一样是桶数组的长度，扩容阈值是容量乘以负载因子。比如new LinkedHashMap<>(4, 0.75f, true)，桶数组长度为 4，扩容阈值是4 * 0.75 = 3，所以你存到第 4 个元素时就可能触发扩容。

这本身不影响 removeEldestEntry 的逻辑（它判断的是 size()），但在性能和内存上不友好。如果要精确控制最大容量并避免频繁扩容，建议初始容量设置为maxCapacity / 0.75f + 1，或者直接用一个较大的初始容量。很多网上教程里的 LRU 示例直接写new LinkedHashMap<>(4, 0.75f, true)，实际跑起来扩展会比你想象的早。

7. 最后分享一个实用技巧

个人实际踩过不少坑之后，我最常用的一条经验是：如果你只是需要一个“保持插入顺序”的 Map，别自己去维护一个 List 加一个 HashMap 的组合，直接上 LinkedHashMap 就完事了。

我之前做导出功能时，就试过用HashMap + ArrayList来记录字段插入顺序：往 Map 里放数据的同时往 List 里 add 一次 key，导出时遍历 List 再查 Map。结果是：业务逻辑里每新增一个字段，就要改两处调用，稍不留神 List 和 Map 就对不上；删除字段时要同步从 List 里移除，代码又臭又长。后来换成 LinkedHashMap，插入、遍历的顺序天然一致，删除也叫remove就自动把链表节点摘掉了，再也不用手动同步。

如果你后续要继续深挖，我建议你去看看 Caffeine 缓存框架的源码，它的淘汰策略本质上比 LinkedHashMap 复杂得多，但核心的“顺序统计树”和“窗口 LRU”思想，和你现在理解的 LinkedHashMap 是相通的。理解了 LinkedHashMap，你就已经迈过了 Java 集合框架最深的一道坎之一，后面再看其他 Map 实现都会轻松很多。