算法必知 --- LRU缓存淘汰算法
2021-06-20 本文已影响0人
_code_x
写在前
就是一种缓存淘汰策略。
计算机的缓存容量有限，如果缓存满了就要删除一些内容，给新内容腾位置。但问题是，删除哪些内容呢？我们肯定希望删掉哪些没什么用的缓存，而把有用的数据继续留在缓存里，方便之后继续使用。那么，什么样的数据，我们判定为「有用的」的数据呢？
LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。
算法描述
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：
- LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
- int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
- void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
注意哦，get 和 put 方法必须都是 O(1) 的时间复杂度！
示例：
/* 缓存容量为 2 */
LRUCache cache = new LRUCache(2);
// 你可以把 cache 理解成一个队列
// 假设左边是队头，右边是队尾
// 最近使用的排在队头，久未使用的排在队尾
// 圆括号表示键值对 (key, val)
cache.put(1, 1);
// cache = [(1, 1)]
cache.put(2, 2);
// cache = [(2, 2), (1, 1)]
cache.get(1); // 返回 1
// cache = [(1, 1), (2, 2)]
// 解释：因为最近访问了键 1，所以提前至队头
// 返回键 1 对应的值 1
cache.put(3, 3);
// cache = [(3, 3), (1, 1)]
// 解释：缓存容量已满，需要删除内容空出位置
// 优先删除久未使用的数据，也就是队尾的数据
// 然后把新的数据插入队头
cache.get(2); // 返回 -1 (未找到)
// cache = [(3, 3), (1, 1)]
// 解释：cache 中不存在键为 2 的数据
cache.put(1, 4);
// cache = [(1, 4), (3, 3)]
// 解释：键 1 已存在，把原始值 1 覆盖为 4
// 不要忘了也要将键值对提前到队头
算法设计
分析上面的操作过程，要让 put 和 get 方法的时间复杂度为 O(1)，我们可以总结出 cache 这个数据结构必要的条件：查找快，插入快，删除快，有顺序之分。
因为显然 cache 必须有顺序之分，以区分最近使用的和久未使用的数据；而且我们要在 cache 中查找键是否已存在；如果容量满了要删除最后一个数据；每次访问还要把数据插入到队头。
那么，什么数据结构同时符合上述条件呢？哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表。
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
LRU 缓存算法的核心数据结构就是哈希链表：双向链表和哈希表的结合体。这个数据结构长这样：
思想很简单，就是借助哈希表赋予了链表快速查找的特性嘛：可以快速查找某个 key 是否存在缓存（链表）中，同时可以快速删除、添加节点。回想刚才的例子，这种数据结构是不是完美解决了 LRU 缓存的需求？
代码实现
- 首先定义双端链表类（包括数据和记录前驱/后继节点的指针）
class DLinkedNode {
int key;
int value;
DLinkedNode pre;
DLinkedNode next;
public DLinkedNode() {};
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
- 双向链表需要提供一些接口api，便于我们操作，主要就是链表的一些操作，画图理解！
private void addFirst(DLinkedNode node) {
node.pre = head;
node.next = head.next;
head.next.pre = node;
head.next = node;
}
private void moveToFirst(DLinkedNode node) {
remove(node);
addFirst(node);
}
private void remove(DLinkedNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
// 删除尾结点，并返回头节点
private DLinkedNode removeLast() {
DLinkedNode ans = tail.pre;
remove(ans);
return ans;
}
private int getSize() {
return size;
}
- 确定LRU缓存类的成员变量（链表长度、缓存容量和map映射等）和构造函数。注意：定义虚拟头尾结点便于在头部插入元素或者寻找尾部元素！并在构造函数初始化。
private Map<Integer, DLinkedNode> cache = new HashMap<>();
private int size;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.pre = head;
}
-
核心代码：get和put方法，都是先根据key获取这个映射，根据映射节点的情况（有无）进行操作。注意：
- get和put都在使用，所以数据要提前！
- put操作如果改变了双端链表长度（不是仅改变值），需要先判断是否达到最大容量！
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// 将该数据移到双端队列头部
moveToFirst(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node != null) {
// 如果存在key，先修改值，然后移动到头部
node.value = value;
moveToFirst(node);
} else {
// 如果key存在，先考虑是否超过容量限制
if (capacity == cache.size()) {
// 删除尾结点和hash表中对应的映射！
DLinkedNode tail = removeLast();
cache.remove(tail.key);
--size;
}
DLinkedNode newNode = new DLinkedNode(key, value);
// 建立映射，并更新双向链表头部
cache.put(key, newNode);
addFirst(newNode);
++size;
}
}
完整代码如下：
class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode pre;
DLinkedNode next;
public DLinkedNode() {};
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
private Map<Integer, DLinkedNode> cache = new HashMap<>();
private int size;
private int capacity;
// 虚拟头尾结点便于在头部插入元素或者寻找尾部元素！
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
// 使用伪头部和伪尾部节点
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.pre = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// 将该数据移到双端队列头部
moveToFirst(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node != null) {
// 如果存在key，先修改值，然后移动到头部
node.value = value;
moveToFirst(node);
} else {
// 如果key存在，先考虑是否超过容量限制
if (capacity == cache.size()) {
// 删除尾结点和hash表中对应的映射！
DLinkedNode tail = removeLast();
cache.remove(tail.key);
--size;
}
DLinkedNode newNode = new DLinkedNode(key, value);
// 建立映射，并更新双向链表头部
cache.put(key, newNode);
addFirst(newNode);
++size;
}
}
private void addFirst(DLinkedNode node) {
node.pre = head;
node.next = head.next;
head.next.pre = node;
head.next = node;
}
private void moveToFirst(DLinkedNode node) {
remove(node);
addFirst(node);
}
private void remove(DLinkedNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
// 删除尾结点，并返回头节点
private DLinkedNode removeLast() {
DLinkedNode ans = tail.pre;
remove(ans);
return ans;
}
private int getSize() {
return size;
}
}
总结与补充
- LRU缓存机制的核心：双向链表（保证元素有序，且能快速的插入和删除）+hash表（可以快速查询）
- 为什么使用双向链表？因为：对于删除操作，使用双向链表，我们可以在O(1)的时间复杂度下，找到被删除节点的前节点。
- 为什么要在链表中同时存键值，而不是只存值？因为：当缓存容量满了之后，我们不仅要在双向链表中删除最后一个节点（即最久没有使用的节点），还要把cache中映射到该节点的key删除，这个key只能有Node得到（即hash表不能通过值得到键）。
巨人的肩膀：
https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/
