算法：leetcode_146_LRU 缓存
·
目录
0. 引言
面试官：我们来聊聊Redis吧, 数据库有1000万数据，Redis只能缓存20w数据，如何保证Redis中的数据都是热点数据？
猪咪：这个就要考虑Redis的缓存淘汰策略了, 推荐使用allkeys-Iru(挑选最近最少使用的数据淘汰)淘汰策略，这样留下来的都是经常访问的热点数据。
面试官：很好, 那你能够用Java设计一个LRU缓存吗？
猪咪：巴拉巴拉巴拉一顿写完。
面试官：同学你基础很棒哇, 你跟谁学的？
猪咪：面试官, 我跟一个博主bugMaker学的, 给你链接你看下：算法：leetcode_146_LRU 缓存-CSDN博客
1. 题目介绍
LRU：最近最久未使用, 使用包括(插入这个节点, 访问这个节点), 做了操作之后, 都要把这个节点放到最前面去。看文字看不懂就来看我的2.1 画图介绍各个操作。
2. 思路
2.1 画图介绍
假如这个缓存的capacity为4, 就是能放入4个节点。
每个节点包括两个值key和value， key是作为这个节点的id, 唯一标识， 我们可以把key抽象成我的爱妃, value是她的丫鬟。
对于put, 即插入操作：如果只是一味地插入, 而不get,可以看成队列：
如下所示, 从左往右, 依次插入1, 2, 3, 4：
别再继续了, 我们来宠幸一位爱妃吧, 我们来访问一个节点, 就来访问节点2吧：get(2), 我们可以得到它的value：2
此时节点2成为我的宠妃, 将他移动到最新的位置, 最左边：其他节点相对位置保持不变
此时我们来访问一个key为5的节点：get(5), 但是在缓存里面没找到, 因此只能返回-1。
此时我们来再插入一个节点5吧：put(5, 5), 此时节点1由于长久未得到我的宠爱, 将他打入冷宫, 再也不管了, 节点3成为最后一个(最久未使用)节点。
我们再来执行个put操作, put(2, 20)吧：
我们发现在缓存中有节点2的, 它原本的value是2, 我们给她换个丫鬟, 将key为2的节点的value更新为20。同时,因为刚刚又访问了节点2, 还是需要将她移动到最左边：
看完画图介绍, 这道题是否就清晰很多了, 接下来看看思路吧。
2.2 存储结构
你是否想到用一个链表来存储这些节点呢?
我们回顾一下题目的要求：函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
对于get操作, 我们访问完中间的某个节点, 如果从头节点开始往右边遍历, 这得是O(n)的时间复杂度, 我们想要一步到胃, 一下就查到任意一个节点。
对于put操作, 如果put的是一个不存在的节点, 直接最简单的头插法就行了, 但是如果put的是一个存在的节点, 又要一步到位地找到这个节点, 同时, 如果容量满了, 还要一步到位将最后一个节点给剔除。
2.2.1 HashMap
对于这两个操作, 最关键的地方就是一步到位，那我们可以考虑用一个map, key就是节点的key, value则是存储这整个节点, 这样就能根据key一下就找到你想要访问的那个节点了。
2.2.2 双向循环链表
但是当容量满了, 你如何一下就找到最后一个节点并删除呢？
那我们直接来个双向循环链表, 第一个节点的前驱节点pre不就是尾节点吗？
2.3 定义节点结构
Node是一个双向循环链表:
private static class Node {
int key, value;
Node pre, next;
Node(int k, int v) {
key = k;
value = v;
}
}2.4 整个缓存结构展示
比如缓存容量为4, 里面依次插入了1, 2, 3, 4节点。
其中节点-1为虚拟头节点, 方便避免头节点是否为空需要做的判断。
2.5 抽象出公共操作
这道题目只需要我们补充3个方法：构造函数, get()和put()。
先来构造函数吧：
2.5.1 构造函数
- 首先先定义好缓存的容量capacity
- 另外我们需要一个虚拟节点, 可以非常方便地避免头节点是否为空需要做的判断。为什么key和value都是-1, 因为题目要求正常节点的key和value都是>=0, -1可以作为特殊值区分。
- 还需要可以通过key快速找到节点的map。
构造函数则只需要根据传入参数, 初始化容量capacity。
另外比较重要的是, 由于整个链表结构是双向循环链表, 我们将虚拟头节点的前驱和后继节点先都指向自己, 便于后续的各种操作。
private final int capacity;
private final Node dummyNode = new Node(-1, -1); // 虚拟哨兵节点
private final Map<Integer, Node> keyToNode = new HashMap<>();// 便于根据key找到链表中的某个节点
// 构造函数 初始化 将虚拟节点头尾指向自身
public LRUCache(int capacity) {
this.capacity = capacity;
dummyNode.pre = dummyNode;
dummyNode.next = dummyNode;
}- 对于get操作和put操作, 我们首先都得尝试访问这个节点存不存在吧, 因此会有一个getNode()方法。
- 访问完节点之后, 肯定要把节点放到最前面去,这个操作需要两个步骤：先断开这个节点的前后链接, 然后放到头部去, 因此会有disconnect()方法和pushFront()方法。
2.5.2 getNode()
对于获取节点, 很明显就是通过map.get(key)：
没找到就返回空, 找到了就返回这个节点, 返回之前需要先断开链接, 再放到头部。
private Node getNode(int key) {
// 如果map里面没有这个节点 返回空
if (!keyToNode.containsKey(key)) {
return null;
}
Node node = keyToNode.get(key); // 根据key找到这个节点
disconnect(node); // 将节点与前后断开链接
pushFront(node); // 放到最前面
return node;
}2.5.3 disconnect()
// 将节点与前后断开链接
private void disconnect(Node node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}断开链接操作非常简单， 我们来一步一步做：
首先原来的缓存结构是：
比如我们要断开节点3的前后链接,
首先需要记录节点3的前后两个节点4和2：
// 获取节点3
Node node = keyToNode.get(3);
// 获取节点3的前后节点4和2
Node pre = node.pre;
Node next = node.next;接下来需要节点4的后继指针指向节点2, 同时节点2的前驱指针指向4。
这样他们正好无视了节点3。
pre.next = next;
next.pre = pre;简单写就是开头所示：
private void disconnect(Node node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}图示：
2.5.4 pushFront()
private void pushFront(Node node) {
node.pre = dummyNode; // node的前向指针指向虚拟头节点
node.next = dummyNode.next; // node的后向指针指向虚拟头节点的下一个节点 夹在两者之间
// 接下来更新node的前后两个节点的指向
node.pre.next = node; // 虚拟节点的后向指针指向 node
node.next.pre = node; // 原先在首位的节点的前向指针指向node 完成插入头部
}比如还是将节点3插入缓存吧, 对于前两步, 首先节点3是小三, 她不管虚拟头节点-1和头节点4,
直接将她的前后指针指向他们：
接着将虚拟头节点-1的后继指针指向节点3, 原真实头节点4的前驱指针指向节点3：
完毕后, 缓存结构如下：
2.6 补充核心函数
2.6.1 get()
这个太轻松了, 直接用刚刚写好的getNode()即可, 已经自动将这个节点放到头部去：
对于得到的节点node, 为空就返回-1, 不为空就返回对应的value。
public int get(int key) {
// 先用getNode 找到是否有这个节点 getNode会完成更新操作 即 先移除 再放进头部位置
Node node = getNode(key);
// 节点存在即返回其value
return node == null ? -1 : node.value;
}2.6.2 put()
put操作就麻烦很多了：
首先还是通过getNode得到需要访问的这个节点
如果不为空, 修改下节点的value值, 直接返回即可。
如果为空, 那麻烦就大了：
- new一个新节点
- 将节点放进map, 便于后续能够快速通过key找到这个新插入的节点。
- 将这个节点放到头部去。
- 判断是否超出容量, 没超出容量不用管。
- 如果超出容量：(1)找到尾部节点;(2)将它从map里面驱逐出去;(3)断开尾部节点的前后链接
public void put(int key, int value) {
// 先用getNode 找到是否有这个节点 getNode会完成更新操作 即 先移除 再放进头部位置
Node node = getNode(key);
// 如果这个节点存在
if (node != null) {
// 更新其value 并返回
node.value = value;
return;
}
// 节点不存在 这个node是新节点
node = new Node(key, value);
// 新节点加入map中
keyToNode.put(key, node);
// 并将新节点放到头部
pushFront(node);
// 如果超出容量
if (keyToNode.size() > capacity) {
// 找到链表的最后一个节点 其是虚拟头节点的前驱节点(双向循环链表)
Node tailNode = dummyNode.pre;
// map根据最后一个节点的key删除其节点
keyToNode.remove(tailNode.key);
// 并在链表中也移除她
disconnect(tailNode);
}
}2.7 打印函数(可忽略)
打印函数即是打印出这个缓存的大致结果, 主要是方便我们自己看缓存里面的节点顺序：
// 打印出来LRU的链表结构, 只是模拟打印出不重复的节点, 不代表链表真实结构
public void print() {
System.out.println("现在打印LRU链表: ");
Node cur = dummyNode.next;
System.out.print("dummy->");
while (cur != dummyNode) {
System.out.print(cur.value + "->");
cur = cur.next;
}
System.out.print("dummy\n");
System.out.println("----------------------------");
}3. 运行示例：
我这里完成了一个步骤就打印了一下看看, 方便自己理解问题：
宝宝们也来试试吧！
4. 完整代码：
我把打印函数和main函数也放进去了, 方便宝宝们打印示例。
提交的时候记得改类名、方法名嗷。
Java
public class Leetcode_146_LRUCache {
// 双向循环链表
private static class Node {
int key, value;
Node pre, next;
Node(int k, int v) {
key = k;
value = v;
}
}
private final int capacity;
private final Node dummyNode = new Node(-1, -1); // 虚拟哨兵节点
private final Map<Integer, Node> keyToNode = new HashMap<>();// 便于根据key找到链表中的某个节点
// 构造函数 初始化 将虚拟节点头尾指向自身
public Leetcode_146_LRUCache(int capacity) {
this.capacity = capacity;
dummyNode.pre = dummyNode;
dummyNode.next = dummyNode;
}
public int get(int key) {
// 先用getNode 找到是否有这个节点 getNode会完成更新操作 即 先移除 再放进头部位置
Node node = getNode(key);
// 节点存在即返回其value
return node == null ? -1 : node.value;
}
public void put(int key, int value) {
// 先用getNode 找到是否有这个节点 getNode会完成更新操作 即 先移除 再放进头部位置
Node node = getNode(key);
// 如果这个节点存在
if (node != null) {
// 更新其value 并返回
node.value = value;
return;
}
// 节点不存在 这个node是新节点
node = new Node(key, value);
// 新节点加入map中
keyToNode.put(key, node);
// 并将新节点放到头部
pushFront(node);
// 如果超出容量
if (keyToNode.size() > capacity) {
// 找到链表的最后一个节点 其是虚拟头节点的前驱节点(双向循环链表)
Node tailNode = dummyNode.pre;
// map根据最后一个节点的key删除其节点
keyToNode.remove(tailNode.key);
// 并在链表中也移除她
disconnect(tailNode);
}
}
private Node getNode(int key) {
// 如果map里面没有这个节点 返回空
if (!keyToNode.containsKey(key)) {
return null;
}
Node node = keyToNode.get(key); // 根据key找到这个节点
disconnect(node); // 将节点与前后断开链接
pushFront(node); // 放到最前面
return node;
}
// 将节点与前后断开链接
private void disconnect(Node node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
private void pushFront(Node node) {
node.pre = dummyNode; // node的前向指针指向虚拟头节点
node.next = dummyNode.next; // node的后向指针指向虚拟头节点的下一个节点 夹在两者之间
// 接下来更新node的前后两个节点的指向
node.pre.next = node; // 虚拟节点的后向指针指向 node
node.next.pre = node; // 原先在首位的节点的前向指针指向node 完成插入头部
}
// 打印出来LRU的链表结构, 只是模拟打印出不重复的节点, 不代表链表真实结构
public void print() {
System.out.println("现在打印LRU链表: ");
Node cur = dummyNode.next;
System.out.print("dummy->");
while (cur != dummyNode) {
System.out.print(cur.value + "->");
cur = cur.next;
}
System.out.print("dummy\n");
System.out.println("----------------------------");
}
private void test(){
// 获取节点3
Node node = keyToNode.get(3);
// 获取节点3的前后节点4和2
Node pre = node.pre;
Node next = node.next;
pre.next = next;
next.pre = pre;
}
public static void main(String[] args) {
Leetcode_146_LRUCache cache = new Leetcode_146_LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.print();
System.out.println(cache.get(1));
cache.print();
cache.put(3, 3);
cache.print();
System.out.println(cache.get(2));
cache.print();
cache.put(4, 4);
cache.print();
System.out.println(cache.get(1));
System.out.println(cache.get(3));
System.out.println(cache.get(4));
}
}C++
#include <iostream>
#include <unordered_map>
using namespace std;
class Leetcode_146_LRUCache {
// 双向循环链表
private:
struct Node {
int key, value;
Node *pre, *next;
Node(int k, int v) : key(k), value(v), pre(nullptr), next(nullptr) {}
};
int capacity;
Node *dummyNode = new Node(-1, -1); // 虚拟哨兵节点
unordered_map<int, Node*> keyToNode; // 便于根据key找到链表中的某个节点
public:
// 构造函数 初始化 将虚拟节点头尾指向自身
Leetcode_146_LRUCache(int capacity) : capacity(capacity) {
dummyNode->pre = dummyNode;
dummyNode->next = dummyNode;
}
int get(int key) {
// 先用getNode 找到是否有这个节点 getNode会完成更新操作 即 先移除 再放进头部位置
Node *node = getNode(key);
// 节点存在即返回其value
return node == nullptr ? -1 : node->value;
}
void put(int key, int value) {
// 先用getNode 找到是否有这个节点 getNode会完成更新操作 即 先移除 再放进头部位置
Node *node = getNode(key);
// 如果这个节点存在
if (node != nullptr) {
// 更新其value 并返回
node->value = value;
return;
}
// 节点不存在 这个node是新节点
node = new Node(key, value);
// 新节点加入map中
keyToNode[key] = node;
// 并将新节点放到头部
pushFront(node);
// 如果超出容量
if (keyToNode.size() > capacity) {
// 找到链表的最后一个节点 其是虚拟头节点的前驱节点(双向循环链表)
Node *tailNode = dummyNode->pre;
// map根据最后一个节点的key删除其节点
keyToNode.erase(tailNode->key);
// 并在链表中也移除她
disconnect(tailNode);
delete tailNode;
}
}
private:
Node* getNode(int key) {
// 如果map里面没有这个节点 返回空
if (keyToNode.find(key) == keyToNode.end()) {
return nullptr;
}
Node *node = keyToNode[key]; // 根据key找到这个节点
disconnect(node); // 将节点与前后断开链接
pushFront(node); // 放到最前面
return node;
}
// 将节点与前后断开链接
void disconnect(Node *node) {
node->pre->next = node->next;
node->next->pre = node->pre;
}
void pushFront(Node *node) {
node->pre = dummyNode; // node的前向指针指向虚拟头节点
node->next = dummyNode->next; // node的后向指针指向虚拟头节点的下一个节点 夹在两者之间
// 接下来更新node的前后两个节点的指向
node->pre->next = node; // 虚拟节点的后向指针指向 node
node->next->pre = node; // 原先在首位的节点的前向指针指向node 完成插入头部
}
public:
// 打印出来LRU的链表结构, 只是模拟打印出不重复的节点, 不代表链表真实结构
void print() {
cout << "现在打印LRU链表: " << endl;
Node *cur = dummyNode->next;
cout << "dummy->";
while (cur != dummyNode) {
cout << cur->value << "->";
cur = cur->next;
}
cout << "dummy" << endl;
cout << "----------------------------" << endl;
}
void test() {
// 获取节点3
Node *node = keyToNode[3];
// 获取节点3的前后节点4和2
Node *pre = node->pre;
Node *next = node->next;
pre->next = next;
next->pre = pre;
}
};
int main() {
Leetcode_146_LRUCache cache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.print();
cout << cache.get(1) << endl;
cache.print();
cache.put(3, 3);
cache.print();
cout << cache.get(2) << endl;
cache.print();
cache.put(4, 4);
cache.print();
cout << cache.get(1) << endl;
cout << cache.get(3) << endl;
cout << cache.get(4) << endl;
return 0;
}JS
class Leetcode_146_LRUCache {
// 双向循环链表
static Node = class {
constructor(k, v) {
this.key = k;
this.value = v;
this.pre = null;
this.next = null;
}
};
capacity;
dummyNode = new Leetcode_146_LRUCache.Node(-1, -1); // 虚拟哨兵节点
keyToNode = new Map(); // 便于根据key找到链表中的某个节点
// 构造函数 初始化 将虚拟节点头尾指向自身
constructor(capacity) {
this.capacity = capacity;
this.dummyNode.pre = this.dummyNode;
this.dummyNode.next = this.dummyNode;
}
get(key) {
// 先用getNode 找到是否有这个节点 getNode会完成更新操作 即 先移除 再放进头部位置
const node = this.getNode(key);
// 节点存在即返回其value
return node == null ? -1 : node.value;
}
put(key, value) {
// 先用getNode 找到是否有这个节点 getNode会完成更新操作 即 先移除 再放进头部位置
const node = this.getNode(key);
// 如果这个节点存在
if (node != null) {
// 更新其value 并返回
node.value = value;
return;
}
// 节点不存在 这个node是新节点
const newNode = new Leetcode_146_LRUCache.Node(key, value);
// 新节点加入map中
this.keyToNode.set(key, newNode);
// 并将新节点放到头部
this.pushFront(newNode);
// 如果超出容量
if (this.keyToNode.size > this.capacity) {
// 找到链表的最后一个节点 其是虚拟头节点的前驱节点(双向循环链表)
const tailNode = this.dummyNode.pre;
// map根据最后一个节点的key删除其节点
this.keyToNode.delete(tailNode.key);
// 并在链表中也移除她
this.disconnect(tailNode);
}
}
getNode(key) {
// 如果map里面没有这个节点 返回空
if (!this.keyToNode.has(key)) {
return null;
}
const node = this.keyToNode.get(key); // 根据key找到这个节点
this.disconnect(node); // 将节点与前后断开链接
this.pushFront(node); // 放到最前面
return node;
}
// 将节点与前后断开链接
disconnect(node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
pushFront(node) {
node.pre = this.dummyNode; // node的前向指针指向虚拟头节点
node.next = this.dummyNode.next; // node的后向指针指向虚拟头节点的下一个节点 夹在两者之间
// 接下来更新node的前后两个节点的指向
node.pre.next = node; // 虚拟节点的后向指针指向 node
node.next.pre = node; // 原先在首位的节点的前向指针指向node 完成插入头部
}
// 打印出来LRU的链表结构, 只是模拟打印出不重复的节点, 不代表链表真实结构
print() {
console.log("现在打印LRU链表: ");
let cur = this.dummyNode.next;
let str = "dummy->";
while (cur !== this.dummyNode) {
str += cur.value + "->";
cur = cur.next;
}
str += "dummy";
console.log(str);
console.log("----------------------------");
}
test() {
// 获取节点3
const node = this.keyToNode.get(3);
// 获取节点3的前后节点4和2
const pre = node.pre;
const next = node.next;
pre.next = next;
next.pre = pre;
}
}
// 测试
const cache = new Leetcode_146_LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.print();
console.log(cache.get(1));
cache.print();
cache.put(3, 3);
cache.print();
console.log(cache.get(2));
cache.print();
cache.put(4, 4);
cache.print();
console.log(cache.get(1));
console.log(cache.get(3));
console.log(cache.get(4));5. 致谢
感谢宝宝们看完这篇分享博客,
觉得我写的屎山代码有用的话, 点赞关注收藏么么哒！
刷到了没时间仔细看的收藏嘻嘻。
重铸Java荣光, 我辈义不容辞!
25届Java小登不定时分享学习笔记，即使已经入职也要继续保持学习哇, 让猪脑子能够保持清醒!
更多推荐
39
0- 0
已为社区贡献3条内容
所有评论(0)