146 LRU缓存
一、题目
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity)以 正整数 作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
二、题解
思路：哈希表 + 双向链表
- 哈希表：用于满足 的
get操作。键为key，值为对应的链表节点引用。 - 双向链表：用于维持数据的“新鲜度”，满足 的
put和剔除操作。- 将最近被访问（
get或put）的节点移动到链表头部 - 当缓存满时，链表尾部的节点就是“最近最少使用”的数据，直接剔除即可。
- 为什么用双向链表？ 因为在移动或删除节点时，我们需要知道该节点的前驱节点，单链表无法在 时间内完成。
- 将最近被访问（
import java.util.HashMap;
import java.util.Map;
class LRUCache {
// ==========================================
// 1. 定义双向链表的节点类
// ==========================================
class DLinkedNode {
int key; // 存储 key：当缓存满需要删除尾部节点时，我们要靠这里的 key 去删掉哈希表里的记录
int value;
DLinkedNode prev; // 指向前一个节点
DLinkedNode next; // 指向后一个节点
public DLinkedNode() {}
public DLinkedNode(int _key, int _value) {
key = _key;
value = _value;
}
}
// ==========================================
// 2. 成员变量定义
// ==========================================
// 哈希表：用于 O(1) 时间复杂度查找 key 对应的节点
private Map<Integer, DLinkedNode> cache = new HashMap<>();
// 记录当前缓存中的元素数量
private int size;
// 记录缓存的最大容量
private int capacity;
// 伪头部和伪尾部节点：
// 它们本身不存储真实数据，专门用来充当边界。
// 作用：在进行节点插入和删除时，保证被操作节点前后总是有节点，从而免去了繁琐的 null 判断。
private DLinkedNode head, tail;
// ==========================================
// 3. 构造函数：初始化 LRU 缓存
// ==========================================
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
// 初始化伪头部和伪尾部
head = new DLinkedNode();
tail = new DLinkedNode();
// 将伪头部和伪尾部连接起来，形成一个初始的空双向链表： head <-> tail
head.next = tail;
tail.prev = head;
}
// ==========================================
// 4. 获取数据 get
// ==========================================
public int get(int key) {
DLinkedNode node = cache.get(key);
// 如果哈希表中没有这个 key，说明缓存未命中，按题意返回 -1
if (node == null) {
return -1;
}
// 如果 key 存在（缓存命中）：
// 根据 LRU 策略，该数据刚刚被访问过，必须刷新它的"新鲜度"。
// 操作：将该节点从当前位置移出，并重新插入到链表的最头部。
moveToHead(node);
return node.value;
}
// ==========================================
// 5. 写入/更新数据 put
// ==========================================
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
// ---> 情况 A：key 不存在，需要插入全新数据
DLinkedNode newNode = new DLinkedNode(key, value);
// 1. 放入哈希表
cache.put(key, newNode);
// 2. 放入双向链表的最头部（代表最新使用）
addToHead(newNode);
// 3. 缓存当前元素个数 +1
++size;
// 4. 检查是否超出了最大容量
if (size > capacity) {
// 如果超载，需要淘汰“最近最少使用”的节点（即链表尾部的真实节点）
DLinkedNode tail = removeTail();
// 同步从哈希表中移除对应的键值对
cache.remove(tail.key);
// 缓存当前元素个数还原
--size;
}
} else {
// ---> 情况 B：key 已经存在，说明这是一次更新操作
// 1. 覆盖节点中的旧值
node.value = value;
// 2. 因为被访问/修改了，同样需要移动到链表头部，标记为“最新使用”
moveToHead(node);
}
}
// ==========================================
// 6. 辅助函数：底层双向链表操作 (封装起来让主逻辑清晰)
// ==========================================
/**
* 在链表头部（伪头节点之后）插入一个新节点
*/
private void addToHead(DLinkedNode node) {
// 先处理新节点自身的两根引线
node.prev = head;
node.next = head.next;
// 再处理原有节点指向新节点的引线（顺序不能错，否则会丢失原来的 head.next）
head.next.prev = node;
head.next = node;
}
/**
* 将一个节点从双向链表中彻底摘除
*/
private void removeNode(DLinkedNode node) {
// 让该节点的前驱节点和后继节点互相牵手，直接跳过当前 node
node.prev.next = node.next;
node.next.prev = node.prev;
}
/**
* 将一个已存在于链表中的节点移动到最头部
*/
private void moveToHead(DLinkedNode node) {
// 逻辑很简单：先把它从原位置删掉，再当作新节点插到头部
removeNode(node);
addToHead(node);
}
/**
* 弹出并返回链表尾部真正的节点（即准备要被淘汰的节点）
*/
private DLinkedNode removeTail() {
// 伪尾部节点(tail)的前一个节点，就是真正最久没被访问的那个节点
DLinkedNode res = tail.prev;
// 将其从链表中摘除
removeNode(res);
// 返回出去，主要是为了让上层拿到它的 key，从而清理哈希表
return res;
}
}时间复杂度：
空间复杂度：
评论