题解：https://leetcode.cn/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/

文章目录

• • [146. LRU 缓存](https://leetcode.cn/problems/lru-cache/)
  • • 思路
    • 从0开始实现
    • 使用LinkedHashMap实现
  • 拓展：[460. LFU 缓存](https://leetcode.cn/problems/lfu-cache/)

146. LRU 缓存

难度中等2596

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 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

思路

题解：https://leetcode.cn/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/

要让 put 和 get 方法的时间复杂度为 O(1)，我们可以总结出 cache 这个数据结构必要的条件：

1、显然 cache 中的元素必须有时序，以区分最近使用的和久未使用的数据，当容量满了之后要删除最久未使用的那个元素腾位置。

2、我们要在 cache 中快速找某个 key 是否已存在并得到对应的 val；

3、每次访问 cache 中的某个 key，需要将这个元素变为最近使用的，也就是说 cache 要支持在任意位置快速插入和删除元素。

那么，什么数据结构同时符合上述条件呢？哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表 LinkedHashMap。

借助这个结构，我们来逐一分析上面的 3 个条件：

1、如果我们每次默认从链表尾部添加元素，那么显然越靠尾部的元素就是最近使用的，越靠头部的元素就是最久未使用的。

2、对于某一个 key，我们可以通过哈希表快速定位到链表中的节点，从而取得对应 val。

3、链表显然是支持在任意位置快速插入和删除的，改改指针就行。只不过传统的链表无法按照索引快速访问某一个位置的元素，而这里借助哈希表，可以通过 key 快速映射到任意一个链表节点，然后进行插入和删除。

也许读者会问，为什么要是双向链表，单链表行不行？另外，既然哈希表中已经存了 key，为什么链表中还要存 key 和 val 呢，只存 val 不就行了？

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

从0开始实现

注意我们实现的双链表 API 只能从尾部插入，也就是说靠尾部的数据是最近使用的，靠头部的数据是最久为使用的。

class LRUCache {// key -> Node(key, val)private HashMap 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;}// 将该数据提升为最近使用的makeRecently(key);return map.get(key).val;}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);
}//  删除某个 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 中删除它的 keyint deletedKey = deletedNode.key;map.remove(deletedKey);}
}class Node {public int key, val;public Node next, prev;public Node(int k, int v) {this.key = k;this.val = v;}
}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; }}

使用LinkedHashMap实现

class LRUCache {int cap;LinkedHashMap 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 value) {if(cache.containsKey(key)){// 修改 key 的值cache.put(key, value);// 将 key 变为最近使用makeRecently(key);return;}if(cache.size() >= this.cap){// 链表头部就是最久未使用的 keyint oldestKey = cache.keySet().iterator().next();cache.remove(oldestKey);}// 将新的 key 添加链表尾部cache.put(key, value);}public void makeRecently(int key){int val = cache.get(key);cache.remove(key);cache.put(key, val);}
}

拓展：460. LFU 缓存