Version: Next
146.LRU 缓存
难度中等1344收藏分享切换为英文接收动态反馈
运用你所掌握的数据结构，设计和实现一个 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 <= 30000 <= key <= 30000 <= value <= 104- 最多调用
3 * 104次get和put
哈希表 + 双向链表
提示
LRU 缓存的常见实现方式是 哈希表 + 双向链表
淘汰算法
List
用 List 存储最近经常访问的 key
- 将刚被访问的 key 插到 List 的一端
- 插到最前面、最后面都可以，此处就插入到最前面
- 在通过 get 方法访问数据时，就要刷新 List 以记录访问记录
- 需要遍历 List 找到 Key
- 需要把目标 Key 对应数据挪动到 List 的一端
- 以上操作在数组中都是 O(n)
因此使用双向链表
LRU Cache 设计
LRUCache 类
包含
- Map：一个 HashMap
- first：指向双向链表头节点，设置一个虚拟头节点
- Last：指向双向链表尾节点，设置一个虚拟尾结点
- capacity：容量
HashMap
- key：存放原始的 key
- value：不直接存储 value，而是存包含了 value 的链表节点
Node
链表节点
- Key：键
- Value：值
- Prev：指向双向链表上的前一个节点
- Next：指向双向链表上的后一个节点
淘汰算法
- 将最近刚被 get 方法访问过的 key - value 对应的节点，采用
头插法，查到虚拟头结点的后面，即所有有效节点的最前面 - Put 时，如果 key 已经存在，那么更新对应的 value，并将这个节点插入到最前面
- put 是，如果 key 不存在，删除双向链表中的尾结点，创建新节点，插入到最前面
public class _146LRU缓存 {
private Map<Integer, Node> map;
private int capacity;
private Node firstNode;
private Node lastNode;
public _146LRU缓存(int capacity) {
this.map = new HashMap<>(capacity);
this.capacity = capacity;
this.firstNode = new Node(); // 虚拟头节点
this.lastNode = new Node(); // 虚拟头节点
// 虚拟头结点的下一个是虚拟尾结点
this.firstNode.next = this.lastNode;
// 虚拟尾结点的前一个是虚拟头结点
this.lastNode.prev = this.firstNode;
}
public int get(int key) {
Node node = map.get(key);
if (node == null) return -1;
// 成功访问了，那么更新双向链表，头插法插到最前面
// 将节点从当前位置删除
removeNode(node);
// 将节点头插到虚拟头节点后面
addAfterFirstNode(node);
return node.value;
}
public void put(int key, int value) {
Node node = map.get(key);
if (node != null) {
node.value = value; // key 中已有值，就只是更新值
// 链表更新
removeNode(node);
addAfterFirstNode(node);
} else { // 添加新的键值对，占用数据结构空间
if (map.size() == capacity) { // 已满
// 淘汰最少使用的 键值对
// 移除最长时间未被访问的元素
// 它是虚拟尾结点的前一个节点
map.remove(lastNode.prev.key);
// 还要从双向链表中删除这个节点
removeNode(lastNode.prev);
}
// 构建新节点
Node newNode = new Node(key, value);
// 存储新键值对
map.put(key, newNode);
// 头插到双向链表头部
addAfterFirstNode(newNode);
}
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addAfterFirstNode(Node node) {
node.next = this.firstNode.next;
node.prev = this.firstNode;
this.firstNode.next.prev = node;
this.firstNode.next = node;
}
private static class Node {
public int key;
public int value;
public Node prev;
public Node next;
public Node() {
}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public static void main(String[] args) {
_146LRU缓存 cache = new _146LRU缓存(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println("cache.get(1) = " + cache.get(1));
cache.put(3, 3);
System.out.println("cache.get(2) = " + cache.get(2));
cache.put(4, 4);
System.out.println("cache.get(-1) = " + cache.get(-1));
System.out.println("cache.get(3) = " + cache.get(3));
System.out.println("cache.get(4) = " + cache.get(4));
}
}