问题背景
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity)以 正整数 作为容量 c a p a c i t y capacity capacity 初始化 LRU 缓存int get(int key)如果关键字 k e y key key 存在于缓存中，则返回关键字的值，否则返回 − 1 -1 −1。void put(int key, int value)如果关键字 k e y key key 已经存在，则变更其数据值 v a l u e value value；如果不存在，则向缓存中插入该组 k e y − v a l u e key - value key−value。如果插入操作导致关键字数量超过 c a p a c i t y capacity capacity，则应该 逐出 最久未使用的关键字。
函数get和put必须以 O ( 1 ) O(1) O(1) 的平均时间复杂度运行。
数据约束
- 1 ≤ c a p a c i t y ≤ 3000 1 \le capacity \le 3000 1≤capacity≤3000
- 0 ≤ k e y ≤ 10000 0 \le key \le 10000 0≤key≤10000
- 0 ≤ v a l u e ≤ 1 0 5 0 \le value \le 10 ^ 5 0≤value≤105
- 最多调用 2 ≤ 1 0 5 2 \le 10 ^ 5 2≤105 次
get和put
解题过程
数据结构设计题，以积累记忆为主。
LRU 是一种典型的页面淘汰策略，显然增删改的操作频率是比较高的，这应该用链表处理。这样一来，加入新页面的操作可以看作在链表头部插入，淘汰旧页面的操作可以看作删除链表的尾节点。
为了方便找到链表的尾节点，可以选择实现一个头尾循环的双向链表结构，这样一来，统一的头节点 d u m m y dummy dummy 的前一个节点就是尾节点。注意区别于一般的循环链表，这里双向链表是强调头尾节点的，而一般的循环链表最大的特征就是无所谓头尾，给定任意一个节点即可遍历整个链表。
还有一个问题，如果某个数据项已经存在，要求更新它的值和频率，也就是要将它的值更改为给定的新值并把这个节点移动到链表头部。但是在链表中按值查找的时间复杂度是 O ( N ) O(N) O(N) 量级的，不符合题目要求。为此，需要再引入查询效率为 O ( 1 ) O(1) O(1) 的哈希表。
综合来看，所有操作的时间复杂度是 O ( 1 ) O(1) O(1)，需要 O ( m i n ( p u t , c a p a c i t y ) ) O(min(put, capacity)) O(min(put,capacity)) 的额外空间（可能出现记录的页面数量少，没有达到过 c a p a c i t y capacity capacity 的情况）。
具体实现
class LRUCache {
// 自定义双向链表
private static class ListNode {
int key, value;
ListNode pre, next;
ListNode(int key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final ListNode dummy = new ListNode(0, 0);
private final Map<Integer, ListNode> map = new HashMap<>();
// 初始状态下头节点的前后指针指向自己
public LRUCache(int capacity) {
this.capacity = capacity;
dummy.pre = dummy;
dummy.next = dummy;
}
// 自己实现的方法一：双向链表的头插法
private void pushFront(ListNode node) {
node.pre = dummy; // 新节点的前驱是头节点
node.next = dummy.next; // 新节点的后继是之前头节点的后继
node.pre.next = node; // 新节点的前驱（就是头节点）的后继是新节点
node.next.pre = node; // 新节点的后继的前驱是新节点
}
// 自己实现的方法二：双向链表中删除某个节点
private void remove(ListNode node) {
node.pre.next = node.next; // 当前节点前驱的后继是当前节点的后继
node.next.pre = node.pre; // 当前节点后继的前驱是当前节点的前驱
}
// 自己实现的方法三：从哈希表中获取某个键对应的链表节点
private ListNode getNode(int key) {
// 该节点不存在则返回空
if(!map.containsKey(key)) {
return null;
}
// 存在则取出该节点，先删除，再从链表头部插入
ListNode node = map.get(key);
remove(node);
pushFront(node);
return node;
}
public void put(int key, int value) {
// 根据相应的键取数据项，若存在则更新它的值
ListNode node = getNode(key);
if(node != null) {
node.value = value;
return;
}
// 若相应的数据项不存在，那么新建节点，更新哈希表并从链表头部插入
node = new ListNode(key, value);
map.put(key, node);
pushFront(node);
// 维护的页面数量超过规定值，进行淘汰
if(map.size() > capacity) {
// 头节点的前驱就是要淘汰的尾节点
ListNode leastUsed = dummy.pre;
// 从哈希表和链表中移除
map.remove(leastUsed.key);
remove(leastUsed);
}
}
public int get(int key) {
ListNode node = getNode(key);
return node != null ? node.value : -1;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/