简介
LinkedHashMap继承至HashMap，对HashMap进行了增强。主要是HashMap是无序的，不能保持插入顺序，而LinkedHashMap对HashMap的Node节点进行了增强。支持了保持插入顺序或者按访问顺序排序。
构造函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
transient LinkedHashMapEntry<K,V> head;
transient LinkedHashMapEntry<K,V> tail;
// 设置排序规则，true：访问顺序，false：插入顺序
final boolean accessOrder;
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
对比HashMap，主要增加了accessOrder来定义排序规则。
Node节点
1
2
3
4
5
6
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
LinkedHashMapEntry<K,V> before, after;
LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
继承至HashMap的Node节点，增加了双链表的结构。
get
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
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
// 如果按访问排序，则需要改变顺序，把e移动到末尾
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return defaultValue;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
// 元素访问时调用，把元素移动到末尾
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMapEntry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<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;
}
}
当元素倍访问后，若是按访问排序，则会把被访问元素放置末尾。
contains
1
2
3
4
5
6
7
8
public boolean containsValue(Object value) {
for (LinkedHashMapEntry<K,V> e = head; e != null; e = e.after) {
V v = e.value;
if (v == value || (value != null && value.equals(v)))
return true;
}
return false;
}
contains相关操作不改变排序顺序，所以几乎是复用的HashMap的
replace
1
2
3
4
5
6
7
8
9
10
11
@Override
public V replace(K key, V value) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
同样是用的HashMap的实现。但是值的更改会触发afterNodeAccess方法来更新顺序。
put
1
2
3
4
5
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMapEntry<K,V> p = new LinkedHashMapEntry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
依旧是复用的HashMap的put方法，不过这里重写了构造node节点的方法，返回的是双链表结构的node节点
remove
1
2
3
4
5
6
7
8
9
10
11
12
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<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;
}
remove也是直接调用的HashMap中的实现，然后再HashMap提供的勾子函数中实现了元素的移除操作。
勾子方法
1
2
3
4
5
6
7
8
9
10
11
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMapEntry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
前面已经看过了HashMap留下的访问以及删除回调，以及新增节点直接添加到末尾的重写。最后看一下afterNodeInsertion方法，这个就是当插入元素后，通过removeEldestEntry判断是否需要删除最旧的元素。这个实现可以在Android中的LruCache中看到。
总结
- LinkedHashMap是继承至HashMap的增强Map，增加了对插入顺序和最近访问顺序的支持，使用的是双向链表。最新数据放置在末尾。
- LinkedHashMap主要重写了HashMap的afterNodeAccess、afterNodeInsertion、afterNodeRemoval三个勾子方法，来在对应的时刻更新顺序。
- 在把accessOrder设置为true后（默认false），replace、get、remove、put都会把最新的数据放到末尾。