关于算法:如何实现LRU算法

读完本文，你能够去力扣拿下如下题目：

146.LRU缓存机制

-----------

一、什么是 LRU 算法

就是一种缓存淘汰策略。

计算机的缓存容量无限，如果缓存满了就要删除一些内容，给新内容腾地位。但问题是，删除哪些内容呢？咱们必定心愿删掉哪些没什么用的缓存，而把有用的数据持续留在缓存里，不便之后持续应用。那么，什么样的数据，咱们断定为「有用的」的数据呢？

LRU 缓存淘汰算法就是一种罕用策略。LRU 的全称是 Least Recently Used，也就是说咱们认为最近应用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。

举个简略的例子，安卓手机都能够把软件放到后盾运行，比方我先后关上了「设置」「手机管家」「日历」，那么当初他们在后盾排列的程序是这样的：

然而这时候如果我拜访了一下「设置」界面，那么「设置」就会被提前到第一个，变成这样：

假如我的手机只容许我同时开 3 个应用程序，当初曾经满了。那么如果我新开了一个利用「时钟」，就必须敞开一个利用为「时钟」腾出一个地位，关那个呢？

依照 LRU 的策略，就关最底下的「手机管家」，因为那是最久未应用的，而后把新开的利用放到最下面：

当初你应该了解 LRU（Least Recently Used）策略了。当然还有其余缓存淘汰策略，比方不要按拜访的时序来淘汰，而是按拜访频率（LFU 策略）来淘汰等等，各有利用场景。本文解说 LRU 算法策略。

二、LRU 算法形容

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 对应的值 1cache.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 这个数据结构必要的条件：查找快，插入快，删除快，有程序之分。

因为显然 cache 必须有程序之分，以辨别最近应用的和久未应用的数据；而且咱们要在 cache 中查找键是否已存在；如果容量满了要删除最初一个数据；每次拜访还要把数据插入到队头。

那么，什么数据结构同时合乎上述条件呢？哈希表查找快，然而数据无固定程序；链表有程序之分，插入删除快，然而查找慢。所以联合一下，造成一种新的数据结构：哈希链表。

LRU 缓存算法的外围数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构长这样：

思维很简略，就是借助哈希表赋予了链表疾速查找的个性嘛：能够疾速查找某个 key 是否存在缓存（链表）中，同时能够疾速删除、增加节点。回忆方才的例子，这种数据结构是不是完满解决了 LRU 缓存的需要？

兴许读者会问，为什么要是双向链表，单链表行不行？另外，既然哈希表中曾经存了 key，为什么链表中还要存键值对呢，只存值不就行了？

想的时候都是问题，只有做的时候才有答案。这样设计的起因，必须等咱们亲自实现 LRU 算法之后能力了解，所以咱们开始看代码吧～

四、代码实现

很多编程语言都有内置的哈希链表或者相似 LRU 性能的库函数，然而为了帮大家了解算法的细节，咱们用 Java 本人造轮子实现一遍 LRU 算法。

首先，咱们把双链表的节点类写进去，为了简化，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 类型构建一个双链表，实现几个须要的 API（这些操作的工夫复杂度均为 O(1))：

class DoubleList {      // 在链表头部增加节点 x，工夫 O(1)    public void addFirst(Node x);    // 删除链表中的 x 节点（x 肯定存在）    // 因为是双链表且给的是指标 Node 节点，工夫 O(1)    public void remove(Node x);        // 删除链表中最初一个节点，并返回该节点，工夫 O(1)    public Node removeLast();        // 返回链表长度，工夫 O(1)    public int size();}

PS：这就是一般双向链表的实现，为了让读者集中精力了解 LRU 算法的逻辑，就省略链表的具体代码。

到这里就能答复方才“为什么必须要用双向链表”的问题了，因为咱们须要删除操作。删除一个节点不光要失去该节点自身的指针，也须要操作其前驱节点的指针，而双向链表能力反对间接查找前驱，保障操作的工夫复杂度 O(1)。

有了双向链表的实现，咱们只须要在 LRU 算法中把它和哈希表联合起来即可。咱们先把逻辑理分明：

// key 映射到 Node(key, val)HashMap<Integer, Node> map;// Node(k1, v1) <-> Node(k2, v2)...DoubleList cache;int get(int key) {    if (key 不存在) {        return -1;    } else {                将数据 (key, val) 提到结尾；        return val;    }}void put(int key, int val) {    Node x = new Node(key, val);    if (key 已存在) {        把旧的数据删除；        将新节点 x 插入到结尾；    } else {        if (cache 已满) {            删除链表的最初一个数据腾地位；            删除 map 中映射到该数据的键；        }         将新节点 x 插入到结尾；        map 中新建 key 对新节点 x 的映射；    }}

如果可能看懂上述逻辑，翻译成代码就很容易了解了：

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();    }        public int get(int key) {        if (!map.containsKey(key))            return -1;        int val = map.get(key).val;        // 利用 put 办法把该数据提前        put(key, val);        return val;    }        public void put(int key, int val) {        // 先把新节点 x 做进去        Node x = new Node(key, val);                if (map.containsKey(key)) {            // 删除旧的节点，新的插到头部            cache.remove(map.get(key));            cache.addFirst(x);            // 更新 map 中对应的数据            map.put(key, x);        } else {            if (cap == cache.size()) {                // 删除链表最初一个数据                Node last = cache.removeLast();                map.remove(last.key);            }            // 间接增加到头部            cache.addFirst(x);            map.put(key, x);        }    }}

这里就能答复之前的问答题“为什么要在链表中同时存储 key 和 val，而不是只存储 val”，留神这段代码：

if (cap == cache.size()) {    // 删除链表最初一个数据    Node last = cache.removeLast();    map.remove(last.key);}

当缓存容量已满，咱们不仅仅要删除最初一个 Node 节点，还要把 map 中映射到该节点的 key 同时删除，而这个 key 只能由 Node 失去。如果 Node 构造中只存储 val，那么咱们就无奈得悉 key 是什么，就无奈删除 map 中的键，造成谬误。

至此，你应该曾经把握 LRU 算法的思维和实现了，很容易犯错的一点是：解决链表节点的同时不要忘了更新哈希表中对节点的映射。