LRU缓存的实现

本文最后更新于:2021年9月22日 凌晨

LRU 缓存介绍与实现 (Java)

力扣真题

https://leetcode-cn.com/problems/lru-cache/

运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。

实现 LRUCache 类:

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
  • void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作?

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入
["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 <= 3000
0 <= key <= 3000
0 <= value <= 104
最多调用 3 * 104 次 get 和 put

引子

我们平时总会有一个电话本记录所有朋友的电话,如果有朋友经常联系,那些朋友的电话号码不用翻电话本我们也能记住,但是,如果长时间没有联系了,要再次联系那位朋友的时候,我们又不得不求助电话本,但是,通过电话本查找还是很费时间的。我们大脑能够记住的东西是一定的,我们只能记住自己 最熟悉的,而长时间不熟悉的自然就忘记了。

其实,计算机也用到了同样的一个概念,我们用缓存来存放以前读取的数据,而不是直接丢掉,这样,再次读取的时候,可以直接在缓存里面取,而不用再重 新查找一遍,这样系统的反应能力会有很大提高。但是,当我们读取的个数特别大的时候,我们不可能把所有已经读取的数据都放在缓存里,毕竟内存大小是一定 的,我们一般把最近常读取的放在缓存里(相当于我们把最近联系的朋友的姓名和电话放在大脑里一样)。现在,我们就来研究这样一种缓存机制。

LRU 缓存

LRU 缓存利用了这样的一种思想。LRU 是 Least Recently Used 的缩写,翻译过来就是“最近最少使用”,也就是说,LRU 缓存把最近最少使用的数据移除,让给最新读取的数据。而往往最常读取的,也是读取次数最多的,所 以,利用 LRU 缓存,我们能够提高系统的performance.

实现

要实现 LRU 缓存,我们首先要用到一个类 LinkedHashMap。 用这个类有两大好处:一是它本身已经实现了按照访问顺序的存储,也就是说,最近读取的会放在最前面,最最不常读取的会放在最后(当然,它也可以实现按照插 入顺序存储)。第二,LinkedHashMap 本身有一个方法用于判断是否需要移除最不常读取的数,但是,原始方法默认不需要移除(这时,LinkedHashMap 相当于一个 Linkedlist ),所以,我们需要override 这样一个方法,使得当缓存里存放的数据个数超过规定个 数后,就把最不常用的移除掉。LinkedHashMap 的 API 写得很清楚,推荐大家可以先读一下。

要基于 LinkedHashMap 来实现 LRU 缓存,我们可以选择 inheritance,也可以选择 delegation

基于 inheritance 的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
// 定义缓存键值对个数
private int cacheSize;

public LRUCache(int cacheSize) {
// 调用父类的构造方法,初始容量为16,加载因子为0.75
// 将排序模式改为访问排序,即每次访问都会重新排序,访问到的数据顺序会排在尾部
super(16, 0.75f, true);
this.cacheSize = cacheSize;
}

protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
// 当当前键值对个数大于定义的缓存键值对个数时,每次添加新的键值对都会删除最老的键值对,实现稳定的缓存个数
return super.size() > cacheSize;
}
}
测试
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
import java.util.Map;
import java.util.Set;

public class Test {
public static void main(String[] args) {
// 初始化缓存容量为3
LRUCache<String,Object> lruCache = new LRUCache<>(3);

// 添加三个元素
lruCache.put("key1", "value1");
lruCache.put("key2", "value2");
lruCache.put("key3", "value3");

// 获取最老的元素
System.out.println(lruCache.get("key1"));

// 添加新元素
lruCache.put("key4", "value4");

// 获取缓存的entrySet
Set<Map.Entry<String,Object>> entrySet = lruCache.entrySet();

// 增强for循环遍历内容
for (Map.Entry<String, Object> next : entrySet) {
System.out.println(next.getKey() + ":" + next.getValue());
}
}
}
结果
1
2
3
4
value1
key3:value3
key1:value1
key4:value4

可以从结果发现,因为我们先访问了key1,这时key1被放到了链表的尾部,排列顺序为key2、key3、key1,然后进行put(“key4”) 的操作在尾部添加数据,这时候键值对的数量超过了缓存键值对的数量,会删除头部最没有被访问过的数据key2,此时链表的排列顺序为key3、key1、key4,和遍历的结果相同

基于 delegation 的实现:

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
import java.util.LinkedHashMap;
import java.util.Collection;
import java.util.Map;
import java.util.ArrayList;

