146_LRU 缓存[MEDIUM]
约 590 字大约 2 分钟
2026-03-21
请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
需要满足:
- 初始化容量
- get方法,从缓存获取一个数
- put方法,将一个数放入缓存,如果已经存在,则更新值
- 如果缓存中的数超过容量,则删除最近最少使用的那个数
- 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行
解题思路
- 使用 HashMap + 双向链表 HashMap 用作哈希存取,双向链表用作最近使用排序(最近最多使用的在表头,最少使用的在表尾)
- 使用
dummyHead和dummyTail虚拟头尾,避免处理空指针 - 调用
get方法,将该节点移动到表头(先在原位置删除再在头部插入) - 调用
put方法,如果节点不存在,新增节点并移动到头部,如果容量超限,删除最末尾节点,并删除 hashMap 中的记录 - 双向链表 Node 必须同时存储 key 和 val , 因为当容量超限时,除了要删除表尾节点,还要删除它在 HashMap 中的记录,没有 key 将会无法删除
Java 实现
public class LRUCache {
class Node{
int key;
int val;
Node prev;
Node next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
public Node() {
}
}
Map<Integer, Node> cache = new HashMap<>();
private int capacity;
// 避免处理 null ,使用伪头部 (dummy head) 和 伪尾部 (dummy tail)
private Node dummyHead;
private Node dummyTail;
public LRUCache(int capacity) {
this.capacity = capacity;
dummyHead = new Node();
dummyTail = new Node();
dummyHead.next = dummyTail;
dummyTail.prev = dummyHead;
}
public int get(int key) {
Node node = cache.get(key);
if (node == null){
return -1;
}
removeNode(node);
moveToHead(node);
return node.val;
}
/**
* 删除节点,即节点的上一个节点接到原节点的下一个节点
*/
private void removeNode(Node node){
node.prev.next = node.next;
node.next.prev = node.prev;
}
/**
* 将节点移动到头部
*/
private void moveToHead(Node node){
// 节点移动到头部
node.next = dummyHead.next;
node.prev = dummyHead;
// 原头部调整
dummyHead.next.prev = node;
// dummy 调整
dummyHead.next = node;
}
public void put(int key, int value) {
Node node = cache.get(key);
// 如果节点不存在,新增节点并移动到头部
if (node == null){
node = new Node(key, value);
moveToHead(node);
cache.put(key, node);
// 如果容量超限,删除最末尾节点,并删除 hashMap 中的记录
if (cache.size() > capacity){
Node tail = dummyTail.prev;
cache.remove(tail.key);
removeNode(tail);
}
}
// 如果节点存在,更新值并移动到头部
node.val = value;
removeNode(node);
moveToHead(node);
}
}