文章目录
- 题目
- 代码
- 原理图
- 原理解释
- 小结
题目
链表：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) 的平均时间复杂度运行。
示例：
输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put
代码
class LRUCache {int capacity_;list<int> keyList_;unordered_map<int,pair<int,list<int>::iterator>>hashMap_; void insert(int key,int value){keyList_.push_back(key);//将键插入到链表末尾hashMap_[key]=make_pair(value,--keyList_.end());//根据键，将对应的值和指向链表中该key的位置的迭代器}
public:LRUCache(int capacity) {//构造函数用来做初始化capacity_=capacity;}int get(int key) {//根据键获取对应的值auto it=hashMap_.find(key); // 在无序映射 hashMap_ 中查找键 keyif(it!=hashMap_.end())//{keyList_.erase(it->second.second);//删除链表中的键对应的节点keyList_.push_back(key);//将key放入链表的最后hashMap_[key].second=(--keyList_.end());//将指向链表中key位置的迭代器更新为链表中新插入节点的位置return it->second.first;//返回键所对应的值}return -1;}void put(int key, int value) {if(get(key)!=-1)//若key存在在hashmap中{hashMap_[key].first=value;//直接更新key对应的值return;}if(hashMap_.size()<capacity_)//若hashmap所存在键值对个数小于缓存容量{insert(key,value);//则直接插入键值对}else{//否则删除链表的头一个节点，并且把hashmap中的键值对也删除，然后在最后插入新的键值对int removeKey=keyList_.front();keyList_.pop_front();hashMap_.erase(removeKey);insert(key,value);}}
};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj = new LRUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/
原理图
原理解释
提示：算法流程及解释在代码中已标注
如原理图的例子所示：
①若想要插入的节点不在hashmap中，直接插入节点，在list中插入key，在hashmap中插入key以及value
②若想要插入的节点已经在hashmap中，删除在list中的key节点，插入到list之后，并更细key在hashmap中的值
③若缓存容量已满，则删除链表的头结点key，并将hashmap中key的键值对删除，并加入新的键值对，并且在list后插入新的key节点。
小结
LRU（Least Recently Used）是一种常见的缓存淘汰算法，其基本思想是通过记录每个缓存数据项的访问时间，当缓存空间满时，淘汰最近最少被访问的数据项。下面是一个简单的LRU缓存算法的小结：
-
数据结构：通常使用双向链表和哈希表来实现LRU缓存。双向链表用于记录数据项的访问顺序，哈希表用于快速查找数据项。
-
数据插入：当新的数据项被访问时，如果该数据项已经存在于缓存中，则将其移动到链表头部（表示最近被访问），并更新哈希表中的位置；如果该数据项不存在于缓存中，需要先判断缓存是否已满，若未满，则直接将数据插入到链表头部和哈希表中；若缓存已满，则需要淘汰链表尾部的数据项，再插入新的数据项。
-
数据访问：当访问缓存中的数据项时，需要将该数据项移动到链表头部，并更新其在哈希表中的位置。
-
缓存淘汰：当缓存空间不足时，需要淘汰最近最少被访问的数据项，即链表尾部的数据项，同时从链表和哈希表中删除该数据项。
-
时间复杂度：LRU算法的时间复杂度主要集中在查找和插入操作上，查找和删除操作可以在常数时间内完成，插入操作的时间复杂度为O(1)。
总的来说，LRU缓存算法通过维护访问顺序，使得缓存中的数据项始终保持最近被访问的状态，提高了缓存的命中率，同时保持了缓存的高效性。
