图解LRU缓存
OJ链接
介绍
LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
-
双向链表按照被使用的顺序存储了这些键值对，靠近尾部的键值对是最近使用的，而靠近头部的键值对是最久未使用的。
-
哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。
这样一来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的尾部，即可在O(1)的时间内完成 get 或者 put 操作。
先介绍两个常用函数：removeToTail(node)和add(node)，removeToTail(node)是在双向链表中，将使用过的node移到链表尾部，add(node)是往双向链表增加一个节点。
removeToTail(node)
add(node)
下面就是主要函数的介绍
get()
对于 get 操作，首先判断 key 是否存在：
-
如果 key 不存在，则返回 −1；
-
如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的尾部，最后返回该节点的值。
put()
对于 put 操作，首先判断 key 是否存在：
-
如果 key 不存在，使用 key 和 value 创建一个新的节点，将 key 和该节点添加进哈希表中，并在双向链表的尾部添加该节点。然后判断哈希表的节点数是否超出容量，如果超出容量，则删除哈希表中对应的项，并删除双向链表的头部节点；
-
如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将该节点移到双向链表的尾部，并将对应的节点的值更新为 value。
复杂度分析
上述各项操作中，访问哈希表的时间复杂度为 O(1)，在双向链表的尾部添加节点、在双向链表的头部删除节点的复杂度也为 O(1)。
代码
import java.util.HashMap;
public class $146 {
class Node {
int key;
int value;
Node prev;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
HashMap<Integer, Node> hashMap = new HashMap<>();
Node head = null;
Node tail = null;
int capacity;
public $146(int capacity) {
this.capacity = capacity;
}
//双向链表，将节点移动到tail后面，表示该节点是最近使用的
public void removeToTail(Node node) {
if (node == tail) {
} else if (node == head) {
tail.next = node;
node.prev = tail;
tail = tail.next;
head = head.next;
} else {
node.prev.next = node.next;
node.next.prev = node.prev;
tail.next = node;
node.prev = tail;
tail = tail.next;
}
}
//双向链表，增加某节点
public void add(Node node) {
if (tail == null) {
head = node;
tail = node;
} else {
tail.next = node;
node.prev = tail;
tail = tail.next;
}
}
public int get(int key) {
//1.哈希表不存在key，返回-1
if (!hashMap.containsKey(key)) {
return -1;
} else { //2.哈希表存在key，从哈希表中获得value，将key移到链表尾部
int res = hashMap.get(key).value;
removeToTail(hashMap.get(key));
return res;
}
}
public void put(int key, int value) {
//1.哈希表不存在key
if (!hashMap.containsKey(key)) {
//1.1创建新节点
Node node = new Node(key, value);
//1.2插入
//插入到哈希表
hashMap.put(key, node);
//插入到链表
add(node);
//1.3判断哈希表容量
if (hashMap.size() > capacity) {
//1.3.1删除
//哈希表删除链表头元素
hashMap.remove(head.key);
//链表删除头元素
// remove(head);
head = head.next;
}
} else { //2.哈希表存在key
//2.1更新
//更新链表，将key移到链表尾部
removeToTail(hashMap.get(key));
//更新哈希表，key对应的value
hashMap.get(key).value = value;
}
}
public static void main(String[] args) {
$146 a = new $146(4);
a.put(8,80);
a.put(9,90);
a.put(7,70);
a.put(6,60);
a.get(8);
a.get(7);
a.put(5,50);
}
// //双向链表，删除某节点
// public void remove(Node node) {
// // head = head.next;
// if (node == tail) {
// tail = tail.prev;
// } else if (node == head) { //均是头结点
// head = head.next;
// } else {
// node.prev.next = node.next;
// node.next.prev = node.prev;
// }
// }
}
