Java 容器源码分析之 LinkedHashMap（3）
|
- UID
- 1066743
|
Java 容器源码分析之 LinkedHashMap（3）
如何维护插入序和访问序？在 LinkedHashMap 中，所有的 Entry 都被串联在一个双向链表中。从上一节的代码中可以看到，每次在新建一个节点时都会将新建的节点链接到双向链表的末尾。这样从双向链表的尾部向头部遍历就可以保证插入顺序了，头部节点是最早添加的节点，而尾部节点则是最近添加的节点。那么，访问顺序要怎么实现呢？
之前我们在分析 HashMap 的源码的时候，在添加及更新、查找、删除等操作中可以看到 afterNodeAccess、afterNodeInsertion、afterNodeRemoval 等几个方法的调用，不过在 HashMap 中这几个方法中没有任何操作。实际上，这几个方法就是供 LinkedHashMap 的重写的，我们不妨看一下在 HashMap 中这几个方法的声明：
1
2
3
4
| // Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
|
在 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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| //移除节点的回调函数
void afterNodeRemoval(Node<K,V> e) { // unlink
//移除一个节点，双向链表中的连接关系也要调整
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
//插入节点的回调函数
//构造函数中调用，evict为false
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
//first是头元素，也是最老的元素
//在插入序中，就是最先插入的元素
//在访问序中，就是最远被访问的元素
//这里removeEldestEntry(first)始终返回true，即不删除最老的元素
//如果是一个容量固定的cache，可调整removeEldestEntry(first)的实现
if (evict && (first = head) != null && removeEldestEntry(first)) {
//不是构造方法中
//头元素不为空
//要删除最老的元素
//在LinkedHashMap的实现中，不会进入这里
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
//访问节点的回调函数
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
//如果是访问序，且当前节点并不是尾节点
//将该节点置为双向链表的尾部
if (accessOrder && (last = tail) != e) {
//p 当前节点， b 前驱结点， a 后继结点
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null; //设为尾节点，则没有后继
if (b == null)
head = a; //p是头节点，调整后其后继结点变为头节点
else
b.after = a;//p不是头节点，前驱和后继结点相连
if (a != null)
a.before = b;
else
last = b;//应该不会出现这种情况，p是尾节点
if (last == null)
head = p;
else {
//将p置于尾节点之后
p.before = last;
last.after = p;
}
tail = p;//调整tail指向
++modCount;//结构性改变
}
}
|
在插入节点、删除节点和访问节点后会调用相应的回调函数。可以看到，在 afterNodeAccess方法中，如果该 LinkedHashMap 是访问序，且当前访问的节点不是尾部节点，则该节点会被置为双链表的尾节点。即，在访问序下，最近访问的节点会是尾节点，头节点则是最远访问的节点。 |
|
|
|
|
|
