LRU 策略详解和实现
关注 TA
[
labuladongL6
](https://leetcode.cn/u/labulad…) 公布于 2019-07-06130.3kC++Javacpp
读完本文，你不仅学会了算法套路，还能够顺便去 LeetCode 上拿下如下题目：
146. LRU 缓存机制（中等）
———–
LRU 算法就是一种缓存淘汰策略，原理不难，然而面试中写出没有 bug 的算法比拟有技巧，须要对数据结构进行层层形象和拆解，本文就带你写一手丑陋的代码。
计算机的缓存容量无限，如果缓存满了就要删除一些内容，给新内容腾地位。但问题是，删除哪些内容呢？咱们必定心愿删掉哪些没什么用的缓存，而把有用的数据持续留在缓存里，不便之后持续应用。那么，什么样的数据，咱们断定为「有用的」的数据呢？
LRU 缓存淘汰算法就是一种罕用策略。LRU 的全称是 Least Recently Used，也就是说咱们认为最近应用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。
举个简略的例子，安卓手机都能够把软件放到后盾运行，比方我先后关上了「设置」「手机管家」「日历」，那么当初他们在后盾排列的程序是这样的：
然而这时候如果我拜访了一下「设置」界面，那么「设置」就会被提前到第一个，变成这样：
假如我的手机只容许我同时开 3 个应用程序，当初曾经满了。那么如果我新开了一个利用「时钟」，就必须敞开一个利用为「时钟」腾出一个地位，关那个呢？
依照 LRU 的策略，就关最底下的「手机管家」，因为那是最久未应用的，而后把新开的利用放到最下面：
当初你应该了解 LRU（Least Recently Used）策略了。当然还有其余缓存淘汰策略，比方不要按拜访的时序来淘汰，而是按拜访频率（LFU 策略）来淘汰等等，各有利用场景。本文解说 LRU 算法策略。
[](#) 一、LRU 算法形容
力扣第 146 题「LRU 缓存机制」就是让你设计数据结构：
首先要接管一个 capacity 参数作为缓存的最大容量，而后实现两个 API，一个是 put(key, val) 办法存入键值对，另一个是 get(key) 办法获取 key 对应的 val，如果 key 不存在则返回 -1。
留神哦，get 和 put 办法必须都是 O(1) 的工夫复杂度，咱们举个具体例子来看看 LRU 算法怎么工作。
/* 缓存容量为 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 // 不要忘了也要将键值对提前到队头
[](#) 二、LRU 算法设计
剖析下面的操作过程，要让 put 和 get 办法的工夫复杂度为 O(1)，咱们能够总结出 cache 这个数据结构必要的条件：
1、显然 cache 中的元素必须有时序，以辨别最近应用的和久未应用的数据，当容量满了之后要删除最久未应用的那个元素腾地位。
2、咱们要在 cache 中疾速找某个 key 是否已存在并失去对应的 val；
3、每次拜访 cache 中的某个 key，须要将这个元素变为最近应用的，也就是说 cache 要反对在任意地位疾速插入和删除元素。
那么，什么数据结构同时合乎上述条件呢？哈希表查找快，然而数据无固定程序；链表有程序之分，插入删除快，然而查找慢。所以联合一下，造成一种新的数据结构：哈希链表 LinkedHashMap。
LRU 缓存算法的外围数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构长这样：
借助这个构造，咱们来逐个剖析下面的 3 个条件：
1、如果咱们每次默认从链表尾部增加元素，那么显然越靠尾部的元素就是最近应用的，越靠头部的元素就是最久未应用的。
2、对于某一个 key，咱们能够通过哈希表疾速定位到链表中的节点，从而获得对应 val。
3、链表显然是反对在任意地位疾速插入和删除的，改改指针就行。只不过传统的链表无奈依照索引快速访问某一个地位的元素，而这里借助哈希表，能够通过 key 疾速映射到任意一个链表节点，而后进行插入和删除。
兴许读者会问，为什么要是双向链表，单链表行不行？另外，既然哈希表中曾经存了 key，为什么链表中还要存 key 和 val 呢，只存 val 不就行了 ？
想的时候都是问题，只有做的时候才有答案。这样设计的起因，必须等咱们亲自实现 LRU 算法之后能力了解，所以咱们开始看代码吧～
[](#) 三、代码实现
很多编程语言都有内置的哈希链表或者相似 LRU 性能的库函数，然而为了帮大家了解算法的细节，咱们先本人造轮子实现一遍 LRU 算法，而后再应用 Java 内置的 LinkedHashMap 来实现一遍。
首先，咱们把双链表的节点类写进去，为了简化，key 和 val 都认为是 int 类型：
class Node {public int key, val; public Node next, prev; public Node(int k, int v) {this.key = k; this.val = v;} }
而后依附咱们的 Node 类型构建一个双链表，实现几个 LRU 算法必须的 API：
class DoubleList {// 头尾虚节点 private Node head, tail; // 链表元素数 private int size; public DoubleList() {// 初始化双向链表的数据 head = new Node(0, 0); tail = new Node(0, 0); head.next = tail; tail.prev = head; size = 0; } // 在链表尾部增加节点 x，工夫 O(1) public void addLast(Node x) {x.prev = tail.prev; x.next = tail; tail.prev.next = x; tail.prev = x; size++;} // 删除链表中的 x 节点（x 肯定存在）// 因为是双链表且给的是指标 Node 节点，工夫 O(1) public void remove(Node x) {x.prev.next = x.next; x.next.prev = x.prev; size--;} // 删除链表中第一个节点，并返回该节点，工夫 O(1) public Node removeFirst() { if (head.next == tail) return null; Node first = head.next; remove(first); return first; } // 返回链表长度，工夫 O(1) public int size() { return size;} }
到这里就能答复方才「为什么必须要用双向链表」的问题了，因为咱们须要删除操作。删除一个节点不光要失去该节点自身的指针，也须要操作其前驱节点的指针，而双向链表能力反对间接查找前驱，保障操作的工夫复杂度 O(1)。
留神咱们实现的双链表 API 只能从尾部插入，也就是说靠尾部的数据是最近应用的，靠头部的数据是最久为应用的 。
有了双向链表的实现，咱们只须要在 LRU 算法中把它和哈希表联合起来即可，先搭出代码框架：
class LRUCache {// key -> Node(key, val) private HashMap<Integer, Node> map; // Node(k1, v1) <-> Node(k2, v2)... private DoubleList cache; // 最大容量 private int cap; public LRUCache(int capacity) {this.cap = capacity; map = new HashMap<>(); cache = new DoubleList();}
先不慌去实现 LRU 算法的 get 和 put 办法。因为咱们要同时保护一个双链表 cache 和一个哈希表 map，很容易漏掉一些操作，比如说删除某个 key 时，在 cache 中删除了对应的 Node，然而却遗记在 map 中删除 key。
解决这种问题的无效办法是：在这两种数据结构之上提供一层形象 API。
说的有点玄幻，实际上很简略，就是尽量让 LRU 的主办法 get 和 put 防止间接操作 map 和 cache 的细节。咱们能够先实现上面几个函数：
/* 将某个 key 晋升为最近应用的 */ private void makeRecently(int key) {Node x = map.get(key); // 先从链表中删除这个节点 cache.remove(x); // 从新插到队尾 cache.addLast(x); } /* 增加最近应用的元素 */ private void addRecently(int key, int val) {Node x = new Node(key, val); // 链表尾部就是最近应用的元素 cache.addLast(x); // 别忘了在 map 中增加 key 的映射 map.put(key, x); } /* 删除某一个 key */ private void deleteKey(int key) {Node x = map.get(key); // 从链表中删除 cache.remove(x); // 从 map 中删除 map.remove(key); } /* 删除最久未应用的元素 */ private void removeLeastRecently() { // 链表头部的第一个元素就是最久未应用的 Node deletedNode = cache.removeFirst(); // 同时别忘了从 map 中删除它的 key int deletedKey = deletedNode.key; map.remove(deletedKey); }
这里就能答复之前的问答题「为什么要在链表中同时存储 key 和 val，而不是只存储 val」，留神 removeLeastRecently 函数中，咱们须要用 deletedNode 失去 deletedKey。
也就是说，当缓存容量已满，咱们不仅仅要删除最初一个 Node 节点，还要把 map 中映射到该节点的 key 同时删除，而这个 key 只能由 Node 失去。如果 Node 构造中只存储 val，那么咱们就无奈得悉 key 是什么，就无奈删除 map 中的键，造成谬误。
上述办法就是简略的操作封装，调用这些函数能够防止间接操作 cache 链表和 map 哈希表，上面我先来实现 LRU 算法的 get 办法：
public int get(int key) {if (!map.containsKey(key)) {return -1;} // 将该数据晋升为最近应用的 makeRecently(key); return map.get(key).val; }
put 办法略微简单一些，咱们先来画个图搞清楚它的逻辑：
这样咱们能够轻松写出 put 办法的代码：
public void put(int key, int val) {if (map.containsKey(key)) {// 删除旧的数据 deleteKey(key); // 新插入的数据为最近应用的数据 addRecently(key, val); return; } if (cap == cache.size()) {// 删除最久未应用的元素 removeLeastRecently(); } // 增加为最近应用的元素 addRecently(key, val); }
至此，你应该曾经齐全把握 LRU 算法的原理和实现了，咱们最初用 Java 的内置类型 LinkedHashMap 来实现 LRU 算法，逻辑和之前完全一致，我就不过多解释了：
class LRUCache {int cap; LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>(); public LRUCache(int capacity) {this.cap = capacity;} public int get(int key) {if (!cache.containsKey(key)) {return -1;} // 将 key 变为最近应用 makeRecently(key); return cache.get(key); } public void put(int key, int val) {if (cache.containsKey(key)) {// 批改 key 的值 cache.put(key, val); // 将 key 变为最近应用 makeRecently(key); return; } if (cache.size() >= this.cap) {// 链表头部就是最久未应用的 key int oldestKey = cache.keySet().iterator().next(); cache.remove(oldestKey); } // 将新的 key 增加链表尾部 cache.put(key, val); } private void makeRecently(int key) {int val = cache.get(key); // 删除 key，从新插入到队尾 cache.remove(key); cache.put(key, val); } }