Java实现LRU缓存案例：从面试题到生产级高并发架构的终极指南
目录导读
- LRU缓存核心原理与数据结构选型
- 为什么HashMap+双向链表是黄金组合？
- 手写LRU：LinkedHashMap的“温柔陷阱”
- Java生产级LRU实现案例（双重锁+泛型+TTL）
代码级拆解：get/put/淘汰/过期四大核心方法
- 高并发场景下的性能优化与坑点规避
- Synchronized vs ConcurrentHashMap+CAS
- 缓存穿透、雪崩、击穿的“三道防线”
- LRU进化版：LRU-K与TinyLFU（面试加分项）
- 常见面试问答（Q&A）速查表
LRU缓存核心原理与数据结构选型
LRU（Least Recently Used）算法的本质是“最近最少使用”，当缓存满时，优先淘汰最长时间未被访问的数据，实现该算法需解决两个核心问题：O(1)时间复杂度的数据访问 与 O(1)时间复杂度的有序淘汰。
为什么HashMap+双向链表是黄金组合？
- HashMap（哈希表）负责提供O(1)的键值查询，通过
hash定位节点地址。 - 双向链表维护访问顺序：每次
get或put，将该节点移动到链表头部；当容量满时，直接删除链表尾部节点。 - 之所以用双向链表而非单链表，是因为删除节点时需要获取其前驱节点，双向链表可直接通过
node.prev获取，避免O(n)遍历。
手写LRU：LinkedHashMap的“温柔陷阱”
Java集合框架的LinkedHashMap内置了accessOrder参数，可在构造时设为true，这样每次访问节点会自动移动到链表尾部，重写removeEldestEntry(Map.Entry)方法，当size() > capacity时返回true即可实现简易LRU。但此方法线程不安全，且无法控制过期时间（TTL）,仅适用于单线程或学习演示。
Java生产级LRU实现案例（双重锁+泛型+TTL）
以下为可直接落地的生产级代码，包含泛型支持、过期时间（TTL）、线程安全（双重检查锁）：
public class LRUCache<K, V> {
// 双向链表节点
private static class Node<K, V> {
K key;
V value;
long expireAt; // 过期时间戳（ms），0表示永不过期
Node<K, V> prev, next;
Node(K key, V value, long expireAt) {
this.key = key;
this.value = value;
this.expireAt = expireAt;
}
}
private final int capacity;
private final Map<K, Node<K, V>> map = new HashMap<>();
private final Node<K, V> head = new Node<>(null, null, 0); // 虚拟头
private final Node<K, V> tail = new Node<>(null, null, 0); // 虚拟尾
private final ReentrantLock lock = new ReentrantLock();
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public V get(K key) {
lock.lock();
try {
Node<K, V> node = map.get(key);
if (node == null) return null;
if (isExpired(node)) { // 过期则删除
removeNode(node);
map.remove(key);
return null;
}
moveToHead(node); // 更新访问顺序
return node.value;
} finally {
lock.unlock();
}
}
public void put(K key, V value, long ttlMillis) {
lock.lock();
try {
Node<K, V> node = map.get(key);
long expireAt = ttlMillis > 0 ? System.currentTimeMillis() + ttlMillis : 0;
if (node != null) {
node.value = value;
node.expireAt = expireAt;
moveToHead(node);
} else {
node = new Node<>(key, value, expireAt);
map.put(key, node);
addToHead(node);
if (map.size() > capacity) {
// 淘汰尾部：需跳过已过期的节点
Node<K, V> tailNode = tail.prev;
while (tailNode != head && isExpired(tailNode)) {
removeNode(tailNode);
map.remove(tailNode.key);
tailNode = tail.prev;
}
if (map.size() > capacity) {
Node<K, V> eldest = tail.prev;
removeNode(eldest);
map.remove(eldest.key);
}
}
}
} finally {
lock.unlock();
}
}
// 省略 addToHead, removeNode, moveToHead, isExpired 等私有方法
}
代码核心设计解析：
- 双重检查锁：
lock保证并发安全，但读写均加锁,写多读少场景性能尚可。 - TTL处理：
get时主动检查过期；put时若缓存已满，为避免“脏数据”堆积，先清理尾部连续过期节点,再淘汰真正的LRU节点。 - 虚拟头尾节点：避免空指针判断,简化链表边界操作。
高并发场景下的性能优化与坑点规避
Synchronized vs ConcurrentHashMap+CAS
- 上述
ReentrantLock是全局锁，高并发（>10万QPS）下竞争激烈，优化方案：改用ConcurrentHashMap存储节点，但并发淘汰逻辑复杂（需原子操作链表）。 - 实践方案：采用
ConcurrentHashMap + 分段锁（Striped Lock），为每个哈希桶分配独立锁,降低竞争。 - 最佳实践：若追求极致性能，可使用
Caffeine或Guava Cache，其基于ConcurrentHashMap+ 环形缓冲区实现,但面试时需展示底层原理。
缓存三大坑（穿透、雪崩、击穿）的“三道防线”
- 缓存穿透（查询不存在的数据）：采用布隆过滤器在缓存前拦截；或缓存空值（TTL设置极短）。
- 缓存雪崩（大量key同时失效）：设置随机TTL（如基础时间+随机数）；或采用多级缓存（本地Caffeine + Redis）。
- 缓存击穿（热点key过期瞬间高并发）：互斥锁（只允许一个线程重建缓存）；或逻辑过期（永不过期，异步更新）。
LRU进化版：LRU-K与TinyLFU（面试加分项）
LRU-K：核心思想是“访问两次才进入缓存”，记录每个key的访问历史（队列），第一次访问仅放入历史队列，第二次访问才移入缓存队列，有效防止一次性数据污染缓存。TinyLFU（Caffeine内置）：使用Count-Min Sketch频率估算器，结合LFU（最不经常使用）与LRU，适应“稀疏突发”流量。
常见面试问答（Q&A）速查表
Q1：为什么用双向链表不用单向？
A：单向链表删除节点需遍历找前驱，复杂度O(n)；双向链表直接node.prev，O(1)。
Q2：HashMap的扩容会影响LRU性能吗？
A：会，扩容需重新哈希，会短暂阻塞，生产环境可预分配容量（new HashMap<>(capacity)），避免扩容。
Q3：如何实现线程安全的LRU且保证高性能？
A：分段锁或使用ConcurrentLinkedHashMap；或直接使用Caffeine（内部采用W-TinyLFU算法）。
Q4：TTL过期但从未访问的节点如何清理？
A：惰性删除（访问时检查） + 定时清理（后台线程扫描链表尾部），实践中优先惰性删除,避免定时任务开销。
从面试手写LinkedHashMap到生产级高并发框架，LRU缓存的实现折射出Java并发编程、数据结构与系统架构设计的核心思想，掌握本文代码与原理，你不仅能轻松应对算法题，更能深入理解Caffeine、Redis等主流组件的底层逻辑。优化永无止境，但基础决定上限。
