本文是对 JDK1.8 中 LinkedHashMap 的分析与总结，在阅读源码的同时加深对其提供的方法的使用，以便更好的理解。

概述

之前说到的 HashMap 在存储键值对的时候是无序的，在对 HashMap 进行遍历的时候，遍历顺序和之前的 put 顺序是不一样的。而 LinkedHashMap 继承了 HashMap，实现了 Map 接口，其内部维护了一个双向链表，该链表用于保持在插入、删除、修改键值对时的先后顺序，同时也提供了维护键值对顺序的相关方法。

1

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

此外，LinkedHashMap 不是线程安全的，但允许 key 或 value 为 null。根据链表中元素的顺序可以将 LinkedHashMap 的迭代顺序分为两类：一类是按照插入节点的顺序进行迭代，另一类是通过指定accessOrder参数为true（默认为 flase），则可以按照访问的顺序进行迭代。

通过下图可知，由于引入了双向链表，则对于每个节点除了存储具体的键值对以外，还有用于维护顺序的前驱和后继，因此要比 HashMap 占用跟多的额外空间。head指向双向链表的头部，tail指向双向链表的尾部，而新加入的节点将会链接在tail引用指向的节点后面，节点插入完成以后，tail会再移动到新的节点上。

Entry

桶数组存储的是键值对，也就是一个键值对就是一个 Entry，LinkedHashMap 的内部类 Entry 继承自 HashMap 中的内部类 Node，新增的 before 和 after 用于维护整个双向链表，HashMap 与 LinkedHashMap 的区别如下所示：

其中，head 和 tail 分别指向双向链表的头和尾，accessOrder 属性默认为 false，即采用插入节点的顺序进行迭代，如果将其置为 true，则就变成按照访问的顺序进行迭代了。这里需要注意一点的是，由于 LinkedHashMap 的桶数组上也会存在链表，所以这里的 next 维护的是链表中的索引，而 before 和 after 维护的是双向链表。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before; 
    Entry<K,V> after;

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

transient LinkedHashMap.Entry<K,V> head;

transient LinkedHashMap.Entry<K,V> tail;

final boolean accessOrder;

构造方法

LinkedHashMap 在 HashMap 的基础上，实现了 5 个构造方法：

第一个构造方法：构造一个指定初始容量和指定负载因子的空 LinkedHashMap；
第二个构造方法：构造一个指定初始容量和默认负载因子为 0.75 的空 LinkedHashMap；
第三个构造方法：构造一个默认初始容量为 16 和默认负载因子为 0.75 的空 LinkedHashMap；
第四个构造方法：构造一个与指定 Map 具有相同映射和默认负载因子是 0.75 的 LinkedHashMap；
第五个构造方法：构造一个指定初始容量和指定负载因子的具有指定迭代顺序的空 LinkedHashMap。

源码如下所示：

 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


// 第一个构造方法
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 的 put 方法，但重写了newNode()方法，在每次构建新节点时，通过linkNodeLast()方法将新节点链接在双向链表的尾部。而 newNode() 方法会在 HashMap 中的 putVal() 方法中被调用，如下所示：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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);
    // 将 Entry 链接在双向链表的尾部
    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 链接在链表尾部
        p.before = last;
        last.after = p;
    }
}

除此之外，还有以下 3 个方法，这些方法在 HashMap 中的 put、get、remove 方法中有被调用，用于在进行相关的操作之后，通过回调的方式，让 LinkedHashMap 有机会做一些后置操作。

1
2
3
4
5


void afterNodeRemoval(Node<K,V> e) { }

void afterNodeInsertion(boolean evict) { }

void afterNodeAccess(Node<K,V> e) { }

其中，afterNodeAccess方法用于将当前节点 e 移至链表的尾部，只有当 accessOrder 属性为 true 的时候，才会执行此方法，在 HashMap 中 putVal 方法就调用了该方法。

对于afterNodeInsertion方法可以通过 HashMap 中的 removeNode 方法将链表的头节点删掉，在 HashMap 中的 putVal 方法中就调用了 afterNodeInsertion 方法。其中，可以通过覆写 afterNodeInsertion 方法里面的removeEldestEntry方法实现 LRU 算法。

对于afterNodeRemoval方法来说，由于 LinkedHashMap 的删除方法是使用 HashMap 实现的。在删除节点后，LinkedHashMap 会通过 afterNodeRemoval 方法将被删除的节点从双向链表中删除。

删除节点

正如上面所说，LinkedHashMap 会调用 HashMap 的删除方法，但 HashMap 中的删除方法并不会维护 LinkedHashMap 中的双向链表。所以，正是有了回调方法afterNodeRemoval，才能将被删除的节点移除。具体的删除过程需要结合 HashMap 中的 removeNode 方法进行查看，假如想要删除链表中的某个节点，首先需要找到待删除节点的桶位置，然后遍历该桶位置上的链表，找到该待删除的节点后就从单链表中移除，此时由于需要维护 LinkedHashMap 中的双向链表的指向，所以最后还需要在双向链表中移除该节点。

源码如下所示：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    // b 为空，说明 p 是头节点
    if (b == null)
        head = a;
    else
        b.after = a;
    // a 为空，说明 p 是尾节点
    if (a == null)
        tail = b;
    else
        a.before = b;
}

重写的方法

LinkedHashMap 重写了 HashMap 中的containsValue方法，如下所示。该方法通过按照插入顺序的的方式使用双向链表来查找是否包含 value，而 HashMap 中的 containsValue 方法是通过遍历桶的方式进行查找的。

 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


// HashMap
public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}


// LinkedHashMap
public boolean containsValue(Object value) {
    for (LinkedHashMap.Entry<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;
}

总结

由于可以通过设置 accessOrder 的属性为 true，将 LinkedHashMap 调整为按照访问顺序维护链表。所以，当在调用 get 等方法的时候，会将这些方法访问到的节点移动到链表的尾部，即让 tail 指向被访问到的节点，然后再调整双向链表的指向，通过这种维护节点的方式来实现按照访问顺序进行遍历。

此外，LinkedHashMap 重写了 containsValue 方法而没有重写 containsKey 方法，是因为通过使用 HashMap 中的 containsKey 方法，可以通过对 key 取 hash 值来快速定位桶的位置，利用了数组的查找优势，这样做的效率是很高的。假如重写了 containsKey 方法，则会循环比对链表的 key 是否相等，无异于降低了查找效率。

参考

JDK1.8源码分析之LinkedHashMap（二）

LinkedHashMap源码解析（JDK8）

JDK 源码之集合类 LinkedHashMap

Contents

概述

Entry

构造方法

新增节点

删除节点

重写的方法

总结

参考