源码分析之LinkedHashMap

概念

LinkedHashMap也是Java集合框架的一员,是HashMap的子类。LinkedHashMap可以保存插入顺序,底层是通过HashMap的哈希表和双向链表保存数据。

类结构

LinkedHashMap继承于HashMap,实现了Map接口。重写了部分HashMap类中的方法。

类成员

Entry 类

1
2
3
4
5
6
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);
}
}

EntryLinkedHashMap静态内部类,继承了HashMap.Node<K,V>类,在Node类的基础上增加了before、 after节点用来构成双向循环链表。

head & tail

1
2
3
4
// 头结点
transient LinkedHashMap.Entry<K,V> head;
// 尾节点
transient LinkedHashMap.Entry<K,V> tail;

headtail节点分别记录分别记录着双向循环链表头结点和尾节点。

accessOrder

1
final boolean accessOrder;

accessOrder 用来区分对LinkedHashMap中元素顺序。accessOrderfalse时(默认为false),按照插入顺序,accessOrdertrue时,按照访问顺序。

构造函数

LinkedHashMap提供了5种构造函数。

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
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}

实际上LinkedHashMap的构造函数时调用父类HashMap的构造函数实现的。前四种accessOrder均为false,也就是表明默认按照插入顺序。第五种构造函数可以指定accessOrder的值。

get(Object key) 方法

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;
}

get方法重写了HashMapget方法。不同的时候,在查找出元素后,如果当前是按照元素访问顺序的模式,这里会通过调用afterNodeAccess方法把元素添加至链表的尾部。因为按照元素访问的模式中,会按照访问效率排序,最少访问的靠前,最新访问的靠后。

put(K key, V value) 方法

LinkedHashMapput方法并没有重写父类HashMapput方法。而是重写了其中的newNodenewTreeNodeafterNodeAccessafterNodeInsertion方法。

linkNodeLast 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
linkNodeLast(p);
return p;
}

LinkedHashMap重写了newTreeNodenewTreeNode方法。这两个方法在创建新节点的时候,都调用了linkNodeLast方法。

1
2
3
4
5
6
7
8
9
10
11
12
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
// 尾节点为空,p设置为head节点
head = p;
else {
// 将节点添加至链表尾部
p.before = last;
last.after = p;
}
}

linkNodeLast方法中将给定的节点,将节点添加到双向链表的尾部。

afterNodeAccess 方法

LinkedHashMap重写了afterNodeAccess方法,在put方法中,当遇到了putkey相同的时候,更新节点的同时,调用afterNodeAccess方法,如果accessOrdertrue的时候,将会把节点添加至链表尾部。

afterNodeInsertion 方法
1
2
3
4
5
6
7
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}

removeEldestEntry方法在LinkedHashMap直接return false。如果有需要,我们可以选择重写removeEldestEntry方法,来定义老节点firstput新数据时的删除机制。

总结

LinkedHashMap通过重新HashMap部分方法来实现其可以按插入顺序或者访问顺序的特性。由于LinkedHashMap按照访问顺序的特性,可以用来实现LRU算法。

LinkedHashMap是非线程安全的,只适用于单线程,多线程环境慎用。