Java集合框架--LinkedHashMap源码分析(基于JDK1.8)
1 概述
前面我们对HashMap的源码进行了分析(详情可以参考:Java集合框架--HashMap源码分析(二)(基于JDK1.8),我们知道HashMap针对数据的插入是通过计算key的hash值和table大小来确定在数组及链表当中的位置的,所以HashMap没法保存插入数据的顺序。为了保存插入元素的顺序,就有了我们现在要提到的LinkedHashMap,从类的命名我们可以猜想,LinkedHashMap在HashMap现有的数据结构的基础上添加了双向链表来保留插入的顺序。
2 数据结构
在前文我们也提到了与HashMap相比,LinkedHashMap多了双向链表的数据结构,也就是LinkedHashMap是由数组+链表+红黑树+双向链表构成。下面我们来看一看LinkedHashMap的数据结构图。
以上图片来自网络。
3 类继承关系及内部类
首先我们来看一下LinkedHashMap的继承关系:
从上面的类关系图我们可以看出LinkedHashMap继承自HashMap。其实LinkedHashMap和HashMap相比仅仅多了一个维护插入顺序的双向链表的数据结构。而且很多操作都使用了HashMap中的方法,不同的是这里使用了模板方法的设计模式,针对LinkedHashMap中的独特需求就在基本方法中实现了。
接下来我们看一看LinkedHashMap中重要的内部类。
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);
}
}
从上面的源码我们可以看出,Entry与Node相比,就是多了一个前继节点和后继节点的引用。
前面我们提到LinkedHashMap里面也包含了红黑树的数据结构,那么为什么没有TreeNode呢?这是由于使用了HashMap中的TreeNode,我们查看HashMap中的TreeNode内部类。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
... ...
可以发现TreeNode就是LinkedHashMap中的Entry的子类,所以直接拥有了前继节点和后继节点的引用。
4 属性
//头节点(最早插入的节点)
transient LinkedHashMap.Entry<K,V> head;
//尾节点(最后插入的节点)
transient LinkedHashMap.Entry<K,V> tail;
/**
* true:按照访问顺序对节点进行排序。
* false:按照插入顺序对节点进行排序。
*/
final boolean accessOrder;
从上面可以看出,针对排序方式的实现其实就是通过accessOrder属性来控制的。
5 构造函数
针对构造函数,我们直接查看一个比较核心的构造函数的实现就行。
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
//调用父类的构造函数
super(initialCapacity, loadFactor);
//设置节点是否按照访问顺序来排序
this.accessOrder = accessOrder;
}
可以看见,构造函数主要还是调用父类的构造函数来实现,不同点在于就多了一个控制排序方式的参数。
6 核心函数
针对LinkedHashMap的核心函数,这里还是值分析一下put函数和get函数以及一些相关的比较重要的函数。
6.1 put函数
查看LinkedHashMap的源码,可以发现里面并没有实现put函数,而是直接使用的父类的put函数,其实这里就用到了模板方法模式,将一些需要LinkedHashMap实现的不同于HashMap的逻辑延迟到了子类中来实现。
我们直接将HashMap中的put函数的源码贴出来,分析比较关键的部分。
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)
//newNode函数在子类中进行了重写,主要添加了维护链表的逻辑
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;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
我们直接来看一下newNode函数做了些什么。
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;
}
从上面的源码我们可以看出,这里就多了一个将节点插入链表尾部的操作。
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;
}
}
在put函数中还有两个函数是在子类中重写的。
(1)afterNodeAccess,在访问节点后要做的操作
//移动节点到链表的最后
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;
}
}
(2)afterNodeInsertion,在插入节点后要做的操作
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);
}
}
其实这个函数什么都不会做,因为if中的条件一致都为false。可以查看removeEldestEntry函数的源码就明白了。
6.1 get函数
get函数的实现就比较简单了,首先我们来看一下源码:
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;
}
可以发现,如果LinkedHashMap是按照插入顺序来保存节点的,get函数和HashMap的get函数就没有区别了。
7 总结
上面我们分析了LinkedHashMap的源码,其实LinkedHashMap与HashMap相比就多了一个维护顺序的链表结构,其余的都完全一致。而合格链表结构的维护是在创建节点的时候。