哈希表+双链表实现LRU缓存机制
将有下面四个问题待解决：
什么是LRU缓存机制？
为什么要用哈希表存？
为什么要用双链表，而不用队列？
如何实现？
什么是LRU缓存机制
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。
先把题目贴出来吧
为什么要用哈希表
因为很明显要用到键值对存key和value
为什么要用双链表而不用队列？
因为题目说，要在满足Cache满的时候将最久未使用过的关键字剔除，所以我一开始是打算用队列来实现的，只要容量满了就把队头元素中的key对应键值对删了（先进先出），但是题目说了 “删除最久未使用的关键字” ，关键点就在这,假设这个关键字是key，只要我们取出该元素，或者插入该元素，或者修改该元素就算使用过，这时候这个元素就不应该在队列的队头，而应该在队尾（刚使用过）。因此队列无法满足要求（wa一次: 8/22）；且题目要求在O(1)内完成，而双链表就能在O(1)的平均时间复杂度里执行各种操作。
下面开始实现
初见参考b站【LeetCode 每日一题】146. LRU 缓存 | 手写图解版思路 + 代码讲解_哔哩哔哩_bilibili
准备双链表
//双链表数据结构
struct Node{
int key, val;
Node *pre;
Node *next;
Node(): key(0),val(0),pre(NULL),next(NULL){}
Node(int _key,int _val): key(_key),val(_val),pre(NULL),next(NULL){}
};初始化哈希表和双链表
Node *head, *tail; //双链表虚拟头尾指针
unordered_map<int, Node*> cache;
int capacity, size; //最大容量，当前元素个数
LRUCache(int _capacity): capacity(_capacity),size(0){
head = new Node();
tail = new Node();
head->next = tail;
tail->pre = head;
}双链表删除节点以及插入节点到头部的操作
双链表这部分就不多说了，数据结构基础
//删除节点
void removeNode(Node *node){
node->pre->next = node->next;
node->next->pre = node->pre;
}
//将节点插到链表头部
void addToHead(Node* node){
node->pre = head;
node->next = head->next;
head->next->pre = node;
head->next = node;
}最后根据题目逻辑给出完整代码
注释很完整了
//双链表数据结构
struct Node{
int key, val;
Node *pre;
Node *next;
Node(): key(0),val(0),pre(NULL),next(NULL){}
Node(int _key,int _val): key(_key),val(_val),pre(NULL),next(NULL){}
};
class LRUCache {
public:
Node *head, *tail; //双链表虚拟头尾指针
unordered_map<int, Node*> cache;
int capacity, size; //最大容量，当前元素个数
LRUCache(int _capacity): capacity(_capacity),size(0){
head = new Node();
tail = new Node();
head->next = tail;
tail->pre = head;
}
int get(int key) {
//不存在该key键值对
if(!cache.count(key)) return -1;
//存在
Node *node = cache[key];
//取出后，算使用过，则更新其位置到链表头部
removeNode(node);
addToHead(node);
return node->val;
}
void put(int key, int value) {
if(cache.count(key)){
//存在key，则修改key对应的value，更新使用状态
Node* node = cache[key];
node->val = value;
removeNode(node);
addToHead(node);
}else {
//不存在，则插入一个新节点，且更新状态
//1.判断容量是否超过capacity,如果超了需要删去链表尾部元素还有哈希表的对应元素
if(size == capacity){
Node *removedNode = tail->pre;
removeNode(removedNode);
cache.erase(removedNode->key); //注意删的不是当前要插入的key！！（这里找了好久的bug，要删掉的是链表头部节点对应的key）
size--;
}
//2.未超过，则将新节点插入哈希表，且插入到链表
Node *node = new Node(key, value);
addToHead(node);
cache[key] = node;
size++;
}
}
//删除节点
void removeNode(Node *node){
node->pre->next = node->next;
node->next->pre = node->pre;
}
//将节点插到链表头部
void addToHead(Node* node){
node->pre = head;
node->next = head->next;
head->next->pre = node;
head->next = node;
}
};
/**
* 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);
*/JAVA 版本
public class LRUCache {
//双链表 从左往右使用减少
class DLinkedNode{
int key, val;
DLinkedNode pre;
DLinkedNode next;
public DLinkedNode(){}
public DLinkedNode(int _key, int _val) {
this.key = _key;
this.val = _val;
}
}
DLinkedNode tail, head; //双链表头指针和尾部指针
HashMap<Integer, DLinkedNode> cache = new HashMap<>();
int size; //当前元素数量
int capacity; //容量
//1.初始化
public LRUCache(int _capacity) {
this.capacity = _capacity;
this.size = 0;
tail = new DLinkedNode();
head = new DLinkedNode();
head.next = tail;
tail.pre = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if(node == null){
//不存在key
return -1;
}else {
//使用了该数，更新缓存
deleteNode(node);
addToHead(node);
}
return node.val;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
//如果存在，修改并更新缓存;
if(node != null){
node.val = value;
deleteNode(node);
addToHead(node);
}else {
//不存在
//1.判断容量 达到最大容量，删除最近未使用节点(别忘了cache也要删)
if(size == capacity){
DLinkedNode removeNode = tail.pre;
deleteNode(removeNode);
cache.remove(removeNode.key);
size--;
}
DLinkedNode newNode = new DLinkedNode(key, value);
size++;
addToHead(newNode);
cache.put(key, newNode);
}
}
//删除双链表中的节点
public void deleteNode(DLinkedNode node){
node.pre.next = node.next;
node.next.pre = node.pre;
}
//加入到链表头部
public void addToHead(DLinkedNode node){
node.pre = head;
node.next = head.next;
head.next.pre = node;
head.next = node;
}
}
/**
* 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);
*/
