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) 的平均时间复杂度运行。
思路
数据结构选择: 使用了两个主要数据结构 -
std::unordered_map
用于快速查找键的位置,以及std::list
用于存储键值对,保持它们的顺序。LRUCache类: 类中的私有成员包括缓存容量
capacity
、哈希表cacheMap
和双向链表lruList
。构造函数: 构造函数接受缓存容量作为参数,并初始化相应的数据结构。
get函数: 根据给定的键查找缓存中的值。如果存在,则将对应的键值对移到链表的前面,表示最近被访问。返回查找到的值,如果键不存在,返回-1。
put函数: 插入或更新缓存中的键值对。如果键已存在,更新其值并将其移到链表的前面。如果键不存在,检查缓存是否已满,如果满了,则删除最不常使用的元素。然后在链表的前面插入新的键值对,并在哈希表中记录位置。
整体思路是通过哈希表维护键在链表中的位置,通过双向链表维护键值对的顺序,以实现LRU缓存的基本功能。这确保了最近访问的元素始终位于链表的前面,而最不常使用的元素会被淘汰。
题解
class LRUCache {
private:
int capacity; // 缓存的容量
unordered_map<int, list<pair<int, int>>::iterator>
cacheMap; // 哈希表,用于快速查找元素在链表中的位置
list<pair<int, int>> lruList; // 双向链表,用于存储键值对,保持元素的顺序
public:
LRUCache(int capacity) { this->capacity = capacity; }
int get(int key) {
auto it = cacheMap.find(key);
if (it != cacheMap.end()) {
// 如果元素存在,将其移到链表的前面,表示最近被访问
lruList.splice(lruList.begin(), lruList, it->second);
return it->second->second; // 返回对应的值
}
return -1; // 如果元素不存在,返回-1
}
void put(int key, int value) {
auto it = cacheMap.find(key);
if (it != cacheMap.end()) {
// 如果键已存在,更新值,并将其移到链表的前面,表示最近被访问
it->second->second = value;
lruList.splice(lruList.begin(), lruList, it->second);
} else {
// 如果键不存在
if (lruList.size() == capacity) {
// 如果缓存达到容量上限,删除链表末尾的元素,即最不常使用的元素
int evictedKey = lruList.back().first;
cacheMap.erase(evictedKey); // 从哈希表中移除对应的位置信息
lruList.pop_back(); // 从链表末尾删除元素
}
// 将新元素插入到链表的前面
lruList.emplace_front(key, value);
cacheMap[key] = lruList.begin(); // 在哈希表中记录新元素的位置
}
}
};