Java集合框架分析-LinkedHashMap

本篇文章主要分析一下Java集合框架中的Map部分,LinkedHashMap,该源码分析基于JDK1.8,分析工具,AndroidStudio,文章分析不足之处,还请见谅!

相关文章
1、Java 集合框架分析-概述
2、Java集合框架分析-HashMap
3、Java集合框架分析-ArrayList
4、Java集合框架分析-LinkedList
5、Java集合框架分析-Iterator
6、Java集合框架分析-HashSet

一、LinkedHashMap简介

首先来看下java集合框架的总图,在网上找了两张关于集合框架的架构图:

1
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

继承自HashMap,一个有序的Map接口实现,这里的有序指的是元素可以按插入顺序或访问顺序排列;与HashMap相比,因为LinkedHashMap是继承自HashMap,因此LinkedHashMap:

  1. 同样是基于散列表实现。
  2. 同时实现了Serializable 和 Cloneable接口,支持序列化和克隆。
  3. 并且同样不是线程安全的。

区别是其内部维护了一个双向循环链表,该链表是有序的,可以按元素插入顺序或元素最近访问顺序(LRU)排列。

二、LinkedHashMap数据结构

LinkedHashMap不仅像HashMap那样对其进行基于哈希表和单链表的Entry数组+ next链表的存储方式,而且还结合了LinkedList的优点,为每个Entry节点增加了前驱和后继,并增加了一个为header头结点,构造了一个双向循环链表。也就是说,每次put进来KV,除了将其保存到对哈希表中的对应位置外,还要将其插入到双向循环链表的尾部。
图片摘自于http://www.cnblogs.com/chenpi/p/5294077.html

上图是LinkedHashMap的全部数据结构,包含散列表和循环双向链表,由于循环双向链表线条太多了,不好画,简单的画了一个节点(黄色圈出来的)示意一下,注意左边的红色箭头引用为Entry节点对象的next引用(散列表中的单链表),绿色线条为Entry节点对象的before, after引用(循环双向链表的前后引用);

图片摘自于http://www.cnblogs.com/chenpi/p/5294077.html

上图专门把循环双向链表抽取出来,直观一点,注意该循环双向链表的头部存放的是最久访问的节点或最先插入的节点,尾部为最近访问的或最近插入的节点,迭代器遍历方向是从链表的头部开始到链表尾部结束,在链表尾部有一个空的header节点,该节点不存放key-value内容,为LinkedHashMap类的成员属性,循环双向链表的入口;

上图便是链表常用的操作了。

三、LinkedHashMap源码

上面是分析LinkedHashMap源码的常规知识点,了解一下,才能更好的分析它的源码,下面我们便开始正式的进行分析工作。

首先我们来看下它设定的一些属性:

1
2
3
4
5
6
7
8
//属性设置,序列化ID
private static final long serialVersionUID = 3801124242820219131L;
//双向链表的头部
private transient LinkedHashMapEntry<K,V> header;
//迭代的时候所用到的顺序,如果为FALSE,则按照插入的时候顺序
private final boolean accessOrder;

这些属性虽然简单,但是比较重要,一开始就直接详细说明,不大好理解,等我们分析完了代码再来回顾一下它们所表示的意思。我们来分析分析它的构造函数。

