HashMap和双向链表合二为一即是LinkedHashMap。所谓LinkedHashMap,其落脚点在HashMap,因此更准确地说,它是一个将所有Entry节点链入一个双向链表的HashMap。由于LinkedHashMap是HashMap的子类,所以LinkedHashMap自然会拥有HashMap的所有特性。比如,LinkedHashMap的元素存取过程基本与HashMap基本类似,只是在细节实现上稍有不同。当然,这是由LinkedHashMap本身的特性所决定的,因为它额外维护了一个双向链表用于保持迭代顺序。此外,LinkedHashMap可以很好的支持LRU算法,笔者在第七节便在LinkedHashMap的基础上实现了一个能够很好支持LRU的结构。

LinkedHashMap 概述

  HashMap 是 Java Collection Framework 的重要成员,也是Map族(如下图所示)中我们最为常用的一种。不过遗憾的是,HashMap是无序的,也就是说,迭代HashMap所得到的元素顺序并不是它们最初放置到HashMap的顺序。HashMap的这一缺点往往会造成诸多不便,因为在有些场景中,我们确需要用到一个可以保持插入顺序的Map。庆幸的是,JDK为我们解决了这个问题,它为HashMap提供了一个子类 —— LinkedHashMap。虽然LinkedHashMap增加了时间和空间上的开销,但是它通过维护一个额外的双向链表保证了迭代顺序。特别地,该迭代顺序可以是插入顺序,也可以是访问顺序。因此,根据链表中元素的顺序可以将LinkedHashMap分为:保持插入顺序的LinkedHashMap保持访问顺序的LinkedHashMap,其中LinkedHashMap的默认实现是按插入顺序排序的。

  本质上,HashMap和双向链表合二为一即是LinkedHashMap。所谓LinkedHashMap,其落脚点在HashMap,因此更准确地说,它是一个将所有Entry节点链入一个双向链表双向链表的HashMap。在LinkedHashMapMap中,所有put进来的Entry都保存在如下面第一个图所示的哈希表中,但由于它又额外定义了一个以head为头结点的双向链表(如下面第二个图所示),因此对于每次put进来Entry,除了将其保存到哈希表中对应的位置上之外,还会将其插入到双向链表的尾部。

              


  更直观地,下图很好地还原了LinkedHashMap的原貌:HashMap和双向链表的密切配合和分工合作造就了LinkedHashMap。特别需要注意的是,next用于维护HashMap各个桶中的Entry链,before、after用于维护LinkedHashMap的双向链表,虽然它们的作用对象都是Entry,但是各自分离,是两码事儿。

​ 特别地,由于LinkedHashMap是HashMap的子类,所以LinkedHashMap自然会拥有HashMap的所有特性。比如,LinkedHashMap也最多只允许一条Entry的键为Null(多条会覆盖),但允许多条Entry的值为Null。此外,LinkedHashMap 也是 Map 的一个非同步的实现。此外,LinkedHashMap还可以用来实现LRU (Least recently used, 最近最少使用)算法,这个问题会在下文的特别谈到。

LinkedHashMap 在 JDK 中的定义

1、类结构定义

  LinkedHashMap继承于HashMap,其在JDK中的定义为:

1
2
3
4
5
6
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V> {

...
}

2、成员变量定义

  与HashMap相比,LinkedHashMap增加了两个属性用于保证迭代顺序,分别是 双向链表头结点header标志位accessOrder (值为true时,表示按照访问顺序迭代;值为false时,表示按照插入顺序迭代)。

1
2
3
4
5
6
7
8
9
10
11
12
/**
* The head of the doubly linked list.
*/
private transient Entry<K,V> header; // 双向链表的表头元素

/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
*
* @serial
*/
private final boolean accessOrder; //true表示按照访问顺序迭代,false时表示按照插入顺序

3、成员方法定义

  从下图我们可以看出,LinkedHashMap中并增加没有额外方法。也就是说,LinkedHashMap与HashMap在操作上大致相同,只是在实现细节上略有不同罢了。

