运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
1
2
3
4
5
6
7
8
9
10
11
|
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
|
题解：
看到此题干中有，<key: value>键值对，最先想到哈希表，哈希表可以在 O(1) 的时间复杂度内，通过key找到 value.
此题可以通过哈希表 和 双向链表 解决。
- 使用虚拟头节点，虚拟尾节点
- 虚拟头节点 指向的元素是 最近使用的元素
- 虚拟尾节点指向的元素是 不长使用的
- put 操作
- 如果map中包含，则取出，value重新复制，map重新赋值, 并将此节点移动至头部
- 如果map中不包含，则重新创建，并加入头部
- 加入后，如果map的size > capacity ， 则尾部删除元素
- get 操作
- 如果map中不包含， 直接return -1
- 如果map中包含，则取出节点，并将此节点移动至头部
上述各项操作中, 哈希表取值时间复杂度为 O (1), 双向链表头部添加节点，尾部删除节点。 移动节点至头部，可以认为是 删除当前节点 + 在头部添加节点， 也是O(1)内完成
故上述操作，时间复杂度都是O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
/*
* 题目主要使用，哈希表，双向链表
* 使用虚拟头节点，虚拟尾节点
* 虚拟头节点指向的元素是最近使用的元素
* 虚拟尾节点指向的元素是最不常使用的元素
*
* put 时
* 如果 map 中包含， 则取出，value重新赋值， map重新赋值， 并将此节点移至头部
* 如果 map 中不包含，则重新创建, 加入头部
* 加入后，如果map的 size > capacity， 则尾部元素删除
*
* get 时
* 如果 map 中不包含，直接return -1
* 如果 map 中包含， 则取出节点，并将此节点移动至头部
* */
public class _146_LRU缓存机制 {
class DLinkedNode{
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode() {};
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
/*
*
* 关键字 : key, value对
* 模式识别 : 一旦出现 key , value 就要想到哈希表
* 改变数据的访问时间
* */
HashMap<Integer,DLinkedNode> map;
LinkedList list;
private int size;
private int capacity;
private DLinkedNode head, tail;
public _146_LRU缓存机制(int capacity) {
map = new HashMap<>();
list = new LinkedList();
this.capacity = capacity;
this.size = 0;
// 虚拟头节点
// 虚拟头节点指向最近使用元素
// 虚拟尾节点指向最近未使用元素
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
DLinkedNode node = map.get(key);
// 将node 移动 到 head指向的元素
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
if (map.containsKey(key)){
// 包含 元素
DLinkedNode node = map.get(key);
node.value = value;
map.put(key,node);
// 移动node到 head指向的元素
moveToHead(node);
return;
}
// 不包含
// 字典中保存键值对
// 新节点 加入队尾
DLinkedNode newNode = new DLinkedNode(key,value);
map.put(key, newNode);
addToHead(newNode);
size ++;
if (size > capacity){
// size 已经 超过 最大容量
// 删除 tail 指向的元素
removeLastNode();
size --;
}
}
// 移动元素 至 队头
private void moveToHead(DLinkedNode node){
node.prev.next = node.next;
node.next.prev = node.prev;
node.next = head.next;
head.next.prev = node;
head.next = node;
node.prev = head;
}
// 删除末尾元素
private void removeLastNode(){
map.remove(tail.prev.key);
tail.prev.prev.next = tail;
tail.prev = tail.prev.prev;
}
private void addToHead(DLinkedNode node){
head.next.prev = node;
node.next = head.next;
head.next = node;
node.prev = head;
}
|
复杂度分析 :
时间复杂度 : put 和 get 都是 O(1).
空间复杂度 : O(capacity)，因为哈希表 和 双向链表 最多存储 capacity + 1个元素.
执行流程：
2020.7.5更 LRU缓存策略的应用
- 今天翻博客目录在 mac 文件夹中的排序方法
- 看到按照修改日期排序
- 心里想，这不就是 LRU缓存策略 吗
- 将最近使用的挪到 链表的头部
- 最不常用的在 链表的尾部
- 猜想可能mac OS操作系统，文件管理，对 文件的排序，使用到了 LRU缓存策略
- 见下图