/**
* An LRU cache, based on <code>LinkedHashMap</code>.
*
* <p>
* This cache has a fixed maximum number of elements (<code>cacheSize</code>).
* If the cache is full and another entry is added, the LRU (least recently
* used) entry is dropped.
*
* <p>
* This class is thread-safe. All methods of this class are synchronized.
*/
public class LRUCache<K, V> {
// 加载因子
private static final float hashTableLoadFactor = 0.75f;
// 底层是一个LinkedHashMap
private final LinkedHashMap<K, V> map;
// 缓存的个数
private final int cacheSize;

/**
* Creates a new LRU cache.
*
* @param cacheSize the maximum number of entries that will be kept in this
* cache.
*/
public LRUCache(int cacheSize) {
this.cacheSize = cacheSize;
int hashTableCapacity = (int) Math.ceil(cacheSize / hashTableLoadFactor) + 1;
map = new LinkedHashMap<K, V>(hashTableCapacity, hashTableLoadFactor, true) {
// (an anonymous inner class)
private static final long serialVersionUID = 1;

@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > LRUCache.this.cacheSize;
}
};
}

/**
* Retrieves an entry from the cache.<br>
* The retrieved entry becomes the MRU (most recently used) entry.
*
* @param key the key whose associated value is to be returned.
* @return the value associated to this key, or null if no value with this key
* exists in the cache.
*/
public synchronized V get(K key) {
return map.get(key);
}

/**
* Adds an entry to this cache. The new entry becomes the MRU (most recently
* used) entry. If an entry with the specified key already exists in the cache,
* it is replaced by the new entry. If the cache is full, the LRU (least
* recently used) entry is removed from the cache.
*
* @param key the key with which the specified value is to be associated.
* @param value a value to be associated with the specified key.
*/
public synchronized void put(K key, V value) {
map.put(key, value);
}

/**
* Clears the cache.
*/
public synchronized void clear() {
map.clear();
}

/**
* Returns the number of used entries in the cache.
*
* @return the number of entries currently in the cache.
*/
public synchronized int usedEntries() {
return map.size();
}

/**
* Returns a <code>Collection</code> that contains a copy of all cache entries.
*
* @return a <code>Collection</code> with a copy of the cache content.
*/
public synchronized Collection<Map.Entry<K, V>> getAll() {
return new ArrayList<>(map.entrySet());
}

}

如果在面试题里考到如何实现 LRU,考官一般会要求使用双链表 + Hashtable 的方式。

双链表 + hashtable 实现原理

将Cache的所有位置都用双连表连接起来,当一个位置被命中之后,就将通过调整链表的指向,将该位置调整到链表头的位置,新加入的Cache直接加到链表头中。这样,在多次进行Cache操作后,最近被命中的,就会被向链表头方向移动,而没有命中的,而向链表后面移动,链表尾则表示最近最少使用的Cache。当需要替换内容时候,链表的最后位置就是最少被命中的位置,我们只需要淘汰链表最后的部分即可。

基于双向链表加 hashtable 实现

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
class Node {
Node prev; // 前一节点
Node next; // 后一节点
Object value;//值
Object key;//键
}

public class LRUCache {
private int cacheSize;//缓存大小
private Hashtable<Object, Node> nodes;//缓存容器
private int currentSize;//当前缓存对象数量
private Node first;//(实现双链表)链表头
private Node last;//(实现双链表)链表尾

public LRUCache(int cacheSize) {
currentSize = 0;
this.cacheSize = cacheSize;
nodes = new Hashtable<>(cacheSize);//缓存容器
}

/**
* 获取缓存中对象
* @param key
* @return
*/
public Object get(Object key) {
Node node = nodes.get(key);
if (node != null) {
moveToHead(node);
return node.value;
} else {
return null;
}
}

/**
* 添加缓存
* @param key
* @param value
*/
public void put(Object key, Object value) {
Node node = nodes.get(key);

if (node == null) {
//缓存容器是否已经超过大小.
if (currentSize >= cacheSize) {
if (last != null)//将最少使用的删除
nodes.remove(last.key);
removeLast();
} else {
currentSize++;
}

node = new Node();
}
node.value = value;
node.key = key;
//将最新使用的节点放到链表头,表示最新使用的.
moveToHead(node);
nodes.put(key, node);
}

/**
* 删除链表尾部节点
* 表示 删除最少使用的缓存对象
*/
private void removeLast() {
//链表尾不为空,则将链表尾指向null. 删除连表尾(删除最少使用的缓存对象)
if (last != null) {
if (last.prev != null)
last.prev.next = null;
else
first = null;
last = last.prev;
}
}

/**
* 移动到链表头,表示这个节点是最新使用过的
* @param node
*/
private void moveToHead(Node node) {
if (node == first)
return;
if (node.prev != null)
node.prev.next = node.next;
if (node.next != null)
node.next.prev = node.prev;
if (last == node)
last = node.prev;
if (first != null) {
node.next = first;
first.prev = node;
}
first = node;
node.prev = null;
if (last == null)
last = first;
}
}
测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Test {
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(3);

lruCache.put("Amy", 1);
lruCache.put("Bill", 2);
lruCache.put("Yancy", 3);
lruCache.put("Buffer", 4);
lruCache.put("Amy", 5);

System.out.println(lruCache.get("Bill"));

System.out.println(lruCache.get("Yancy"));

lruCache.put("John", 16);

System.out.println(lruCache.get("Buffer"));
}
}
结果
1
2
3
null
3
null