4、基本元素 Entry

  LinkedHashMap采用的hash算法和HashMap相同,但是它重新定义了Entry。LinkedHashMap中的Entry增加了两个指针 beforeafter,它们分别用于维护双向链接列表。特别需要注意的是,next用于维护HashMap各个桶中Entry的连接顺序,before、after用于维护Entry插入的先后顺序的,源代码如下:

1
2
3
4
5
6
7
8
9
10
private static class Entry<K,V> extends HashMap.Entry<K,V> {

// These fields comprise the doubly linked list used for iteration.
Entry<K,V> before, after;

Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
...
}

  形象地,HashMap与LinkedHashMap的Entry结构示意图如下图所示:

LinkedHashMap 的构造函数

  LinkedHashMap 一共提供了五个构造函数,它们都是在HashMap的构造函数的基础上实现的,分别如下:

1、LinkedHashMap()

  该构造函数意在构造一个具有 默认初始容量 (16)和默认负载因子(0.75)的空 LinkedHashMap,是 Java Collection Framework 规范推荐提供的,其源码如下:

1
2
3
4
5
6
7
8
    /**
* Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
* with the default initial capacity (16) and load factor (0.75).
*/
public LinkedHashMap() {
super(); // 调用HashMap对应的构造函数
accessOrder = false; // 迭代顺序的默认值
}

2、LinkedHashMap(int initialCapacity, float loadFactor)

  该构造函数意在构造一个指定初始容量和指定负载因子的空 LinkedHashMap,其源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
   /**
* Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
* with the specified initial capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor); // 调用HashMap对应的构造函数
accessOrder = false; // 迭代顺序的默认值
}

3、LinkedHashMap(int initialCapacity)

  该构造函数意在构造一个指定初始容量和默认负载因子 (0.75)的空 LinkedHashMap,其源码如下:

1
2
3
4
5
6
7
8
9
10
11
    /**
* Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
* with the specified initial capacity and a default load factor (0.75).
*
* @param initialCapacity the initial capacity
* @throws IllegalArgumentException if the initial capacity is negative
*/
public LinkedHashMap(int initialCapacity) {
super(initialCapacity); // 调用HashMap对应的构造函数
accessOrder = false; // 迭代顺序的默认值
}

4、LinkedHashMap(Map<? extends K, ? extends V> m)

  该构造函数意在构造一个与指定 Map 具有相同映射的 LinkedHashMap,其 初始容量不小于 16 (具体依赖于指定Map的大小),负载因子是 0.75,是 Java Collection Framework 规范推荐提供的,其源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with
* the same mappings as the specified map. The <tt>LinkedHashMap</tt>
* instance is created with a default load factor (0.75) and an initial
* capacity sufficient to hold the mappings in the specified map.
*
* @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); // 调用HashMap对应的构造函数
accessOrder = false; // 迭代顺序的默认值
}12345678910111213

5、LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

  该构造函数意在构造一个指定初始容量和指定负载因子的具有指定迭代顺序的LinkedHashMap,其源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* Constructs an empty <tt>LinkedHashMap</tt> instance with the
* specified initial capacity, load factor and ordering mode.
*
* @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); // 调用HashMap对应的构造函数
this.accessOrder = accessOrder; // 迭代顺序的默认值
}

  初始容量 和负载因子是影响HashMap性能的两个重要参数。同样地,它们也是影响LinkedHashMap性能的两个重要参数。此外,LinkedHashMap 增加了双向链表头结点 header和标志位 accessOrder两个属性用于保证迭代顺序。

6、init 方法

  从上面的五种构造函数我们可以看出,无论采用何种方式创建LinkedHashMap,其都会调用HashMap相应的构造函数。事实上,不管调用HashMap的哪个构造函数,HashMap的构造函数都会在最后调用一个init()方法进行初始化,只不过这个方法在HashMap中是一个空实现,而在LinkedHashMap中重写了它用于初始化它所维护的双向链表。例如,HashMap的参数为空的构造函数以及init方法的源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    /**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}

/**
* Initialization hook for subclasses. This method is called
* in all constructors and pseudo-constructors (clone, readObject)
* after HashMap has been initialized but before any entries have
* been inserted. (In the absence of this method, readObject would
* require explicit knowledge of subclasses.)
*/
void init() {
}

  在LinkedHashMap中,它重写了init方法以便初始化双向列表,源码如下:

