关于算法:如何实现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 对应的值 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 这个数据结构必要的条件：查找快，插入快，删除快，有程序之分。

因为显然 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 算法的思维和实现了，很容易犯错的一点是：解决链表节点的同时不要忘了更新哈希表中对节点的映射。