`LinkedHashMap` 继承自`HashMap`, 它维护着一个运行于所有条目的双重链接列表。
此链接列表定义了迭代顺序，该迭代顺序通常就是将键插入到映射中的顺序（插入顺序）。
我们从HashMap的putVal()方法开始看
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
| final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
|
在newNode(hash, key, value, null);时调用了LinkedHashMap的linkNodeLast
1
2
3
4
5
6
7
8
9
10
| private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
|
这个操作就是将新的Node插入到LinkedHashMap的尾节点.
我们看完插入操作, 再看一下afterNodeAccess(), 这个方法在HashMap的putVal()方法中, 重新插入一个数据时会调用到(还有一些其他的方法也会调用这个方法). 当重新插入数据时, 会尝试afterNodeAccess()调用, 然后改变LinkedHashMap的双向链表, 从而改变整个链表表达的插入顺序.
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
| void afterNodeAccess(Node<K,V> e) {
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e,
b = p.before,
a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
|
从上面方法的if中我们可以看到,如果accessOrder为true(默认false), 当重新访问数据时, 插入顺序呢是会改变的. 也就是说在调用下列方法时
- put
- replace
- computeIfAbsent
- compute
- merge
- get
被调用的数据会放到队列尾, 因此如果我们将accessOrder置为true, LinkedHashMap可以当做LRU Cache使用
当继承LinkedHashMap, 实现一个LRU Cache的时候, 我们可以重载一下removeEldestEntry(Map.Entry<K,V> eldest)这个方法, 当插入新的数据的时候, 可以灵活地处理过期的数据
写个测试程序测试一下
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
| import org.junit.Test;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
public class TestLinkedHashMap {
@Test
public void testHashMap() {
Map<String, String> map = new HashMap<>();
for (int i = 0; i < 1000; i++) {
map.put(i + "", "");
}
testStep1("testHashMap", map);
}
private Map<String, String> falseAccessOrderMap() {
LinkedHashMap<String, String> map = new LinkedHashMap<>();
for (int i = 1; i < 1000; i++) {
map.put(i + "", "");
}
return map;
}
private void testStep1(String module, Map<String, String> map) {
int older = 0;
for (String string : map.keySet()) {
int num = Integer.parseInt(string);
if ((older + 1) != num) {
System.err.println(module + " : " + (older + 1) + " -> " + num);
break;
}
older = num;
}
}
@Test
public void falseAccessOrderLinkedHashMap_SaveOrder() {
Map<String, String> map = falseAccessOrderMap();
testStep1("falseAccessOrderLinkedHashMap_SaveOrder", map);
}
@Test
public void falseAccessOrderLinkedHashMap_RePutSaveOrder() {
Map<String, String> map = falseAccessOrderMap();
map.put("123", "");
testStep1("falseAccessOrderLinkedHashMap_RePutSaveOrder", map);
}
@Test
public void falseAccessOrderLinkedHashMap_GetSaveOrder() {
Map<String, String> map = falseAccessOrderMap();
map.put("123", "");
map.put("123", "");
map.put("123", "");
testStep1("falseAccessOrderLinkedHashMap_GetSaveOrder", map);
}
private Map<String, String> trueAccessOrderMap() {
LinkedHashMap<String, String> map = new LinkedHashMap<>(10, 0.75f, true);
for (int i = 1; i < 1000; i++) {
map.put(i + "", "");
}
return map;
}
@Test
public void trueAccessOrderLinkedHashMap_SaveOrder() {
Map<String, String> map = trueAccessOrderMap();
testStep1("trueAccessOrderLinkedHashMap_SaveOrder", map);
}
@Test
public void trueAccessOrderLinkedHashMap_RePutSaveOrder() {
Map<String, String> map = trueAccessOrderMap();
map.put("123", "");
testStep1("trueAccessOrderLinkedHashMap_RePutSaveOrder", map);
}
@Test
public void trueAccessOrderLinkedHashMap_GetSaveOrder() {
Map<String, String> map = trueAccessOrderMap();
map.put("123", "");
map.put("123", "");
map.put("123", "");
testStep1("trueAccessOrderLinkedHashMap_GetSaveOrder", map);
}
}
|
运行一下, 结果果真如此.