1
2
3
4
5
6
7
8
9
 /**
* Called by superclass constructors and pseudoconstructors (clone,
* readObject) before any entries are inserted into the map. Initializes
* the chain.
*/
void init() {
header = new Entry<K,V>(-1, null, null, null);
header.before = header.after = header;
}

  因此,我们在创建LinkedHashMap的同时就会不知不觉地对双向链表进行初始化。

LinkedHashMap 的快速存取

  我们知道,在HashMap中最常用的两个操作就是:put(Key,Value) 和 get(Key)。同样地,在 LinkedHashMap 中最常用的也是这两个操作。对于put(Key,Value)方法而言,LinkedHashMap完全继承了HashMap的 put(Key,Value) 方法,只是对put(Key,Value)方法所调用的recordAccess方法和addEntry方法进行了重写;对于get(Key)方法而言,LinkedHashMap则直接对它进行了重写。下面我们结合JDK源码看 LinkedHashMap 的存取实现。

1、LinkedHashMap 的存储实现 : put(key, vlaue)

  上面谈到,LinkedHashMap没有对 put(key,vlaue) 方法进行任何直接的修改,完全继承了HashMap的 put(Key,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
    /**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with key, or null if there was no mapping for key.
* Note that a null return can also indicate that the map previously associated null with key.
*/
public V put(K key, V value) {

//当key为null时,调用putForNullKey方法,并将该键值对保存到table的第一个位置
if (key == null)
return putForNullKey(value);

//根据key的hashCode计算hash值
int hash = hash(key.hashCode());

//计算该键值对在数组中的存储位置(哪个桶)
int i = indexFor(hash, table.length);

//在table的第i个桶上进行迭代,寻找 key 保存的位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//判断该条链上是否存在hash值相同且key值相等的映射,若存在,则直接覆盖 value,并返回旧value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this); // LinkedHashMap重写了Entry中的recordAccess方法--- (1)
return oldValue; // 返回旧值
}
}

modCount++; //修改次数增加1,快速失败机制

//原Map中无该映射,将该添加至该链的链头
addEntry(hash, key, value, i); // LinkedHashMap重写了HashMap中的createEntry方法 ---- (2)
return null;
}

  上述源码反映了LinkedHashMap与HashMap保存数据的过程。特别地,在LinkedHashMap中,它对addEntry方法和Entry的recordAccess方法进行了重写。下面我们对比地看一下LinkedHashMap 和HashMap的addEntry方法的具体实现:

LinkedHashMap中的addEntry方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    /**
* This override alters behavior of superclass put method. It causes newly
* allocated entry to get inserted at the end of the linked list and
* removes the eldest entry if appropriate.
*
*/
void addEntry(int hash, K key, V value, int bucketIndex) {

//创建新的Entry,并插入到LinkedHashMap中
createEntry(hash, key, value, bucketIndex); // 重写了HashMap中的createEntry方法

//双向链表的第一个有效节点(header后的那个节点)为最近最少使用的节点,这是用来支持LRU算法的
Entry<K,V> eldest = header.after;
//如果有必要,则删除掉该近期最少使用的节点,
//这要看对removeEldestEntry的覆写,由于默认为false,因此默认是不做任何处理的。
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
//扩容到原来的2倍
if (size >= threshold)
resize(2 * table.length);
}
}