这种方法比较简单,但不太容易理解,下面这种更加容易理解一点的

基于链表加键值的实现

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
package test3;

class Node {
Node prev; // 前一节点
Node next; // 后一节点
Object key; // 键
Object value; // 值

public Node(Object key) {
this.key = key;
}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((key == null) ? 0 : key.hashCode());
result = prime * result + ((next == null) ? 0 : next.hashCode());
result = prime * result + ((prev == null) ? 0 : prev.hashCode());
result = prime * result + ((value == null) ? 0 : value.hashCode());
return result;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (key == null) {
if (other.key != null)
return false;
} else if (!key.equals(other.key))
return false;
if (next == null) {
if (other.next != null)
return false;
} else if (!next.equals(other.next))
return false;
if (prev == null) {
if (other.prev != null)
return false;
} else if (!prev.equals(other.prev))
return false;
if (value == null) {
if (other.value != null)
return false;
} else if (!value.equals(other.value))
return false;
return true;
}
}

public class LRUCache{
int cacheSize; // 缓存容量
int currentSize;// 当前键值数量
Node first; // 头节点
Node last; // 尾结点

public LRUCache(int cacheSize) {
currentSize = 0;
this.cacheSize = cacheSize; // 初始化缓存容量
first = null; // 头节点为空
last = first; // 尾节点就是头节点
}

/**
* 根据键获取对应node节点
*
* 1、首先判断头节点是否为空,如果为空直接返回null
* 2、此时的头节点一定不为空,声明一个临时变量指向头节点
* 3、遍历整个链表,当节点为null时停止遍历
* 1、比较传入的键和节点中的键是否相同,如果相同就返回此节点
* 2、将node指向下一个节点
* 4、遍历完了整个链表都没有找到对应的key,返回null
*/
public Node getNode(Object key) {
if (first == null) {
return null;
}

Node node = first;

while (node != null) {
if (node.key.equals(key)) {
return node;
}
node = node.next;
}

return null;
}

/**
* 根据键获取对应的值, 并把它放在头节点(最近最多使用)
*/
public Object get(Object key) {
Node node = getNode(key);

if (null != node) {
moveToHead(node);

return node.value;
}
return null;
}

/**
* 移动到链表头,表示这个节点是最新使用过的
*
* 1、如果node是头节点,直接返回(已经是最近最多使用)
* 2、如果node是尾节点,将node的上一个节点作为尾结点
* 1、此时node既不是头节点也不是尾节点,一定存在上下节点的指向
* 2、将node的上节点与下节点相互指向
* 3、将头节点的上节点与传入的节点的下节点相互指向
* 4、将传入的节点作为头节点
*/
private void moveToHead(Node node) {
if (node == first) {
return;
}

if (last == node) {
node.prev.next = null;
last = node.prev;
} else {
if (null != node.prev) {
node.prev.next = node.next;
}

if (null != node.next) {
node.next.prev = node.prev;
}
}

first.prev = node;
node.next = first;

node.prev = null;
first = node;
}

/**
* 添加或修改键值对
* @param key 键
* @param value 值
* @return 添加返回新值,更改返回旧值
*
* 1、通过key获取node,如果node存在说明已经有当前键值对,更新值并把当前节点放到头节点后返回旧值
* 2、此时没有获取到node,说明是添加,创建一个带有key的新节点,判断头节点是否为空
* 1、头节点为空直接将新节点和值赋给头节点,头尾节点是同一个
* 2、头节点不为空,就将新节点作为头节点,并把新节点的下节点和原来头节点的上节点进行指向
* 3、添加完对当前链表长度+1
* 4、判断是否需要达到缓存的最大容量,如果达到了就移除最近最少使用的节点(即尾节点)
*/
public Object put(Object key, Object value) {
Node node = getNode(key);

if (null != node) {
Object oldValue = node.value;

node.value = value;

moveToHead(node);

return oldValue;
}

node = new Node(key);

if (first == null) {
first = node;
first.value = value;

first.prev = null;
first.next = null;

last = first;
} else {
Node firstNode = node;
firstNode.value = value;

firstNode.next = first;
first.prev = firstNode;

firstNode.prev = null;
first = firstNode;
}

currentSize++;

if (currentSize > cacheSize) {
removeLast();
}

return value;
}

/**
* 删除链表尾部节点,即使用最近最少使用的
*
* 1、如果尾节点的上一个节点不为空,将上节点的下节点指向null
* 2、如果尾节点的上一个节点为空,说明当前节点是头节点,直接等于null
* 3、将尾节点的上节点当做尾节点
*/
private Object removeLast() {
if (last != null) {
if (last.prev != null) {
last.prev.next = null;
} else {
first = null;
}
last = last.prev;
currentSize--;
return last.value;
}

return null;
}

/**
* 移除指定key
* @param key 键
* @return 返回键对应的值或者null
*
* 1、先根据键获取到对应的对应的节点,如果节点为null说明当前键值对不存在,直接返回null
* 2、获取到键对应的节点,把节点的上节点和下节点相互引用
* 3、当前链表长度-1,返回节点的值
*/
public Object remove(Object key) {
Node node = getNode(key);

if (null != node) {
Object value = node.value;

if (null != node.prev) {
node.prev.next = node.next;
}

if (null != node.next) {
node.next.prev = node.prev;
}

currentSize--;
return value;
}

return null;
}

// toString
@Override
public String toString() {

StringBuilder sb = new StringBuilder();
sb.append("NewLRUCache :{ ");

Node node = first;

while (node != null) {
sb.append("{" + node.key + ":" + node.value + "}, ");
node = node.next;
}

sb.delete(sb.length()-2, sb.length());

sb.append(" }");

return sb.toString();
}
}
测试
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
public class Test {
public static void main(String[] args) {
NewLRUCache lruCache = new NewLRUCache(3);

lruCache.put("a", 1); // a:1
lruCache.put("b", 2); // b:2 a:1
lruCache.put("c", 3); // c:3 b:2 a:1

System.out.println(lruCache.remove("b")); // c:3 a:1

lruCache.put("a", 4); // a:4 c:3
lruCache.put("e", 5); // e:5 a:4 c:3

System.out.println(lruCache.get("c")); // c:3 e:5 a:4

lruCache.put("f", 6); // f:6 c:3 e:5

System.out.println(lruCache.put("e", 100)); // e:100 f:6 c:3
// System.out.println(lruCache.first.key);
// System.out.println(lruCache.first.next.key);
// System.out.println(lruCache.last.key);
// System.out.println(lruCache.currentSize);

System.out.println(lruCache); // e:100 f:6 c:3
}
}

