146. LRU 缓存
4 min
题目
解法：哈希链表
思路
核心思想是结合哈希表与双向链表：哈希表提供 O(1) 的键值查找，双向链表维护元素的访问时间顺序。通过将最近访问的节点移动到链表头部，并在缓存满时淘汰尾部节点，实现高效的 LRU 策略。
该方法的正确性基于两个关键不变量：1) 哈希表始终保存所有缓存键到链表节点的映射，确保查找效率；2) 双向链表严格按访问时间从近到远排序，头部为最新访问，尾部为最久未访问。当执行 get 或 put 操作时，通过 splice 操作在 O(1) 时间内调整节点位置，不会破坏链表顺序性。淘汰时删除尾部节点正是移除最久未使用项，符合 LRU 定义。
- Step 1: 初始化缓存容量，创建空的哈希表和双向链表
- Step 2: get 操作时，通过哈希表查找 key，若不存在返回 -1
- Step 3: 若存在，使用 splice 将对应节点移动到链表头部，返回值
- Step 4: put 操作时，若 key 存在，更新值并将节点移动到头部
- Step 5: 若 key 不存在，检查容量，若满则删除尾部节点和对应哈希表项
- Step 6: 在链表头部插入新节点，并在哈希表中添加映射
复杂度
- 时间复杂度: 平均时间复杂度。哈希表查找/插入为 O(1)，链表的 splice、push_front、pop_back 操作均为 O(1)，整体操作无循环依赖。
- 空间复杂度: 。哈希表和双向链表各存储 capacity 个键值对，额外空间为常数级指针开销。
代码
#include <unordered_map>
#include <list>
using namespace std;
class LRUCache {
public:
int len;
list<pair<int, int>> ls;
// 关键点1：换成 unordered_map 才能实现平均 O(1)
unordered_map<int, list<pair<int, int>>::iterator> mp;
LRUCache(int capacity) : len(capacity) {}
int get(int key) {
if (mp.find(key) == mp.end()) return -1;
// 关键点2：使用 splice 实现真正的“节点瞬移”，不涉及内存申请释放
// 将 mp[key] 指向的节点移动到 ls.begin() 位置
ls.splice(ls.begin(), ls, mp[key]);
return mp[key]->second;
}
void put(int key, int value) {
if (mp.find(key) != mp.end()) {
#include <unordered_map>
#include <list>
using namespace std;
class LRUCache {
public:
int len;
list<pair<int, int>> ls;
// 关键点1：换成 unordered_map 才能实现平均 O(1)
unordered_map<int, list<pair<int, int>>::iterator> mp;
LRUCache(int capacity) : len(capacity) {}
int get(int key) {
if (mp.find(key) == mp.end()) return -1;
// 关键点2：使用 splice 实现真正的“节点瞬移”，不涉及内存申请释放
// 将 mp[key] 指向的节点移动到 ls.begin() 位置
ls.splice(ls.begin(), ls, mp[key]);
return mp[key]->second;
}
void put(int key, int value) {
if (mp.find(key) != mp.end()) {
// key 已存在，更新值
mp[key]->second = value;
// 移动到头部
ls.splice(ls.begin(), ls, mp[key]);
} else {
// key 不存在
if (ls.size() == len) {
// 满了，删除末尾
int oldKey = ls.back().first;
mp.erase(oldKey);
ls.pop_back();
}
// 插入新节点
ls.push_front({key, value});
mp[key] = ls.begin();
}
}
};