3.1 构造器分析

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
/**
* 设置初始容量和加载因子的构造器
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
/**
* 设置初始容量的构造器
* @param initialCapacity the initial capacity
* @throws IllegalArgumentException if the initial capacity is negative
*/
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
/**
* 默认的空参数的构造器,默认容量为16以及加载因子为0.75
* with the default initial capacity (16) and load factor (0.75).
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
/**
* 使用一个现有的Map来构造LinkedHashMap
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super(m);
accessOrder = false;
}
/**
* 设定迭代顺序的构造器
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @param accessOrder the ordering mode - <tt>true</tt> for
* access-order, <tt>false</tt> for insertion-order
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}

这些构造器都比较简单,我们稍微提及一下,若未指定初始容量initialCapacity,则默认为使用HashMap的初始容量,即16。若未指定加载因子loadFactor,则默认为0.75。accessOrder默认为faslse。这里需要介绍一下这个布尔值,它是双向链表中元素排序规则的标志位。

  1. accessOrder若为false,遍历双向链表时,是按照插入顺序排序。
  2. accessOrder若为true,表示双向链表中的元素按照访问的先后顺序排列,最先遍历到(链表头)的是最近最少使用的元素。

从构造方法中可以看出,默认都采用插入顺序来维持取出键值对的次序。所有构造方法都是通过调用父类的构造方法来创建对象的。

在父类的构造器中我们可以看到它调用了init方法,即在Map类中的构造器中调用了init方法,我们进入查看一下内容

1
2
3
4
5
@Override
void init() {
header = new LinkedHashMapEntry<>(-1, null, null, null);
header.before = header.after = header;
}

这个init方法主要是对header节点进行初始化的,构成一个双向链表。分析完了构造器,接着我们分析一下最常见的一个属性Entry。

3.2 LinkedHashMapEntry分析

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
//这个Entry继承自HashMapEntry
private static class LinkedHashMapEntry<K,V> extends HashMapEntry<K,V> {
//双向节点的前后引用
// These fields comprise the doubly linked list used for iteration.
LinkedHashMapEntry<K,V> before, after;
//构造器
LinkedHashMapEntry(int hash, K key, V value, HashMapEntry<K,V> next) {
super(hash, key, value, next);
}
//移除一个节点
private void remove() {
before.after = after;
after.before = before;
}
/**
* 在指定的位置前面插入一个节点
*/
private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
/*
*在HashMap的put和get方法中,会调用该方法,在HashMap中该方法为空
* 在LinkedHashMap中,当按访问顺序排序时,该方法会将当前节点插入到链表尾部(头结点的前一个节点),否则不做任何事
*/
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//当LinkedHashMap按访问排序时
if (lm.accessOrder) {
lm.modCount++;
//移除当前节点
remove();
//将当前节点插入到头结点前面
addBefore(lm.header);
}
}
void recordRemoval(HashMap<K,V> m) {
remove();
}
}

接着分析最常用的方法put。

3.3 put分析

我们在使用LinkedHashMap的put方法时,发现它调用的是HashMap的put方法,自己本身没有复写put方法,所以这种情况下,我们就得分两种情况来讨论LinkedHashMap的put操作了。

1、Key已存在的情况

在HashMap的put方法中,在发现插入的key已经存在时,除了做替换工作,还会调用recordAccess()方法,在HashMap中该方法为空。LinkedHashMap覆写了该方法,(调用LinkedHashmap覆写的get方法时,也会调用到该方法),LinkedHashMap并没有覆写HashMap中的put方法,recordAccess()在LinkedHashMap中的实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//如果当前标明的accessOrder为TRUE的话,则将当前访问的Entry放置到双向循环链表的尾部,以标明最近访问 ,这也是为什么在HashMap.Entry中有一个空的 recordAccess(HashMap<K,V> m)方法的原因
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//LRU算法,将访问的节点插入到链表尾部
if (lm.accessOrder) {
lm.modCount++;
//删除当前节点
remove();
//将当前节点插入到头结点前面
addBefore(lm.header);
}
}
//将当前节点插入到头结点前面
private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}

2、key不存在的情况下

在put新Entry的过程中,如果发现key不存在时,除了将新Entry放到哈希表的相应位置,还会调用addEntry方法,它会调用creatEntry方法,该方法将新插入的元素放到双向链表的尾部,这样做既符合插入的先后顺序,又符合了访问的先后顺序。

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
//创建节点,插入到LinkedHashMap中,该方法覆盖HashMap的addEntry方法
void addEntry(int hash, K key, V value, int bucketIndex) {
//注意头结点的下个节点即header.after,存放于链表头部,是最不经常访问或第一个插入的节点,
LinkedHashMapEntry<K,V> eldest = header.after;
//如果有必要,则删除掉该近期最少使用的节点
if (eldest != header) {
boolean removeEldest;
size++;
try {
//removeEldestEntry方法的实现,这里默认为false
removeEldest = removeEldestEntry(eldest);
} finally {
size--;
}
if (removeEldest) {
removeEntryForKey(eldest.key);
}
}
//调用HashMap的addEntry方法
super.addEntry(hash, key, value, bucketIndex);
}
//创建节点,并将该节点插入到链表尾部
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> old = table[bucketIndex];
LinkedHashMapEntry<K,V> e = new LinkedHashMapEntry<>(hash, key, value, old);
table[bucketIndex] = e;
//并将其移到双向链表的尾部
e.addBefore(header);
size++;
}

