LRU缓存机制
题目： 146. LRU 缓存
请你设计并实现一个满足 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
LRU 缓存的核心是， 淘汰最久未使用的元素，因此常规思路是，每个缓存项携带最后访问时间， 然后在put 的时候如果满了，则把访问时间最早的元素给移除。
但是针对此题，有这样一项要求函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。，因此上述方案是不行的，因为上述操作无法做到o1。
针对O1操作，我们可以想到HashMap的查询是o1的， 双向链表的删除和新增是O1的，因此这个可以结合HashMap和双向链表。于是我们可以写出下面的代码：
class LRUCache {
int capacity;
Node head;
Node tail;
Map<Integer, Node> map = new HashMap<>();
static class Node {
Integer key;
Integer val;
Node next;
Node prev;
public Node(Integer key, Integer val, Node next, Node prev) {
this.key = key;
this.val = val;
this.next = next;
this.prev = prev;
}
}
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>(capacity);
}
public int get(int key) {
// 根据Key 查到链表的节点
Node node = map.get(key);
// 没查到
if (node == null) return -1;
// 将其移动到表头
delNode(node); // 删除操作
addToHead(node); // 添加到头部
return node.val;
}
public void put(int key, int value) {
Node node = map.get(key);
if (node == null) {
node = new Node(key, value, head, null);
} else {
node.val = value;
// 删除操作
delNode(node);
}
// 添加到头部
addToHead(node);
map.put(key, node);
// 超过了设计容量，需要移除最久没访问的，队尾的元素即使最久未访问的。
if (map.size() > capacity) {
// map 移除。防止被查询到
Node deleNode = map.remove(tail.key);
// 链表中彻底进行移除
delNode(deleNode);
}
}
private void addToHead(Node node) {
// 如果链表为空， 则表头和表尾均是node
if (head == null) {
tail = node;
head = node;
return;
}
// 添加到表头
node.next = head;
head.prev = node;
head = node;
head.prev = null;
}
private void delNode(Node node) {
// 下属两种情况可能都存在，当只有一个元素的时候既是表头又是表尾
if (node == head) head = head.next; // 如果删除的是表头
if (node == tail) tail = tail.prev; // 删除的是表尾
// 删除node元素
if (node.prev != null) {
node.prev.next = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
}
}
}
void main() {
LRUCache lruCache = new LRUCache(1);
lruCache.put(2, 1);
System.out.println("1=" + lruCache.get(2));
lruCache.put(3, 2);
System.out.println("-1=" + lruCache.get(2));
System.out.println("2=" + lruCache.get(3));
}
当然我们还可以给链表设定一个固定的表头和表尾，这样可以节省链表操作中对表头和表尾的判断。在空数据的情况下
表头 <-> 表尾。 有数据后 表头 <-> 1 <-> 2 <->表尾。
代码经过改动后如下：
class LRUCache {
int capacity;
Node head;
Node tail;
Map<Integer, Node> map = new HashMap<>();
static class Node {
Integer key;
Integer val;
Node next;
Node prev;
public Node(Integer key, Integer val, Node next, Node prev) {
this.key = key;
this.val = val;
this.next = next;
this.prev = prev;
}
}
public LRUCache(int capacity) {
this.capacity = capacity;
head = new Node(null, null, null, null);
tail = new Node(null, null, null, null);
head.next = tail;
tail.prev = head;
map = new HashMap<>(capacity);
}
public int get(int key) {
Node node = map.get(key);
if (node == null) return -1;
// 删除操作
delNode(node);
// 添加到头部
addToHead(node);
return node.val;
}
public void put(int key, int value) {
Node node = map.get(key);
if (node == null) {
node = new Node(key, value, head.next, head);
} else {
// 删除操作
node.val = value;
delNode(node);
}
// 添加到头部
addToHead(node);
map.put(key, node);
if (map.size() > capacity) {
// 删除队元素，此处取值tail.prev即是队尾元素
Node deleNode = map.remove(tail.prev.key);
delNode(deleNode);
}
}
private void addToHead(Node node) {
// 添加到表头
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void delNode(Node node) {
// 删除元素
node.prev.next = node.next;
node.next.prev = node.prev;
}
}
可以看到添加和删除的时候代码简洁很多，不需要进行判空处理。