手写LRU Cache：LinkedHashMap的accessOrder模式与源码
2026/4/30大约 11 分钟
手写LRU Cache：LinkedHashMap的accessOrder模式与源码
适读人群：Java后端开发，准备面试或系统设计的同学 | 阅读时长：约16分钟 | 文章类型：源码解析+手写实现
开篇故事
LRU Cache可能是面试里出现频率最高的手写题之一。我面试过的人里，大概有60%听说过可以用LinkedHashMap实现，但真正能说清楚为什么的，不到20%。
有次面试一个工作三年的开发，小刘，我让他手写LRU。他很快写出来了：
// 他的答案
class LRUCache extends LinkedHashMap<Integer, Integer> {
private int capacity;
LRUCache(int capacity) {
super(capacity, 0.75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}我说：不错，但你知道super(capacity, 0.75f, true)这个true是什么意思吗？
他说：开启访问顺序模式。
我说：那底层是怎么实现的？访问一个元素之后，它怎么跑到链表尾部的？
他开始想，想了一会儿，说：可能是把节点删掉再插入？
我说：差不多对，但源码里有个细节，是直接在双向链表里移动节点，不删除。你能把这个移动逻辑的时间复杂度告诉我吗？
沉默。
其实这一步是O(1)，因为双向链表的节点移动只需要改几个指针，不需要遍历。LinkedHashMap选择双向链表而不是单向链表，就是为了让这个操作高效。
今天我们就把LinkedHashMap的accessOrder模式从源码层面搞清楚，然后手写一个线程安全的生产级LRU Cache。
一、LinkedHashMap与HashMap的关系
LinkedHashMap继承HashMap，在HashMap的桶+链表/红黑树结构之上，额外维护了一条贯穿所有节点的双向链表。
这条链表记录了节点的插入顺序（或访问顺序，取决于accessOrder参数）。
LinkedHashMap.Entry在HashMap.Node的基础上增加了before和after两个指针，形成双向链表。这就是为什么LinkedHashMap比HashMap多占一点内存。
二、accessOrder模式的源码实现
2.1 afterNodeAccess：访问后移到链表尾部
package com.laozhang.cache;
import java.util.LinkedHashMap;
import java.util.Map;
/**
* LinkedHashMap accessOrder模式的核心源码解析（JDK11）
*
* accessOrder=false（默认）：按插入顺序，最早插入的在链表头部
* accessOrder=true：按访问顺序，最近访问的在链表尾部（LRU的核心）
*/
public class LinkedHashMapSourceAnalysis {
/**
* afterNodeAccess：每次get/put操作后被回调（仅当accessOrder=true时生效）
* 作用：把刚访问的节点移到双向链表的尾部（表示"最近使用"）
*
* 时间复杂度：O(1)
* 原因：双向链表的节点移动只需要改6个指针（或更少），无需遍历
*/
// JDK源码（LinkedHashMap.afterNodeAccess）：
/*
void afterNodeAccess(Node<K,V> e) { // 参数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; // p将成为新的尾节点，after置null
// 1. 把p从当前位置摘出来：连接p的前驱和后继
if (b == null)
head = a; // p原来是头节点，头节点变成a
else
b.after = a; // p的前驱指向p的后继
if (a != null)
a.before = b; // p的后继的前驱指向p的前驱
else
last = b; // a==null说明p原来是尾节点（不可能进入这个if，因为已经判断了last!=e）
// 2. 把p接到链表尾部
if (last == null)
head = p; // 链表为空（不可能进入这个分支）
else {
p.before = last; // p的前驱指向原尾节点
last.after = p; // 原尾节点的后继指向p
}
tail = p; // 更新tail指针
++modCount; // 结构修改计数（用于fast-fail）
}
}
*/
/**
* afterNodeInsertion：新节点插入后被回调
* 作用：判断是否需要删除最老的节点（LRU淘汰）
*
* 这里有个坑：HashMap默认调用这个方法，但removeEldestEntry默认返回false
* 只有override了removeEldestEntry的子类（比如自定义LRU）才会真正删除节点
*/
// JDK源码（LinkedHashMap.afterNodeInsertion）：
/*
void afterNodeInsertion(boolean evict) { // evict=true时表示"可以淘汰"
LinkedHashMap.Entry<K,V> first;
// removeEldestEntry默认返回false，除非子类override
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true); // 删除链表头部（最老的）
}
}
*/
/**
* 演示accessOrder=true的效果
*/
public static void demonstrateAccessOrder() {
// accessOrder=true：按访问顺序排列
LinkedHashMap<String, Integer> accessOrderMap =
new LinkedHashMap<>(16, 0.75f, true);
accessOrderMap.put("a", 1);
accessOrderMap.put("b", 2);
accessOrderMap.put("c", 3);
System.out.println("插入后: " + accessOrderMap.keySet()); // [a, b, c]
accessOrderMap.get("a"); // 访问a，a移到链表尾部
System.out.println("访问a后: " + accessOrderMap.keySet()); // [b, c, a]
accessOrderMap.get("b"); // 访问b，b移到链表尾部
System.out.println("访问b后: " + accessOrderMap.keySet()); // [c, a, b]
// 头部（c）就是最久未访问的，LRU应该淘汰它
System.out.println("最久未访问（LRU淘汰候选）: " + accessOrderMap.keySet().iterator().next());
}
}2.2 基于LinkedHashMap的LRU实现（面试标准答案）
package com.laozhang.cache;
import java.util.LinkedHashMap;
import java.util.Map;
/**
* 基于LinkedHashMap的LRU Cache实现
* 面试时的标准答案，简洁优雅，但非线程安全
*
* 核心思路：
* 1. 继承LinkedHashMap，开启accessOrder=true
* 2. override removeEldestEntry，超出容量时返回true（淘汰最老节点）
* 3. 利用LinkedHashMap内置的get/put钩子自动维护顺序
*/
public class LRUCacheSimple<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
/**
* @param capacity 缓存最大容量
* 注意：initialCapacity用capacity+1，避免在刚好capacity个元素时触发resize
* loadFactor=0.75是默认值
* accessOrder=true：按访问顺序（最近访问的在尾部）
*/
public LRUCacheSimple(int capacity) {
super(capacity + 1, 0.75f, true);
this.capacity = capacity;
}
/**
* 是否删除最老节点的判断逻辑
* 每次afterNodeInsertion时被调用
* 返回true表示"删除链表头部（最久未访问的节点）"
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity; // 超出容量就淘汰
}
/**
* 这个方法可以不写，LinkedHashMap.get已经在accessOrder=true时自动调用afterNodeAccess
* 这里只是为了演示完整性
*/
// public V get(Object key) { return super.get(key); }
// 使用示例
public static void main(String[] args) {
LRUCacheSimple<Integer, String> cache = new LRUCacheSimple<>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
System.out.println(cache); // {1=one, 2=two, 3=three}
cache.get(1); // 访问1，1移到尾部
cache.put(4, "four"); // 触发淘汰：最老的是2（1被访问过了）
System.out.println(cache); // {3=three, 1=one, 4=four}，2被淘汰
System.out.println("是否包含key=2: " + cache.containsKey(2)); // false
}
}三、生产级线程安全LRU Cache
面试版本够用，但生产环境需要线程安全。
package com.laozhang.cache;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantReadWriteLock;
/**
* 生产级线程安全LRU Cache
* 不依赖LinkedHashMap，手动维护双向链表
*
* 设计选择：
* 1. 用ReentrantReadWriteLock：读多写少时比synchronized更高效
* 2. 手写双向链表：更灵活，便于扩展（比如过期时间）
* 3. 用哨兵节点（head/tail）避免边界判断
*
* 时间复杂度：
* get: O(1)（HashMap查找 + 链表节点移动）
* put: O(1)（同上，淘汰也是O(1)）
*/
public class ThreadSafeLRUCache<K, V> {
private final int capacity;
private final Map<K, Node<K, V>> map;
private final Node<K, V> head; // 哨兵头节点（不存储数据）
private final Node<K, V> tail; // 哨兵尾节点（不存储数据）
private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
// 双向链表节点
private static class Node<K, V> {
K key;
V value;
Node<K, V> prev;
Node<K, V> next;
Node(K key, V value) {
this.key = key;
this.value = value;
}
}
public ThreadSafeLRUCache(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>(capacity * 2); // 预留空间避免扩容
// 初始化哨兵节点：head <-> tail
head = new Node<>(null, null);
tail = new Node<>(null, null);
head.next = tail;
tail.prev = head;
}
/**
* 获取缓存值
* 命中：移到链表尾部（最近访问），返回值
* 未命中：返回null
*/
public V get(K key) {
lock.readLock().lock();
try {
Node<K, V> node = map.get(key);
if (node == null) return null;
// 需要升级为写锁来移动节点
lock.readLock().unlock();
lock.writeLock().lock();
try {
// double-check（升级锁期间可能被其他线程修改）
node = map.get(key);
if (node == null) return null;
moveToTail(node);
return node.value;
} finally {
lock.readLock().lock(); // 重新获取读锁（finally块执行前恢复状态）
lock.writeLock().unlock();
}
} finally {
lock.readLock().unlock();
}
}
/**
* 更简洁的线程安全get（直接用写锁，适合读写比较均衡的场景）
*/
public V getSimple(K key) {
lock.writeLock().lock();
try {
Node<K, V> node = map.get(key);
if (node == null) return null;
moveToTail(node);
return node.value;
} finally {
lock.writeLock().unlock();
}
}
/**
* 写入缓存值
*/
public void put(K key, V value) {
lock.writeLock().lock();
try {
if (map.containsKey(key)) {
// 更新已有节点：改value，移到尾部
Node<K, V> node = map.get(key);
node.value = value;
moveToTail(node);
} else {
// 新节点
if (map.size() >= capacity) {
// 淘汰最久未访问的节点（head.next，链表头部）
Node<K, V> evicted = head.next;
removeNode(evicted);
map.remove(evicted.key);
}
Node<K, V> newNode = new Node<>(key, value);
addToTail(newNode);
map.put(key, newNode);
}
} finally {
lock.writeLock().unlock();
}
}
// 把节点插入链表尾部（tail的前面）
private void addToTail(Node<K, V> node) {
node.prev = tail.prev;
node.next = tail;
tail.prev.next = node;
tail.prev = node;
}
// 从链表中移除节点
private void removeNode(Node<K, V> node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
// 移到链表尾部（先移除再插入尾部）
private void moveToTail(Node<K, V> node) {
removeNode(node);
addToTail(node);
}
public int size() {
lock.readLock().lock();
try { return map.size(); } finally { lock.readLock().unlock(); }
}
public static void main(String[] args) throws InterruptedException {
ThreadSafeLRUCache<Integer, String> cache = new ThreadSafeLRUCache<>(3);
// 单线程功能验证
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
System.out.println("get(1): " + cache.getSimple(1)); // one，并把1移到尾部
cache.put(4, "four"); // 淘汰最老的（2，因为1被访问过了）
System.out.println("get(2): " + cache.getSimple(2)); // null（已淘汰）
System.out.println("get(3): " + cache.getSimple(3)); // three
System.out.println("size: " + cache.size()); // 3
// 并发测试
java.util.concurrent.ExecutorService pool =
java.util.concurrent.Executors.newFixedThreadPool(10);
java.util.concurrent.CountDownLatch latch =
new java.util.concurrent.CountDownLatch(100);
for (int i = 0; i < 100; i++) {
final int idx = i;
pool.submit(() -> {
cache.put(idx % 10, "val-" + idx);
cache.getSimple(idx % 5);
latch.countDown();
});
}
latch.await();
System.out.println("并发操作后size（应该<=3）: " + cache.size());
pool.shutdown();
}
}四、踩坑实录
坑1：在多线程环境下直接使用LinkedHashMap版的LRU，数据结构损坏
报错现象：生产环境偶发NullPointerException，栈里指向LinkedHashMap.afterNodeAccess。线上稳定运行了两周才出现，极难复现。
根本原因：LinkedHashMap的accessOrder=true模式下，每次get都会修改双向链表（调用afterNodeAccess），而LinkedHashMap没有任何同步保护。两个线程同时get，双向链表的before/after指针被并发修改，指针断裂。
具体解法：
// 解法1：Collections.synchronizedMap包装（粗粒度锁，全局锁）
Map<K,V> syncLRU = Collections.synchronizedMap(new LRUCacheSimple<>(100));
// 缺点：所有操作串行，高并发下性能差
// 解法2：用上面的ThreadSafeLRUCache（读写锁，读写分离）
// 解法3：生产环境直接用Caffeine（Google开源，高性能，功能完整）
// implementation 'com.github.ben-manes.caffeine:caffeine:3.1.6'
// Cache<Key, Value> cache = Caffeine.newBuilder()
// .maximumSize(100)
// .expireAfterWrite(10, TimeUnit.MINUTES)
// .build();坑2：removeEldestEntry的参数eldest不一定是"最旧的"那个
报错现象：自定义了removeEldestEntry，以为eldest.getValue()拿到的是最老的元素，用来做一些业务逻辑，结果发现行为不对。
根本原因：removeEldestEntry的参数eldest是链表头部的节点，但链表头部到底是"最早插入的"还是"最久未访问的"，取决于accessOrder参数。如果你在removeEldestEntry里访问eldest，不要修改map，否则会触发ConcurrentModificationException。
具体解法：
// 错误：在removeEldestEntry里修改map
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
if (size() > capacity) {
// 错误！！不能在这里修改map
someOtherMap.put(eldest.getKey(), eldest.getValue()); // 可能导致并发问题
return true;
}
return false;
}
// 正确：removeEldestEntry只做判断，不做副作用操作
// 如果需要在淘汰时触发回调，override LinkedHashMap.afterNodeRemoval
@Override
protected void afterNodeRemoval(HashMap.Node<K, V> p) {
// 这里可以安全地执行淘汰回调，节点已经从map中移除
System.out.println("淘汰节点: " + p.key);
}坑3：LRU容量设置不合理，缓存命中率很低
报错现象：上线了LRU Cache，但数据库压力没有明显减少，监控发现缓存命中率只有20%。
根本原因：容量设置太小，热点数据被冷门数据频繁挤出去。这不是代码bug，是容量规划问题。
具体解法：
// 分析缓存命中率的方法：统计hitCount/totalCount
public class InstrumentedLRUCache<K, V> extends LRUCacheSimple<K, V> {
private long hitCount = 0;
private long missCount = 0;
public InstrumentedLRUCache(int capacity) { super(capacity); }
@Override
public V get(Object key) {
V value = super.get(key);
if (value != null) hitCount++;
else missCount++;
return value;
}
public double hitRate() {
long total = hitCount + missCount;
return total == 0 ? 0 : (double) hitCount / total;
}
public void printStats() {
System.out.printf("命中率: %.2f%% (命中%d次, 未命中%d次)%n",
hitRate() * 100, hitCount, missCount);
}
}
// 实际操作：先跑一周低命中率预警，根据hitRate动态扩容
// 经验值：大多数场景，容量设为预期热点数据量的1.5倍，命中率可以达到80%+五、总结与延伸
LinkedHashMap的accessOrder=true模式是Java内置的LRU机制，但非线程安全。 它的核心是afterNodeAccess钩子，每次访问都把节点移到双向链表尾部，O(1)复杂度。面试写这个答案代码量少，但要说清楚原理才能加分。手写LRU的难点不在逻辑，在细节：哨兵节点、双写一致（HashMap和链表同步更新）、线程安全。 用哨兵节点可以避免大量边界判断，这是工程实践里的经验，不是教科书能学到的。
生产环境别自己造LRU轮子，用Caffeine。 它实现的是改进版W-TinyLFU算法（比LRU命中率更高），支持过期时间、软引用、异步加载等特性，性能比
Collections.synchronizedMap包装的LRU快10倍以上。面试场景手写LRU，工作场景用Caffeine。