HashMap中的addEntry方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    /**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
//获取bucketIndex处的Entry
Entry<K,V> e = table[bucketIndex];

//将新创建的 Entry 放入 bucketIndex 索引处,并让新的 Entry 指向原来的 Entry
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);

//若HashMap中元素的个数超过极限了,则容量扩大两倍
if (size++ >= threshold)
resize(2 * table.length);
}

​ 由于LinkedHashMap本身维护了插入的先后顺序,因此其可以用来做缓存,14~19行的操作就是用来支持LRU算法的,这里暂时不用去关心它。此外,在LinkedHashMap的addEntry方法中,它重写了HashMap中的createEntry方法,我们接着看一下createEntry方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
void createEntry(int hash, K key, V value, int bucketIndex) { 
// 向哈希表中插入Entry,这点与HashMap中相同
//创建新的Entry并将其链入到数组对应桶的链表的头结点处,
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
table[bucketIndex] = e;

//在每次向哈希表插入Entry的同时,都会将其插入到双向链表的尾部,
//这样就按照Entry插入LinkedHashMap的先后顺序来迭代元素(LinkedHashMap根据双向链表重写了迭代器)
//同时,新put进来的Entry是最近访问的Entry,把其放在链表末尾 ,也符合LRU算法的实现
e.addBefore(header);
size++;
}

  由以上源码我们可以知道,在LinkedHashMap中向哈希表中插入新Entry的同时,还会通过Entry的addBefore方法将其链入到双向链表中。其中,addBefore方法本质上是一个双向链表的插入操作,其源码如下:

1
2
3
4
5
6
7
//在双向链表中,将当前的Entry插入到existingEntry(header)的前面  
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}

  到此为止,我们分析了在LinkedHashMap中put一条键值对的完整过程。总的来说,相比HashMap而言,LinkedHashMap在向哈希表添加一个键值对的同时,也会将其链入到它所维护的双向链表中,以便设定迭代顺序。

LinkedHashSet 的实现

  1. LinkedHashSet概述:

    ​ LinkedHashSet是具有可预知迭代顺序的Set接口的哈希表和链接列表实现。此实现与HashSet的不同之处在于,后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序可为插入顺序或是访问顺序。

    ​ 注意,此实现不是同步的。如果多个线程同时访问链接的哈希Set,而其中至少一个线程修改了该Set,则它必须保持外部同步。

  2. LinkedHashSet的实现:

    ​ 对于LinkedHashSet而言,它继承与HashSet、又基于LinkedHashMap来实现的。

    ​ LinkedHashSet底层使用LinkedHashMap来保存所有元素,它继承与HashSet,其所有的方法操作上又与HashSet相同,因此LinkedHashSet 的实现上非常简单,只提供了四个构造方法,并通过传递一个标识参数,调用父类的构造器,底层构造一个LinkedHashMap来实现,在相关操作上与父类HashSet的操作相同,直接调用父类HashSet的方法即可。LinkedHashSet的源代码如下:

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
public class LinkedHashSet<E>  
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {

private static final long serialVersionUID = -2851667679971038690L;

/**
* 构造一个带有指定初始容量和加载因子的新空链接哈希set。
*
* 底层会调用父类的构造方法,构造一个有指定初始容量和加载因子的LinkedHashMap实例。
* @param initialCapacity 初始容量。
* @param loadFactor 加载因子。
*/
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}

/**
* 构造一个带指定初始容量和默认加载因子0.75的新空链接哈希set。
*
* 底层会调用父类的构造方法,构造一个带指定初始容量和默认加载因子0.75的LinkedHashMap实例。
* @param initialCapacity 初始容量。
*/
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}

/**
* 构造一个带默认初始容量16和加载因子0.75的新空链接哈希set。
*
* 底层会调用父类的构造方法,构造一个带默认初始容量16和加载因子0.75的LinkedHashMap实例。
*/
public LinkedHashSet() {
super(16, .75f, true);
}

/**
* 构造一个与指定collection中的元素相同的新链接哈希set。
*
* 底层会调用父类的构造方法,构造一个足以包含指定collection
* 中所有元素的初始容量和加载因子为0.75的LinkedHashMap实例。
* @param c 其中的元素将存放在此set中的collection。
*/
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
}

​ 在父类HashSet中,专为LinkedHashSet提供的构造方法如下,该方法为包访问权限,并未对外公开。

1
2
3
4
5
6
7
8
9
10
11
12
/** 
* 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。
* 此构造函数为包访问权限,不对外公开,实际只是是对LinkedHashSet的支持。
*
* 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。
* @param initialCapacity 初始容量。
* @param loadFactor 加载因子。
* @param dummy 标记。
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

​ 由上述源代码可见,LinkedHashSet通过继承HashSet,底层使用LinkedHashMap,以很简单明了的方式来实现了其自身的所有功能。

联系我

评论