原文链接: https://leetcode-cn.com/problems/lru-cache

英文原文

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

 

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

 

Constraints:

• 1 <= capacity <= 3000
• 0 <= key <= 104
• 0 <= value <= 105
• At most 2 * 105 calls will be made to get and put.

中文题目

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。

实现 LRUCache 类：

• LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

 

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

 

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

 

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多调用 2 * 105 次 get 和 put

通过代码

高赞题解

读完本文，你不仅学会了算法套路，还可以顺便去 LeetCode 上拿下如下题目：

146.LRU缓存机制

———–

一、什么是 LRU 算法

就是一种缓存淘汰策略。

计算机的缓存容量有限，如果缓存满了就要删除一些内容，给新内容腾位置。但问题是，删除哪些内容呢？我们肯定希望删掉哪些没什么用的缓存，而把有用的数据继续留在缓存里，方便之后继续使用。那么，什么样的数据，我们判定为「有用的」的数据呢？

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

举个简单的例子，安卓手机都可以把软件放到后台运行，比如我先后打开了「设置」「手机管家」「日历」，那么现在他们在后台排列的顺序是这样的：

{:width=450}{:align=center}

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

{:width=450}{:align=center}

假设我的手机只允许我同时开 3 个应用程序，现在已经满了。那么如果我新开了一个应用「时钟」，就必须关闭一个应用为「时钟」腾出一个位置，关那个呢？

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

{:width=450}{:align=center}

现在你应该理解 LRU（Least Recently Used）策略了。当然还有其他缓存淘汰策略，比如不要按访问的时序来淘汰，而是按访问频率（LFU 策略）来淘汰等等，各有应用场景。本文讲解 LRU 算法策略。

PS：我认真写了 100 多篇题解，手把手带你刷力扣，全部发布在 LeetCode刷题套路，持续更新。建议收藏，先按照我的文章顺序刷题，掌握各种算法套路后投再入题海就如鱼得水了。

二、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 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构长这样：

{:width=450}{:align=center}

思想很简单，就是借助哈希表赋予了链表快速查找的特性嘛：可以快速查找某个 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 算法的思想和实现了，很容易犯错的一点是：处理链表节点的同时不要忘了更新哈希表中对节点的映射。

＿＿＿＿＿＿＿＿＿＿＿＿＿

点击 我的头像 看更多优质文章，。

统计信息

通过次数	提交次数	AC比率
254778	485538	52.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
LFU 缓存	困难
设计内存文件系统	困难
迭代压缩字符串	简单