LRU（Least Recently Used，最近最少使用）缓存是一种经典的数据结构，广泛应用于操作系统内存管理、数据库缓冲池、分布式缓存（如Redis的淘汰策略）以及Web应用的本地缓存等场景。其核心思想是：当缓存容量满时，优先淘汰最久未被访问的数据，以保留近期活跃的数据。
本文将用Java从零实现一个完整的LRU缓存，深入讲解哈希表实现O(1)查找与双向链表维护访问顺序的核心机制，并扩展至线程安全版本。
一、为什么需要LRU缓存
在计算机系统中，内存访问速度远快于磁盘或网络。缓存通过将热点数据保留在内存中，显著降低后续访问的延迟。但内存容量有限，当缓存满时必须决定淘汰哪些数据。
常见的缓存淘汰策略包括：
| 策略 | 描述 | 适用场景 |
|---|---|---|
| FIFO | 先进先出，按进入顺序淘汰 | 顺序处理流 |
| LFU | 最少使用，按访问频率淘汰 | 频率稳定的热点 |
| LRU | 最近最少使用，按时间局部性淘汰 | 大多数通用场景 |
LRU基于时间局部性原理：如果一个数据最近被访问过，那么它在未来被访问的概率也更高。这一假设在绝大多数实际场景中成立。
二、LRU的核心设计思路
要实现一个高效的LRU缓存，需要同时满足两个操作都在O(1)时间复杂度：
- get(key)：查找某个key对应的value
- put(key, value)：插入或更新一个键值对，并在容量满时淘汰最久未使用的数据
单一数据结构无法满足这两个需求：
– 哈希表：get和put都是O(1)，但无法记录访问顺序
– 链表：可以维护顺序，但查找需要O(n)
解决方案：哈希表 + 双向链表的强强联合
- 哈希表（HashMap）：存储key到链表节点的映射，实现O(1)查找
- 双向链表（Doubly Linked List）：按访问时间顺序存储节点，头部为最近访问，尾部为最久未访问，实现O(1)的移动和删除
三、数据结构定义
3.1 双向链表节点
/**
* 双向链表节点，同时存储key和value
* 存储key的目的是在淘汰尾部节点时，能通过key从哈希表中删除对应映射
*/
class Node {
int key;
int value;
Node prev;
Node next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
3.2 链表操作封装
为了简化LRUCache的实现，我们将链表操作（添加到头部、删除节点、移动节点到头部）封装在独立方法中。
/**
* LRU缓存核心实现
* 时间复杂度：get和put均为O(1)
* 空间复杂度：O(capacity)
*/
public class LRUCache {
private final int capacity;
private final Map<Integer, Node> cache;
private final Node head; // 伪头部：最近使用的节点
private final Node tail; // 伪尾部：最久未使用的节点
private int size;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
// 使用伪头部和伪尾部简化边界判断
this.head = new Node(-1, -1);
this.tail = new Node(-1, -1);
head.next = tail;
tail.prev = head;
this.size = 0;
}
}
四、核心操作实现
4.1 移动到头部（标记为最近使用）
/**
* 将节点移动到链表头部（标记为最近使用）
* 步骤：先删除原位置，再插入头部
*/
private void moveToHead(Node node) {
removeNode(node);
addToHead(node);
}
/**
* 在链表头部添加节点
*/
private void addToHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
/**
* 从链表中删除节点
*/
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
4.2 淘汰尾部节点（移除最久未使用）
/**
* 删除链表尾部节点（最久未使用），并返回该节点
* 用于容量满时淘汰数据
*/
private Node removeTail() {
Node node = tail.prev;
removeNode(node);
return node;
}
4.3 get操作：O(1)查找与更新
/**
* 获取key对应的value
* 如果key存在，将其移动到链表头部（标记为最近使用），返回value
* 如果key不存在，返回-1
*/
public int get(int key) {
Node node = cache.get(key);
if (node == null) {
return -1; // key不存在
}
// 访问过，移动到头部
moveToHead(node);
return node.value;
}
4.4 put操作：插入、更新与淘汰
/**
* 插入或更新键值对
* 如果key已存在，更新value并移动到头部
* 如果key不存在，创建新节点插入头部；若容量满，先淘汰尾部节点
*/
public void put(int key, int value) {
Node node = cache.get(key);
if (node != null) {
// key已存在，更新value并移动到头部
node.value = value;
moveToHead(node);
return;
}
// key不存在，创建新节点
Node newNode = new Node(key, value);
cache.put(key, newNode);
addToHead(newNode);
size++;
// 超出容量，淘汰尾部节点
if (size > capacity) {
Node tailNode = removeTail();
cache.remove(tailNode.key);
size--;
}
}
五、完整Java代码
import java.util.HashMap;
import java.util.Map;
/**
* LRU缓存实现（哈希表 + 双向链表）
* get和put操作时间复杂度均为O(1)
*/
public class LRUCache {
/**
* 双向链表节点
*/
static class Node {
int key;
int value;
Node prev;
Node next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final Map<Integer, Node> cache;
private final Node head; // 伪头部
private final Node tail; // 伪尾部
private int size;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
this.head = new Node(-1, -1);
this.tail = new Node(-1, -1);
head.next = tail;
tail.prev = head;
this.size = 0;
}
/**
* 获取key对应的value，不存在返回-1
* 每次get都会将该节点提升为最近使用
*/
public int get(int key) {
Node node = cache.get(key);
if (node == null) {
return -1;
}
moveToHead(node);
return node.value;
}
/**
* 插入或更新键值对
*/
public void put(int key, int value) {
Node node = cache.get(key);
if (node != null) {
node.value = value;
moveToHead(node);
return;
}
Node newNode = new Node(key, value);
cache.put(key, newNode);
addToHead(newNode);
size++;
if (size > capacity) {
Node tailNode = removeTail();
cache.remove(tailNode.key);
size--;
}
}
private void addToHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(Node node) {
removeNode(node);
addToHead(node);
}
private Node removeTail() {
Node node = tail.prev;
removeNode(node);
return node;
}
/**
* 打印当前缓存状态（调试用）
*/
public void printCache() {
System.out.print("Cache[head->tail]: ");
Node cur = head.next;
while (cur != tail) {
System.out.print("(" + cur.key + "=" + cur.value + ") ");
cur = cur.next;
}
System.out.println();
}
/**
* 主程序：演示LRU缓存的工作过程
*/
public static void main(String[] args) {
System.out.println("=== LRU缓存演示（容量=3） ===\n");
LRUCache cache = new LRUCache(3);
// 步骤1：依次插入1, 2, 3
System.out.println("插入 (1=10), (2=20), (3=30)");
cache.put(1, 10);
cache.put(2, 20);
cache.put(3, 30);
cache.printCache(); // 3, 2, 1
// 步骤2：访问key=1，将其提升到最近使用
System.out.println("\nget(1) = " + cache.get(1));
cache.printCache(); // 1, 3, 2
// 步骤3：插入4，超出容量，淘汰最久未使用的2
System.out.println("\n插入 (4=40)，容量满，淘汰key=2");
cache.put(4, 40);
cache.printCache(); // 4, 1, 3
// 步骤4：访问3，提升到最近使用
System.out.println("\nget(3) = " + cache.get(3));
cache.printCache(); // 3, 4, 1
// 步骤5：插入5，淘汰最久未使用的1
System.out.println("\n插入 (5=50)，淘汰key=1");
cache.put(5, 50);
cache.printCache(); // 5, 3, 4
// 步骤6：访问不存在的key
System.out.println("\nget(2) = " + cache.get(2) + " (已被淘汰)");
// 步骤7：更新已有key的值
System.out.println("\n更新 (3=300)");
cache.put(3, 300);
cache.printCache(); // 3, 5, 4
System.out.println("\n=== 演示结束 ===");
}
}
六、Java标准库的LinkedHashMap方案
Java标准库中的LinkedHashMap已经内置了LRU支持，只需重写removeEldestEntry方法即可：
import java.util.LinkedHashMap;
import java.util.Map;
/**
* 基于LinkedHashMap的LRU缓存实现
* 代码更简洁，但理解底层原理对面试至关重要
*/
public class LRUCacheLinkedHashMap extends LinkedHashMap<Integer, Integer> {
private final int capacity;
public LRUCacheLinkedHashMap(int capacity) {
// accessOrder=true 表示按访问顺序排序（false为插入顺序）
super(capacity, 0.75f, true);
this.capacity = capacity;
}
/**
* 当插入新元素后，如果此方法返回true，则删除最老的元素
*/
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
public static void main(String[] args) {
LRUCacheLinkedHashMap cache = new LRUCacheLinkedHashMap(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println(cache.get(1)); // 1
cache.put(3, 3); // 淘汰key=2
System.out.println(cache.get(2)); // -1
System.out.println(cache.get(3)); // 3
}
}
虽然LinkedHashMap方案简洁，但面试和工程深入理解时，手写哈希表+双向链表的版本更能展示对数据结构的掌控力。
七、线程安全扩展
在多线程环境中，需要对get和put方法加锁。可以使用synchronized或ReentrantReadWriteLock优化读多写少的场景：
import java.util.concurrent.locks.ReentrantReadWriteLock;
/**
* 线程安全的LRU缓存
* 使用读写锁优化并发性能：允许多个线程同时读，写操作独占
*/
public class ConcurrentLRUCache {
private final LRUCache cache;
private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
private final ReentrantReadWriteLock.ReadLock readLock = lock.readLock();
private final ReentrantReadWriteLock.WriteLock writeLock = lock.writeLock();
public ConcurrentLRUCache(int capacity) {
this.cache = new LRUCache(capacity);
}
public int get(int key) {
readLock.lock();
try {
return cache.get(key);
} finally {
readLock.unlock();
}
}
public void put(int key, int value) {
writeLock.lock();
try {
cache.put(key, value);
} finally {
writeLock.unlock();
}
}
}
八、复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| get | O(1) | O(1) | 哈希表查找 + 链表移动 |
| put | O(1) | O(1) | 哈希表插入/更新 + 链表操作 |
| 整体 | — | O(capacity) | 最多存储capacity个节点 |
九、实际应用场景
- 数据库连接池：缓存最近使用的数据库连接，避免频繁创建和销毁
- 图片/资源缓存：Android的LruCache就是基于此原理
- DNS缓存：操作系统缓存最近解析的域名，加速后续访问
- CPU缓存行：硬件层面的LRU近似算法管理缓存行替换
- Redis：支持allkeys-lru淘汰策略，在内存满时自动淘汰冷数据
十、总结
LRU缓存是数据结构与算法结合的完美典范：
- 哈希表提供O(1)的键值查找能力，是”快速定位”的基石
- 双向链表提供O(1)的顺序维护能力，是”有序管理”的基石
- 两者的配合使得LRU的两个核心操作都在常数时间内完成
掌握LRU缓存的实现，不仅能应对各类算法面试，更能帮助你在实际工程中设计出高效的缓存系统。从LinkedHashMap的简洁方案到手写双向链表的底层方案，建议先理解后者，再使用前者提升开发效率。
