🎄LRU（Least Recently Used）
🍭题目来源
Least Recently Used -> 最近最少使用的
🍭题目分析
❓一个LRU缓存结构中应该包含哪些内容？
（1）map映射表 -> 用于在O(1)的复杂度下访问缓存结构中某个Node元素
（2）capacity容量属性和size实际大小属性
（3）整个缓存结构是一个双向链表 这个双向链表有一个虚拟头结点和尾结点 缓存结构中的元素都能在map中找到
（4）正如上面所说 在实现LRU缓存结构的时候 需要自己定义一个双向链表结点
Node
❓要注意的实现思路？
（1）在get元素的时候 是从map中get而不是从双向链表中get 也就是说 双向链表维护的是使用的先后关系 而map维护是的缓存中所有结点的映射关系
（2）在set元素的时候 首先要检查其是否已经存在于缓存中
（2.1）如果已经存在则将其值更新并放置于链表的头部即可
（2.2）如果不存在则要检查链表是否已经满了
（2.2.1）如果链表未满 则将其放在链表的头部 并将其放入map即可
（2.2.2）如果链表已经满了 则先将位于链表尾部的元素从链表和map中移除 再把新的元素放置在链表的头部和map中
🍭实现过程
🎯Node双向链表结点实现
// 定义双向链表结点 存储缓存结构的数据
// 最后使用的Node放在链表的头部 最久未使用的结点放在链表的尾部
class Node {
int key; // key用于后面的map的key map中的value是整个Node结点
int val;
Node pre;
Node next;
public Node(int key, int val) {
this.key = key;
this.val = val;
this.pre = null;
this.next = null;
}
}
🎯解决方案
其中get和set方法会使用到takeOffAndInsertToHead和insertToHead方法 所以将后两个方法 先实现
public class Solution {
// 对Node进行键值映射
HashMap<Integer, Node> m; // 根据Node中的键获取Node -> O(1)复杂度
int capacity; // 缓存结构的最大容量
int size; // 缓存结构的实际存储大小
// 创建一个头结点和一个尾结点
Node head = new Node(-1, -1);
Node rear = new Node(-1, -1);
public Solution(int capacity) {
// write code here
this.capacity = capacity;
this.size = 0;
m = new HashMap<>();
// 初始化结点指向
head.next = rear;
rear.pre = head;
}
// [实现思路]
// 获取元素的时候 存在两种情况 [1] 不存在返回-1 [2] 存在返回并将结点挪到链表头部
public int get(int key) {
...
}
// set函数的实现思路
// 当key存在 则更新至 并将node放置头部
// 当key不存在 则插入 [1] 链表容量满 [2] 链表容量未满 (插入的时候直接插入到头部)
public void set(int key, int value) {
...
}
// 将元素移动到链表头
public void takeOffAndInsertToHead(Node node) {
if (node.pre == head) return; // node已经位于头部
// 移动之前 先将结点取出 -> takeOff
node.pre.next = node.next;
node.next.pre = node.pre;
// 然后 将结点放置在头部
insertToHead(node);
}
// 将元素插入到链表头部
public void insertToHead(Node node) {
// 四步操作
node.next = head.next;
node.pre = head;
head.next.pre = node;
head.next = node;
}
}
🎯get方法实现
get方法和set方法是LRU中最关键的两个方法 完全展现了LRU的核心实现 题目分析中已经详细描述过
// [实现思路]
// 获取元素的时候 存在两种情况 [1] 不存在返回-1 [2] 存在返回并将结点挪到链表头部
public int get(int key) {
// write code here
// 当元素不存在
if (m.get(key) == null) return -1; // 默认返回-1
else {
Node node = (Node) m.get(key);
// 并且将此元素移动到链表的头部
takeOffAndInsertToHead(node);
return node.val; // 返回key对应的val
}
}
🎯set方法实现
// set函数的实现思路
// 当key存在 则更新至 并将node放置头部
// 当key不存在 则插入 [1] 链表容量满 [2] 链表容量未满 (插入的时候直接插入到头部)
public void set(int key, int value) {
// 构建插入结点
Node newNode = new Node(key, value);
// write code here
if (m.get(key) == null) { // 元素不存在
// [1] 链表容量满 删除尾部元素 并插入元素到头部
if (size == capacity) {
// 删除尾部元素
Node delNode = rear.pre;
m.remove(delNode.key);
rear.pre.pre.next = rear; // 1->2->3
rear.pre = rear.pre.pre;
// 插入元素到头部
insertToHead(newNode);
// size不变
} else { // [2] 链表容量未满
// 插入元素到头部
insertToHead(newNode);
// size++
++size;
}
// 放入map集合
m.put(newNode.key, newNode);
} else { // 元素已经存在
// 先获取到结点
Node curNode = (Node) m.get(key);
// [1] 更新元素val
curNode.val = value;
// [2] 将元素挪到头部
takeOffAndInsertToHead(curNode);
}
}