补充:链表加键值对加迭代器实现

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
class Entry {
Object key; // 键
Object value; // 值
}

class Node {
Node prev; // 前一节点
Node next; // 后一节点
Entry entry;

public Node(Object key) {
Entry entry = new Entry();
entry.key = key;
this.entry = entry;
}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((entry == null) ? 0 : entry.hashCode());
result = prime * result + ((next == null) ? 0 : next.hashCode());
result = prime * result + ((prev == null) ? 0 : prev.hashCode());
return result;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (entry == null) {
if (other.entry != null)
return false;
} else if (!entry.equals(other.entry))
return false;
if (next == null) {
if (other.next != null)
return false;
} else if (!next.equals(other.next))
return false;
if (prev == null) {
if (other.prev != null)
return false;
} else if (!prev.equals(other.prev))
return false;
return true;
}
}

public class LRUCache implements Iterable<Entry>{
private int cacheSize; // 缓存容量
private int currentSize;// 当前键值数量
private Node first; // 头节点
private Node last; // 尾结点

public LRUCache(int cacheSize) {
currentSize = 0;
this.cacheSize = cacheSize; // 初始化缓存容量
first = null; // 头节点为空
last = first; // 尾节点就是头节点
}

/**
* 根据键获取对应node节点
*
* 1、首先判断头节点是否为空,如果为空直接返回null
* 2、此时的头节点一定不为空,声明一个临时变量指向头节点
* 3、遍历整个链表,当节点为null时停止遍历
* 1、比较传入的键和节点中的键是否相同,如果相同就返回此节点
* 2、将node指向下一个节点
* 4、遍历完了整个链表都没有找到对应的key,返回null
*/
public Node getNode(Object key) {
if (first == null) {
return null;
}

Node node = first;

while (node != null) {
if (node.entry.key.equals(key)) {
return node;
}
node = node.next;
}

return null;
}

/**
* 根据键获取对应的值, 并把它放在头节点(最近最多使用)
*/
public Object get(Object key) {
Node node = getNode(key);

if (null != node) {
moveToHead(node);

return node.entry.value;
}
return null;
}

/**
* 移动到链表头,表示这个节点是最新使用过的
*
* 1、如果node是头节点,直接返回(已经是最近最多使用)
* 2、如果node是尾节点,将node的上一个节点作为尾结点
* 1、此时node既不是头节点也不是尾节点,一定存在上下节点的指向
* 2、将node的上节点与下节点相互指向
* 3、将头节点的上节点与传入的节点的下节点相互指向
* 4、将传入的节点作为头节点
*/
private void moveToHead(Node node) {
if (node == first) {
return;
}

if (last == node) {
node.prev.next = null;
last = node.prev;
} else {
if (null != node.prev) {
node.prev.next = node.next;
}

if (null != node.next) {
node.next.prev = node.prev;
}
}

first.prev = node;
node.next = first;

node.prev = null;
first = node;
}

/**
* 添加或修改键值对
* @param key 键
* @param value 值
* @return 添加返回新值,更改返回旧值
*
* 1、通过key获取node,如果node存在说明已经有当前键值对,更新值并把当前节点放到头节点后返回旧值
* 2、此时没有获取到node,说明是添加,创建一个带有key的新节点,判断头节点是否为空
* 1、头节点为空直接将新节点和值赋给头节点,头尾节点是同一个
* 2、头节点不为空,就将新节点作为头节点,并把新节点的下节点和原来头节点的上节点进行指向
* 3、添加完对当前链表长度+1
* 4、判断是否需要达到缓存的最大容量,如果达到了就移除最近最少使用的节点(即尾节点)
*/
public Object put(Object key, Object value) {
Node node = getNode(key);

if (null != node) {
Object oldValue = node.entry.value;

node.entry.value = value;

moveToHead(node);

return oldValue;
}

node = new Node(key);

if (first == null) {
first = node;
first.entry.value = value;

first.prev = null;
first.next = null;

last = first;
} else {
Node firstNode = node;
firstNode.entry.value = value;

firstNode.next = first;
first.prev = firstNode;

firstNode.prev = null;
first = firstNode;
}

currentSize++;

if (currentSize > cacheSize) {
removeLast();
}

return value;
}

/**
* 删除链表尾部节点,即使用最近最少使用的
*
* 1、如果尾节点的上一个节点不为空,将上节点的下节点指向null
* 2、如果尾节点的上一个节点为空,说明当前节点是头节点,直接等于null
* 3、将尾节点的上节点当做尾节点
*/
private Object removeLast() {
if (last != null) {
if (last.prev != null) {
last.prev.next = null;
} else {
first = null;
}
last = last.prev;
currentSize--;

return last.entry.value;
}

return null;
}

/**
* 移除指定key
* @param key 键
* @return 返回键对应的值或者null
*
* 1、先根据键获取到对应的对应的节点,如果节点为null说明当前键值对不存在,直接返回null
* 2、获取到键对应的节点,把节点的上节点和下节点相互引用
* 3、当前链表长度-1,返回节点的值
*/
public Object remove(Object key) {
Node node = getNode(key);

if (null != node) {

Object value = node.entry.value;

if (null != node.prev) {
node.prev.next = node.next;
}

if (null != node.next) {
node.next.prev = node.prev;
}

currentSize--;

return value;
}

return null;
}

// 迭代器
public Iterator<Entry> iterator(){

return new Iterator<Entry>(){

private int temp = 0;

public boolean hasNext() {
return temp++ < currentSize;
}

public Entry next() {
Node node = first;
for (int i = 1; i < temp; i++) {
node = node.next;
}

return node.entry;
}

};
}
}
测试
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Test {
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(3);

lruCache.put("a", 1); // a:1
lruCache.put("b", 2); // b:2 a:1
lruCache.put("c", 3); // c:3 b:2 a:1

for (Entry entry : lruCache) {
System.out.println(entry.key + ":" + entry.value);
}
}
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!