一、项目背景详细介绍
在高并发、高性能的现代应用中，缓存（Cache）是提升系统响应速度、降低后端存储压力的关键技术之一。根据“最近最少使用”策略（LRU，Least Recently Used），当缓存达到容量上限时，应当淘汰最久未被访问的条目，以保证热点数据能够长久保留在缓存中。LRU 缓存在 Web 浏览器缓存、数据库连接池、操作系统页面置换、分布式缓存（如 Redis LRU 模式）等场景中被广泛采用。
在 Java 生态中，可以利用 LinkedHashMap 的访问顺序特性快速实现 LRU。但在一些特定场景下，我们需要更细粒度的控制，例如自定义淘汰时机、统计命中率、结合多级缓存、或在无 LinkedHashMap 的环境下手写实现。本项目旨在通过底层原理讲解，结合 Map + 双向链表，手工实现一个线程安全或非线程安全版本的通用 LRU 缓存类，并提供完整可运行代码与示例，帮助开发者深刻理解 LRU 算法原理与 Java 实现细节。
二、项目需求详细介绍
功能需求
提供一个泛型类 LRUCache
构造时指定缓存最大容量 capacity；
支持以下基本操作：
V get(K key)：获取缓存中对应值，若存在则提升为“最近使用”；
void put(K key, V value)：插入或更新缓存条目，若达到容量上限，则淘汰最久未使用条目；
支持 void remove(K key)、void clear() 等辅助方法；
缓存内部统计命中次数和访问次数（可选）。
性能需求
时间复杂度：get 与 put 操作均需保持 O(1)；
空间复杂度：仅额外开销双向链表节点和 Map 条目。
线程安全需求
提供非线程安全版；
可选提供基于 ReentrantLock 或 Collections.synchronizedMap 的线程安全包装。
可扩展性要求
支持自定义淘汰回调，如在条目被淘汰时执行清理操作；
支持 TTL（Time-To-Live）过期策略与 LRU 结合；
支持多级缓存设计接口。
代码规范
Java 8 及以上；
将不同类分文件显示在同一代码块内，不同文件以注释分隔；
代码含详细注释，说明每步原理与关键逻辑；
代码详细解读仅说明各方法职责，不重复源码。
三、相关技术详细介绍
LRU 算法原理
核心思想：维护一组缓存条目，最近访问的放在队首，最久未使用的放在队尾；
每次 get 或 put 时，将对应条目移动到队首；
当容量超限时，移除队尾条目；
双向链表
用于快速插入和删除任意节点，支持 O(1) 时间移动；
每个节点包含 prev、next 指针，以及 key 与 value；
哈希表（Map）
用于根据 key 快速定位到对应的链表节点，支持 O(1) 时间查找；
Map 条目映射 key 到双向链表节点引用；
Java 内置类：LinkedHashMap
LinkedHashMap 带访问顺序参数，可以通过覆写 removeEldestEntry() 实现 LRU；
但学习价值稍逊，本文更侧重底层手写实现；
线程同步
非线程安全实现仅在单线程或外部同步场景使用；
若需线程安全，可在关键方法上加 synchronized 或使用 ReentrantLock；
四、实现思路详细介绍
本文采用经典的 Map + 双向链表结构，思路如下：
数据结构
class Node { K key; V value; Node prev, next; }
Map
Node head, tail：双向链表哨兵，用于界定最“新”与最“久”；
初始化
构造 LRUCache(int capacity) 时，初始化 map = new HashMap<>(capacity)；
初始化 head、tail 为虚拟节点，并互相指向；
get 操作
在 map 中查找对应 Node；
若不存在，返回 null 或默认值；
若存在，将该节点从链表中摘除并插入到 head.next，标记为最近使用；
返回 value；
put 操作
在 map 中查找 key；
若存在，更新节点的 value 并同样移动到队首；
若不存在，构建新 Node 并插入到链表头部，同时放入 map；
检查 map.size() > capacity，如是，取出链表尾部节点（即 tail.prev），从链表中删除并从 map 中移除；可调用淘汰回调；
remove / clear
remove(K key)：在 map 中定位节点，若存在，摘除并删除映射；
clear()：重置链表指针与清空 map。
可选统计
在 get 和 put 中分别累加访问次数和命中次数，计算命中率。
线程安全包装
在类上或关键方法上加 synchronized；
或使用 ReentrantLock lock，在方法体 lock.lock()…finally{lock.unlock();}。
五、完整实现代码
// 文件：Node.java
package com.example.cache;
/**
* 双向链表节点
* @param
* @param
*/
public class Node
K key;
V value;
Node
Node
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
// 文件：LRUCache.java
package com.example.cache;
import java.util.HashMap;
import java.util.Map;
/**
* 基于 Map + 双向链表的 LRU 缓存实现
* @param
* @param
*/
public class LRUCache
private final int capacity; // 缓存容量上限
private final Map
private final Node
// 可选统计字段
private long hits = 0; // 命中次数
private long requests = 0; // 访问总次数
/**
* 构造指定容量的 LRUCache
* @param capacity 缓存最大容量
*/
public LRUCache(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("Capacity must be positive");
}
this.capacity = capacity;
this.map = new HashMap<>(capacity);
// 初始化虚拟头尾节点
head = new Node<>(null, null);
tail = new Node<>(null, null);
head.next = tail;
tail.prev = head;
}
/**
* 获取键对应的值，并将该条目提升为最近使用
* @param key 键
* @return 值；若缓存中不存在，返回 null
*/
public V get(K key) {
requests++;
Node
if (node == null) {
return null;
}
hits++;
// 将节点移动到头部（最近使用）
removeNode(node);
insertAfterHead(node);
return node.value;
}
/**
* 插入或更新键值，并将其提升为最近使用；若超出容量，淘汰最久未使用条目
* @param key 键
* @param value 值
*/
public void put(K key, V value) {
Node
if (node != null) {
// 更新值并移动
node.value = value;
removeNode(node);
insertAfterHead(node);
} else {
// 插入新节点
Node
map.put(key, newNode);
insertAfterHead(newNode);
// 超出容量时淘汰尾部节点
if (map.size() > capacity) {
Node
removeNode(lru);
map.remove(lru.key);
// 可选回调：onEvict(lru.key, lru.value);
}
}
}
/**
* 删除指定键对应条目
* @param key 键
*/
public void remove(K key) {
Node
if (node != null) {
removeNode(node);
}
}
/** 清空整个缓存 */
public void clear() {
map.clear();
head.next = tail;
tail.prev = head;
hits = requests = 0;
}
/** 返回缓存当前命中率 */
public double getHitRate() {
return requests == 0 ? 0.0 : (double) hits / requests;
}
// 从链表中摘除节点（不涉及 map）
private void removeNode(Node
node.prev.next = node.next;
node.next.prev = node.prev;
}
// 将节点插入到虚拟头后面（标记为最近使用）
private void insertAfterHead(Node
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
}
// 文件：Main.java
package com.example.cache;
public class Main {
public static void main(String[] args) {
// 创建容量为 3 的 LRU 缓存
LRUCache
cache.put(1, "A"); // 缓存：1:A
cache.put(2, "B"); // 缓存：2:B,1:A
cache.put(3, "C"); // 缓存：3:C,2:B,1:A
cache.get(2); // 命中 B，缓存：2:B,3:C,1:A
cache.put(4, "D"); // 插入 D，淘汰 1:A，缓存：4:D,2:B,3:C
System.out.println(cache.get(1)); // null (已淘汰)
System.out.println(cache.get(3)); // C
System.out.println("Hit rate: " + cache.getHitRate());
}
}
六、代码详细解读
Node
LRUCache 构造方法：
校验 capacity 合法性；
初始化 map，并创建虚拟头尾节点，完成链表初始连接；
get(K) 方法：
在 map 中查找节点，若不存在返回 null；
若存在，先自增统计，再从链表中摘除该节点并插入到头部，最后返回 value；
put(K,V) 方法：
若 key 已存在，更新其 value 并移动节点至头部；
否则，新建节点插入头部并放入 map，然后检查容量，若超限则移除尾部最旧节点并从 map 中删除；
辅助方法
removeNode(Node)：从双向链表中摘除某节点；
insertAfterHead(Node)：将节点插入到虚拟头节点之后，标记为最近使用；
统计与其他方法
remove(K)、clear() 分别用于删除单条或全量清空缓存；
getHitRate() 返回命中率，供性能分析；
七、项目详细总结
基于 Map + 双向链表 实现 LRU，可在 O(1) 时间完成查找、插入、更新和淘汰操作；
虚拟头尾节点设计简化边界逻辑，使插入与删除操作无需处理空链表或单节点特殊情况；
统计命中率功能有助于分析缓存性能与容量调优；
通过接口与回调，可进一步扩展至多级缓存、过期策略或持久化；
八、项目常见问题及解答
为什么要用虚拟头尾节点？
避免在链表头部或尾部插入与删除时做额外的空指针检查，逻辑更简洁；
如何让本实现线程安全？
可在 get、put、remove 等方法上加 synchronized，或在类中使用 private final ReentrantLock lock 并在方法体内加锁；
为何要将访问统计放在 get 方法中？
统计命中率时需要区分访问次数与命中次数，以评估缓存效果；
如何支持条目过期（TTL）？
可为每个节点额外维护 timestamp，定期扫描或在 get 时检查并移除过期节点；
Map 初始容量如何设置？
为避免扩容带来的性能消耗，可根据 capacity 计算 loadFactor 并设置 HashMap 初始容量；
九、扩展方向与性能优化
多级缓存设计
L1 级使用本地内存 LRU；L2 级使用分布式缓存（如 Redis）；
过期与访问统计结合
按访问频次和时间综合权重淘汰，实现 LFU 或 LFU+LRU 混合策略；
异步淘汰与批量驱逐
在后台定时驱逐过期或低频条目，避免用户操作阻塞；
无锁实现
基于 java.util.concurrent 包中的 ConcurrentLinkedDeque 和 ConcurrentHashMap 实现近似 LRU；
持久化缓存
将热点数据序列化存入本地文件或分布式存储，支持重启恢复；