数据结构
LinkedHashMap 继承了HashMap,对HashMap进行了增强，通过内部维护了双向链表，使LinkedHashMap拥有了顺序访问的功能，提供了有序性。
1
2
3
| public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
|
内部构造
Entry内部维护了 before 和 after 两个entry，用于构建双向链表entry之间的指向关系，同时accessOrder 用于设置LinkedHashMap的读取是按照访问顺序还是插入顺序，通过这个accessOrder属性可以很容易实现 LRU
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
// 头节点（最旧未使用）
transient LinkedHashMap.Entry<K,V> head;
// 尾节点 （最近使用）
transient LinkedHashMap.Entry<K,V> tail;
// 设置LinkedHashMap的读取顺序
// false(default)：插入顺序
// true：访问顺序
final boolean accessOrder;
|
get(Object key)
get()方法使用的是HashMap的get(),但如果 accessOrder 为 true时，要根据最近访问的原则，将访问到的元素添加到LinkedHashMap末尾
1
2
3
4
5
6
7
8
| public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
|
具体的移动节点到末尾的代码，同时要考虑到节点临界值的问题（-双向链接， -> 单向链接）
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
| void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 如果 accessOrder为true，并且当前节点不是tail节点（尾节点不用移动位置），进行移动操作
if (accessOrder && (last = tail) != e) {
// 获取当前节点的 b(before) a(after)
// b - p - a
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 当前节点的after释放
p.after = null;
// 如果b为空，即当前节点p为head
if (b == null)
head = a;
// b -> a
else
b.after = a;
// a不为空，b <- a
if (a != null)
a.before = b;
// a空，b为tail节点
else
last = b;
// 尾节点为空，p设置为头节点
if (last == null)
head = p;
// 将p放入链表末尾 last -> p
else {
p.before = last;
last.after = p;
}
// 刷新设置尾节点p
tail = p;
++modCount;
}
}
|
put(Object K, Object V)
LinkedHashMap内部并没有put()，它采用的是HashMap中的put()，同时根据访问规则，将新节点放入队列尾部
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
| 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) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 直接回调LinkedHashMap中的具体方法
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
|