在上面的addEntry方法中有一个removeEldestEntry方法,这个方法可以被覆写,比如可以将该方法覆写为如果设定的内存已满,则返回true,这样就可以将最近最少使用的节点(header后的节点)删除掉。

为什么这个方法始终返回false?

结合上面的addEntry(int hash,K key,V value,int bucketIndex)方法,这样设计可以使LinkedHashMap成为一个正常的Map,不会去移除“最老”的节点。 为什么不在代码中直接去除这部分逻辑而是设计成这样呢?这为开发者提供了方便,若希望将Map当做Cache来使用,并且限制大小,只需继承LinkedHashMap并重写removeEldestEntry(Entry<K,V> eldest)方法,像这样:

1
2
3
4
private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}

总结一下

只要是put进来的新元素,不管accessOrder标志位是什么,均将新元素放到双链表尾部,并且可以在需要实现Lru算法时时覆写removeEldestEntry方法,剔除最近最少使用的节点。

3.4 get分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//覆写HashMap中的get方法,通过getEntry方法获取Entry对象。
//注意这里的recordAccess方法,
//如果链表中元素的排序规则是按照插入的先后顺序排序的话,该方法什么也不做,
//如果链表中元素的排序规则是按照访问的先后顺序排序的话,则将e移到链表的末尾处。
public V get(Object key) {
LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}

get(Object key)方法通过HashMap的getEntry(Object key)方法获取节点,并返回该节点的value值,获取节点如果为null则返回null。通过key获取value,与HashMap的区别是:当LinkedHashMap按访问顺序排序的时候,会将访问的当前节点移到链表尾部(头结点的前一个节点)。

到这里我们来具体总结一下accessOrder标志位的作用原理。

1、accessOrder不起作用

对于put操作时,不管accessOrder标志位是什么,我们都将节点插入到链表的尾部,但是呢,可以在需要实现Lru算法时时覆写removeEldestEntry方法,剔除最近最少使用的节点。

2、accessOrder起作用

当我们进行put操作是,如果key不等于null的话,会调用recordAccess方法,在该方法中accessOrder就得起作用了,如果accessOrder为fasle时,什么也不做,也就是说当我们放入已经存在Key的键值对,它在双链表中的位置是不会变的。accessOrder设置为true时,put操作会将相关元素放置到双链表的尾部。

另外一种情况就是get操作,get操作我们同时也会调用recordAccess方法,对于这个方法,我们需要判断accessOrder的状态,如果accessOrder为fasle时,什么也不做,也就是说当我们放入已经存在Key的键值对,它在双链表中的位置是不会变的。accessOrder设置为true时,put操作会将相关元素放置到双链表的尾部。在缓存的角度来看,这就是所谓的“脏数据”,即最近被访问过的数据,因此在需要清理内存时(添加进新元素时),就可以将双链表头节点(空节点)后面那个节点剔除。

3.5 不常用方法

到此为止,基本上LinkedHashMap比较重要的方法就分析过了,还剩一些比较不重要的方法,我们一次性给它注视下,稍微看下。

1
2
3
4
5
6
7
8
9
10
//
@Override
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
for (LinkedHashMapEntry<K,V> e = header.after; e != header; e = e.after) {
int index = indexFor(e.hash, newCapacity);
e.next = newTable[index];
newTable[index] = e;
}
}

