什么是 LRU Cache？
LRU (Least Recently Used) 缓存是一种常用的缓存淘汰策略，当缓存满了需要删除数据时，优先删除最久未使用的数据。
核心思想
LRU Cache 需要同时满足两个要求：
- 快速访问：O(1) 时间复杂度的 get 和 put 操作
- 维护访问顺序：能够快速找到最久未使用的元素
数据结构设计
为了同时满足上述要求，我们使用 HashMap + 双向链表 的组合：
- HashMap：提供 O(1) 的查找速度
- 双向链表：维护元素的使用顺序，头部是最久未使用的，尾部是最近使用的
public class LRUCache {
private int capacity;
private Map<Integer, Node> cacheMap = new HashMap<>();
private DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
}
核心操作
1. GET 操作
public int get(int key) {
Node node = cacheMap.get(key);
if (node == null) {
return -1; // 未找到
} else {
// 将访问的节点移到链表尾部（标记为最近使用）
doubleLinkedList.moveToLast(node);
return node.value;
}
}
2. PUT 操作
public void put(int key, int value) {
Node newNode = doubleLinkedList.add(key, value);
Node existNode = cacheMap.get(key);
// 如果超过容量限制
if ((cacheMap.size() + 1) > capacity && !cacheMap.isEmpty()) {
if (existNode != null) {
// 更新已存在的键
doubleLinkedList.removeNode(existNode);
} else {
// 删除最久未使用的元素（链表头部）
Node removeNode = doubleLinkedList.removeHeadNode();
cacheMap.remove(removeNode.key);
}
} else {
// 容量未满，但键已存在，需要更新
if (existNode != null) {
doubleLinkedList.removeNode(existNode);
}
}
// 存放新元素
cacheMap.put(key, newNode);
}
双向链表实现
节点结构
public class Node {
int key;
int value;
Node next;
Node prev;
}
关键方法：移动到链表尾部
public void moveToLast(Node node) {
if (node.next == null) {
return; // 已经是尾节点
}
if (node.prev == null) {
// 头节点情况
node.next.prev = null;
head = node.next;
} else {
// 中间节点情况
node.prev.next = node.next;
node.next.prev = node.prev;
}
// 移动到尾部
tail.next = node;
node.prev = tail;
tail = node;
node.next = null;
}
测试示例
LRUCache cache = new LRUCache(2);
cache.put(1, 1); // 缓存: {1=1}
cache.put(2, 2); // 缓存: {1=1, 2=2}
cache.get(1); // 返回 1，缓存: {2=2, 1=1}
cache.put(3, 3); // 移除 key 2，缓存: {1=1, 3=3}
cache.get(2); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(1); // 返回 1
关键要点
- 双向链表：能够快速删除中间节点
- HashMap存储节点引用：实现 O(1) 查找
- 尾插法：新元素和最近访问的元素都放在链表尾部
- 头删法：容量满时删除链表头部的最久未使用元素
时间复杂度
- GET 操作：O(1)
- PUT 操作：O(1)
- 空间复杂度：O(capacity)
完整代码
public class LRUCache {
// 容量
int capacity;
// 缓存 Map
Map<Integer, DoubleLinkedList.Node> cacheMap = new HashMap<>();
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
// 1. 查找元素
DoubleLinkedList.Node valueNode = cacheMap.get(key);
// 1.1 没找到元素的情况
if (Objects.isNull(valueNode)) {
return -1;
} else {
// 1.2 找到元素的情况
// 更新双向链表中节点的顺序
doubleLinkedList.moveToLast(valueNode);
return valueNode.value;
}
}
public void put(int key, int value) {
DoubleLinkedList.Node newNode = doubleLinkedList.add(key, value);
DoubleLinkedList.Node existNode = cacheMap.get(key);
// 超过容量限制
if ((cacheMap.size() + 1) > capacity && !cacheMap.isEmpty()) {
// Map key 重复的情况
if (!Objects.isNull(existNode)) {
doubleLinkedList.removeNode(existNode);
} else {
// 剔除最长未使用的元素，放入新元素
DoubleLinkedList.Node removeNode = doubleLinkedList.removeHeadNode();
// 移除最老未使用的元素
cacheMap.remove(removeNode.key);
}
} else {
// Map key 重复的情况
if (!Objects.isNull(existNode)) {
// 剔除指定的 existNode 元素
doubleLinkedList.removeNode(existNode);
}
}
// 存放新元素
cacheMap.put(key, newNode);
}
class DoubleLinkedList {
// 头节点指针
DoubleLinkedList.Node head;
// 尾节点指针
DoubleLinkedList.Node tail;
public void printList() {
Node current = head;
System.out.print("链表顺序: ");
while (current != null) {
System.out.print(current.key);
if (current.next != null) {
System.out.print(" -> ");
}
current = current.next;
}
System.out.println();
}
/**
* 节点
*/
public class Node {
int key;
int value;
// 指向后一个节点指针
DoubleLinkedList.Node next;
// 指向钱一个节点指针
DoubleLinkedList.Node prev;
}
/**
* 添加元素(尾插法)
*/
public DoubleLinkedList.Node add(int key, int value) {
// 1. 空链表的情况
DoubleLinkedList.Node newNode = initNodeValue(key, value);
if (head == null) {
// 头节点指向当前节点
head = newNode;
// 尾节点指向当前节点
tail = newNode;
} else {
// 2. 非空链表的情况
// 节点指向新节点
tail.next = newNode;
// 新节点操作
newNode.prev = tail;
newNode.next = null;
// 尾节点指向新的节点
tail = newNode;
}
return newNode;
}
/**
* 双向链表移除第一个节点
*/
public DoubleLinkedList.Node removeHeadNode() {
// 空链表
if (head == null) {
return null;
}
// 记录保存第一个节点
DoubleLinkedList.Node firstNode = head;
// 只有一个节点的情况
if (head == tail) {
// 把这个节点清理掉
head = null;
tail = null;
} else {
// 第二个节点当头节点啦
head.next.prev = null;
// head 指向第二个节点
head = head.next;
}
// 第一个节点断手断尾
firstNode.prev = null;
firstNode.next = null;
return firstNode;
}
/**
* 双向链表移除最后一个节点
*/
public DoubleLinkedList.Node removeTailNode() {
// 空链表
if (head == null) {
return null;
}
// 记录保存最后一个节点
DoubleLinkedList.Node oldLastNode = tail;
// 只有一个节点的情况
if (head == tail) {
// 把这个节点清理掉
head = null;
tail = null;
} else {
// 多个节点的情况
// tail 指向前一个节点
tail = tail.prev;
// 断开尾节点
tail.next = null;
}
oldLastNode.prev = null;
oldLastNode.next = null;
return oldLastNode;
}
/**
* 移除指定节点
*/
public void removeNode(Node node) {
if (node.prev == null) {
// 头节点的情况，移除头节点
removeHeadNode();
return;
}
if (node.next == null) {
// 尾节点的情况，移除尾节点
removeTailNode();
return;
}
// 断开当前 node 节点的前后指针
node.prev.next = node.next;
node.next.prev = node.prev;
// 断开当前的 node 节点，等着被垃圾回收器回收
node.prev = null;
node.next = null;
}
public void moveToLast(Node node) {
// 尾节点的情况
if (node.next == null) {
// 本次链表用的是尾插法，已经是尾了，不用再做操作啦
return;
}
// 首节点的情况
if (node.prev == null) {
// 下一个节点变为首节点
node.next.prev = null;
head = node.next;
// 当前节点移到最后，成为尾节点
tail.next = node;
node.prev = tail;
tail = node;
node.next = null;
return;
}
// 中间节点的情况
node.prev.next = node.next;
node.next.prev = node.prev;
tail.next = node;
node.prev = tail;
tail = node;
node.next = null;
}
private DoubleLinkedList.Node initNodeValue(int key, int value) {
DoubleLinkedList.Node node = new DoubleLinkedList.Node();
node.key = key;
node.value = value;
node.prev = null;
node.next = null;
return node;
}
}
}
总结
LRU Cache 的核心在于巧妙地结合 HashMap 和双向链表：
- HashMap 解决了快速查找的问题
- 双向链表解决了维护访问顺序的问题
- 通过将最近访问的元素移到链表尾部，最久未使用的元素自然就在链表头部
这种设计既保证了操作的高效性，又满足了 LRU 策略的需求。