LRU即最近最少使用淘汰策略，核心逻辑是优先淘汰最久未被访问的缓存数据，在本地缓存场景中应用广泛。默认基于HashMap和双向链表实现的LRU缓存无法应对多线程并发访问，需要结合并发容器和同步机制保证线程安全。
核心设计思路
实现线程安全的LRU缓存需要兼顾两个核心需求：一是快速定位缓存节点，二是维护节点的访问顺序实现淘汰逻辑。ConcurrentHashMap可以保证节点的增删改操作的线程安全，双向链表可以维护节点的访问顺序，两者结合即可满足需求。
- ConcurrentHashMap存储键到双向链表节点的映射，支持O(1)时间复杂度的节点查找
- 双向链表维护节点的访问顺序，头部为最近访问节点，尾部为最久未访问节点
- 所有修改链表结构的操作都需要加锁，避免并发修改导致的链表错乱
节点结构设计
双向链表的节点需要存储键、值、前驱节点和后继节点，方便调整链表顺序和移除节点。
class Node<K, V> {
K key;
V value;
Node<K, V> prev;
Node<K, V> next;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
缓存核心实现
初始化参数
缓存需要指定最大容量，当缓存大小超过最大容量时触发淘汰逻辑。
public class ThreadSafeLRUCache<K, V> {
// 最大容量
private final int maxSize;
// 存储键到节点的映射
private final ConcurrentHashMap<K, Node<K, V>> cache;
// 双向链表头尾虚拟节点，简化边界处理
private final Node<K, V> head;
private final Node<K, V> tail;
// 链表操作锁
private final Object lock = new Object();
public ThreadSafeLRUCache(int maxSize) {
this.maxSize = maxSize;
this.cache = new ConcurrentHashMap<>();
// 初始化虚拟头尾节点，不存储实际数据
head = new Node<>(null, null);
tail = new Node<>(null, null);
head.next = tail;
tail.prev = head;
}
}
访问缓存逻辑
访问缓存时，若节点存在则将其移动到链表头部，表示最近被访问；若不存在返回null。
public V get(K key) {
Node<K, V> node = cache.get(key);
if (node == null) {
return null;
}
// 移动节点到头部，需要加锁保证链表操作线程安全
synchronized (lock) {
moveToHead(node);
}
return node.value;
}
添加/更新缓存逻辑
添加缓存时，若键已存在则更新值并移动到头部；若不存在则创建新节点添加到头部，若超过最大容量则移除尾部节点。
public void put(K key, V value) {
Node<K, V> existingNode = cache.get(key);
if (existingNode != null) {
// 更新已有节点的值
existingNode.value = value;
synchronized (lock) {
moveToHead(existingNode);
}
return;
}
// 创建新节点
Node<K, V> newNode = new Node<>(key, value);
synchronized (lock) {
// 添加到链表头部
addToHead(newNode);
cache.put(key, newNode);
// 超过最大容量，移除尾部节点
if (cache.size() > maxSize) {
Node<K, V> removedNode = removeTail();
if (removedNode != null) {
cache.remove(removedNode.key);
}
}
}
}
链表辅助方法
链表的操作包括添加节点到头部、移除节点、移动节点到头部、移除尾部节点，这些操作都需要保证原子性，因此放在同步块中执行。
// 添加节点到链表头部
private void addToHead(Node<K, V> node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
// 移除指定节点
private void removeNode(Node<K, V> node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
// 移动节点到头部
private void moveToHead(Node<K, V> node) {
removeNode(node);
addToHead(node);
}
// 移除尾部节点，返回被移除的节点
private Node<K, V> removeTail() {
Node<K, V> node = tail.prev;
if (node == head) {
return null;
}
removeNode(node);
return node;
}
使用示例
以下是缓存的基本使用方式，模拟多线程场景下的缓存访问。
public class Main {
public static void main(String[] args) {
ThreadSafeLRUCache<String, Integer> cache = new ThreadSafeLRUCache<>(2);
// 添加缓存
cache.put("a", 1);
cache.put("b", 2);
// 访问缓存，触发a移动到头部
System.out.println(cache.get("a")); // 输出1
// 添加新缓存，超过容量，淘汰最久未访问的b
cache.put("c", 3);
System.out.println(cache.get("b")); // 输出null，已被淘汰
System.out.println(cache.get("c")); // 输出3
}
}
线程安全说明
本实现的线程安全保证来自两部分：一是ConcurrentHashMap本身的线程安全特性，保证键值映射的增删查操作不会出现并发问题；二是所有修改双向链表结构的操作都通过同一个锁对象同步，避免多个线程同时修改链表导致的指针错乱。这种组合方式既保证了并发性能，又实现了完整的LRU淘汰逻辑。
LRU缓存ConcurrentHashMap双向链表线程安全修改时间：2026-07-02 11:15:33