transfer(HashMap.Entry[] newTable)方法和init()方法一样也在HashTable中被调用。transfer(HashMap.Entry[] newTable)方法在HashMap调用resize(int newCapacity)方法的时候被调用。根据链表节点e的哈希值计算e在新容量的table数组中的索引,并将e插入到计算出的索引所引用的链表中。

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean containsValue(Object value) {
// Overridden to take advantage of faster iterator
if (value==null) {
for (LinkedHashMapEntry e = header.after; e != header; e = e.after)
if (e.value==null)
return true;
} else {
for (LinkedHashMapEntry e = header.after; e != header; e = e.after)
if (value.equals(e.value))
return true;
}
return false;
}

重写父类的containsValue(Object value)方法,直接通过header遍历链表判断是否有值和value相等,利用双向循环链表的特点进行查询,少了对数组的外层for循环 ,而不用查询table数组。

1
2
3
4
public void clear() {
super.clear();
header.before = header.after = header;
}

clear()方法先调用父类的方法clear()方法,之后将链表的header节点的before和after引用都指向header自身,即header节点就是一个双向循环链表。这样就无法访问到原链表中剩余的其他节点,他们都将被GC回收。清空HashMap的同时,将双向链表还原为只有头结点的空链表。

以上便是LinkedHashMap源码主要方法的分析,到这里就要结束了,我们来总结一下关于HashMap和LinkedHashMap的相关东西。

四。总结

对于LinkedHashMap,我们总结了以下几点内容:

1、由于LinkedHashMap继承自HashMap,所以它不仅像HashMap那样对其进行基于哈希表和单链表的Entry数组+ next链表的存储方式,而且还结合了LinkedList的优点,为每个Entry节点增加了前驱和后继,并增加了一个为header头结点,构造了一个双向循环链表。(多一个以header为头结点的双向循环链表,也就是说,每次put进来KV,除了将其保存到对哈希表中的对应位置外,还要将其插入到双向循环链表的尾部。)

2、LinkedHashMap的属性比HashMap多了一个accessOrder属性。当它false时,表示双向链表中的元素按照Entry插入LinkedHashMap到中的先后顺序排序,即每次put到LinkedHashMap中的Entry都放在双向链表的尾部,这样遍历双向链表时,Entry的输出顺序便和插入的顺序一致,这也是默认的双向链表的存储顺序;当它为true时,表示双向链表中的元素按照访问的先后顺序排列,可以看到,虽然Entry插入链表的顺序依然是按照其put到LinkedHashMap中的顺序,但put和get方法均有调用recordAccess方法(put方法在key相同,覆盖原有的Entry的情况下调用recordAccess方法),该方法判断accessOrder是否为true,如果是,则将当前访问的Entry(put进来的Entry或get出来的Entry)移到双向链表的尾部(key不相同时,put新Entry时,会调用addEntry,它会调用creatEntry,该方法同样将新插入的元素放入到双向链表的尾部,既符合插入的先后顺序,又符合访问的先后顺序,因为这时该Entry也被访问了),否则,什么也不做。

3、构造函数中有设置accessOrder的方法,如果我们需要实现LRU算法时,就需要将accessOrder的值设定为TRUE。

4、在HashMap的put方法中,如果key不为null时且哈希表中已经在存在时,循环遍历table[i]中的链表时会调用recordAccess方法,而在HashMap中这个方法是个空方法,在LinkedHashMap中则实现了该方法,该方法会判断accessOrder是否为true,如果为true,它会将当前访问的Entry(在这里指put进来的Entry)移动到双向循环链表的尾部,从而实现双向链表中的元素按照访问顺序来排序(最近访问的Entry放到链表的最后,这样多次下来,前面就是最近没有被访问的元素,在实现、LRU算法时,当双向链表中的节点数达到最大值时,将前面的元素删去即可,因为前面的元素是最近最少使用的),否则什么也不做。


关于作者

github: https://github.com/crazyandcoder
博客: http://crazyandcoder.github.io
掘金:https://juejin.im/user/56b96af96240b8005865df59/share

参考链接

1、http://www.cnblogs.com/chenpi/p/5294077.html
2、http://blog.csdn.net/jzhf2012/article/details/8540688
3、http://blog.csdn.net/ns_code/article/details/37867985
4、http://www.cnblogs.com/hzmark/archive/2012/12/26/LinkedHashMap.html