乐趣区

关于算法:如何实现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 算法的思维和实现了,很容易犯错的一点是:解决链表节点的同时不要忘了更新哈希表中对节点的映射。

退出移动版