★ FEATURED ARTICLE 说到 LinkedHashMap很多人的第一反应是“不就是 HashMap 加了个链表嘛”但真让你讲讲它底层怎么维护顺序、怎么实现 LRU 缓存、为什么迭代顺序能稳定不变估计不少人会卡壳。这篇就从 JDK 源码层面把 LinkedHashMap 剥开揉碎从结构设计、回调钩子、迭代器实现到 LRU 实战手写一条线串下来看完你不仅能应付面试还能在项目里放心用它做缓存淘汰。1. LinkedHashMap 的结构设计到底在 HashMap 之上加了什么1.1 继承关系与新增字段LinkedHashMap 的类声明很简单public class LinkedHashMapK,V extends HashMapK,V implements MapK,V关键不是它继承了 HashMap而是它利用 HashMap 预留的扩展点在不动 HashMap 核心逻辑的前提下叠加了一条双向链表。这条链表是干什么用的一句话记录节点的插入顺序或访问顺序。HashMap 本身是无序的因为元素存到数组里之后位置由hash (n-1)决定跟插入顺序没关系。而 LinkedHashMap 在每次 put、get 成功之后都把对应节点“串”到一条双向链表上遍历的时候沿着链表走顺序就固定下来了。字段只有三个transient LinkedHashMap.EntryK,V head; transient LinkedHashMap.EntryK,V tail; final boolean accessOrder;head和tail分别是双向链表的头尾节点accessOrder决定链表维护的是“插入顺序”还是“访问顺序”。默认是false也就是插入顺序构造时传true就能实现 LRU 那种“最近访问的排到尾部”的效果。节点结构也和 HashMap 的 Node 不同static class EntryK,V extends HashMap.NodeK,V { EntryK,V before, after; Entry(int hash, K key, V value, NodeK,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(NodeK,V p) { } void afterNodeInsertion(boolean evict) { } void afterNodeRemoval(NodeK,V p) { }名字里的after说明它们都是在操作完成之后被回调的。HashMap 内部实现并不关心这三个方法做什么它只负责在合适的时机调用。这就是典型的模板方法模式父类定义流程框架子类通过覆写钩子方法改变局部行为。LinkedHashMap 重写这三个钩子后在节点被访问、插入、删除时同步维护双向链表结构。这也是为什么 LinkedHashMap 的 put、get 逻辑能和 HashMap 完全复用——它不需要改动 HashMap 的哈希逻辑只需要在“操作完成后”补一刀把链表关系理顺。2. 三个核心钩子方法源码逐行拆解2.1 afterNodeAccess把节点移动到链表尾部这个方法在get或者put覆盖已有 key 时会被调用。如果accessOrder为false它什么都不做如果为true就把访问到的节点移动到链表的tail。源码如下void afterNodeAccess(NodeK,V e) { LinkedHashMap.EntryK,V last; if (accessOrder (last tail) ! e) { LinkedHashMap.EntryK,V p (LinkedHashMap.EntryK,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.EntryK,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.EntryK,V eldest) { return false; }这又是一个钩子默认返回false表示永远不移除最老的节点。但你要是想实现 LRU覆写这个方法让它返回size() MAX_SIZE那么每次插入新元素后如果容量超了就会把链表的头节点也就是最久没被访问的节点删掉。我在实际项目中就手写过这样一个 LRU 缓存核心就两行LinkedHashMapString, Object cache new LinkedHashMapString, Object(16, 0.75f, true) { Override protected boolean removeEldestEntry(Map.EntryString, Object eldest) { return size() 100; } };这一段代码比任何理论讲解都有说服力。accessOrder true让每次get都把节点移到尾部removeEldestEntry保证容量超出 100 时自动淘汰头节点。一个线程不安全的简易 LRU 缓存就这么完成了。2.3 afterNodeRemoval删除节点后修正链表指针这个方法和 HashMap 的 removeNode 配对删除节点后把双向链表中的节点摘除void afterNodeRemoval(NodeK,V e) { LinkedHashMap.EntryK,V p (LinkedHashMap.EntryK,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 的链表位置。举个例子MapString, Integer map new LinkedHashMap(); map.put(A, 1); map.put(B, 2); map.put(C, 3); map.put(A, 100); // 遍历顺序A, B, CA 虽然被重新 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都会把节点移动到链表尾部。头部自然就成了“最久没被访问”的节点。这个设计完美契合 LRULeast Recently Used淘汰算法最近用过的靠后最久没用过的靠前容量不够就从头删。我之前测试过一个典型场景LinkedHashMapInteger, Integer map new LinkedHashMap(4, 0.75f, true); map.put(1, 10); map.put(2, 20); map.put(3, 30); map.get(1); // 访问 11 被移到尾部 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.EntryK,V next; LinkedHashMap.EntryK,V current; int expectedModCount; LinkedHashIterator() { next head; expectedModCount modCount; current null; } public final boolean hasNext() { return next ! null; } final LinkedHashMap.EntryK,V nextNode() { LinkedHashMap.EntryK,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() { NodeK,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 LRUCacheK, V extends LinkedHashMapK, V { private final int maxCapacity; public LRUCache(int maxCapacity) { // 初始容量、负载因子、accessOrdertrue super(maxCapacity, 0.75f, true); this.maxCapacity maxCapacity; } Override protected boolean removeEldestEntry(Map.EntryK, V eldest) { return size() maxCapacity; } }使用示例LRUCacheInteger, 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); // 访问 11 移到尾部 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 吹得很神但实际使用时要清楚它的代价。相比 HashMapLinkedHashMap 每个节点多了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.EntryK, V eldest) { return size() maxCapacity; // OK }有问题的写法是protected boolean removeEldestEntry(Map.EntryK, 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。正确写法是IteratorInteger 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 实现都会轻松很多。
阅读完成 · 觉得有帮助？
