Java集合之LinkedHashMap源码剖析

1.整体结构

LinkedHashMap 是 Java 提供的一个集合类，它继承自 HashMap，并在 HashMap 基础上维护一条双向链表，具备如下特性:

1. 支持遍历时会按照插入顺序有序进行迭代。
2. 支持按照元素访问顺序排序,适用于封装 LRU 缓存工具。
3. 因为内部使用双向链表维护各个节点，所以遍历时的效率和元素个数成正比，相较于和容量成正比的 HashMap 来说，迭代效率会高很多。

LinkedHashMap 逻辑结构如下图所示，它是在 HashMap 基础上在各个节点之间维护一条双向链表，使得原本散列在不同桶位上的节点、链表、红黑树有序关联起来。

2.简单使用

LinkedHashMap 的遍历顺序是有序的，这点跟 HashMap 不同，具体的遍历顺序可以根据 accessOrder 属性配置，默认 false 表示按照插入顺序遍历，true 表示按照访问顺序遍历，结合 removeEldestEntry 方法可以实现一个简单的 LRU 缓存。

// 默认按照插入顺序遍历
LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("key1", "val1");
linkedHashMap.put("key2", "val2");
linkedHashMap.put("key3", "val3");
linkedHashMap.put("key4", "val4");
linkedHashMap.put("key5", "val5");
for (Map.Entry<String, String> entry : linkedHashMap.entrySet()) {
    System.out.println(entry.getKey() + "-" + entry.getValue());
}

// 按照访问顺序遍历
LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);
linkedHashMap.put("key1", "val1");
linkedHashMap.put("key2", "val2");
linkedHashMap.put("key3", "val3");
linkedHashMap.put("key4", "val4");
linkedHashMap.put("key5", "val5");
linkedHashMap.get("key3");
linkedHashMap.get("key1");
for (Map.Entry<String, String> entry : linkedHashMap.entrySet()) {
    System.out.println(entry.getKey() + "-" + entry.getValue());
}

public class LinkedHashMapTest {
    public static void main(String[] args) {
        LRUCache<String, String> cache = new LRUCache<>(3);
        cache.put("key1", "val1");
        cache.put("key2", "val2");
        cache.put("key3", "val3");
        cache.put("key4", "val4");
        cache.put("key5", "val5");
        for (Map.Entry<String, String> entry : cache.entrySet()) {
            System.out.println(entry.getKey() + "-" + entry.getValue());
        }
    }

    static class LRUCache<K, V> extends LinkedHashMap<K, V> {
        private final int capacity;

        public LRUCache(int capacity) {
            super(capacity, 0.75f, true);
            this.capacity = capacity;
        }

        /**
         * 判断size超过容量时返回true，告知LinkedHashMap移除最旧的缓存项(即链表的第一个元素)
         */
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > capacity;
        }
    }
}

3.节点设计

• LinkedHashMap 的节点内部类 Entry 基于 HashMap 的基础上，增加 before 和 after 指针使节点具备双向链表的特性。

• HashMap 的树节点 TreeNode 继承了具备双向链表特性的 LinkedHashMap 的 Entry。

为什么 HashMap 的树节点 TreeNode 要通过 LinkedHashMap 获取双向链表的特性呢?为什么不直接在 Node 上实现前驱和后继指针呢?

先来回答第一个问题，我们都知道 LinkedHashMap 是在 HashMap 基础上对节点增加双向指针实现双向链表的特性,所以 LinkedHashMap 内部链表转红黑树时，对应的节点会转为树节点 TreeNode,为了保证使用 LinkedHashMap 时树节点具备双向链表的特性，所以树节点 TreeNode 需要继承 LinkedHashMap 的 Entry。

再来说说第二个问题，我们直接在 HashMap 的节点 Node 上直接实现前驱和后继指针,然后 TreeNode 直接继承 Node 获取双向链表的特性为什么不行呢？其实这样做也是可以的。只不过这种做法会使得使用 HashMap 时存储键值对的节点类 Node 多了两个没有必要的引用，占用没必要的内存空间。

所以，为了保证 HashMap 底层的节点类 Node 没有多余的引用，又要保证 LinkedHashMap 的节点类 Entry 拥有存储链表的引用，设计者就让 LinkedHashMap 的节点 Entry 去继承 Node 并增加存储前驱后继节点的引用 before、after，让需要用到链表特性的节点去实现需要的逻辑。然后树节点 TreeNode 再通过继承 Entry 获取 before、after 两个指针。

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

但是这样做，不也使得使用 HashMap 时的 TreeNode 多了两个没有必要的引用吗?这不也是一种空间的浪费吗？

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
  //略
}

对于这个问题,引用作者的一段注释，作者们认为在良好的 hashCode 算法时，HashMap 转红黑树的概率不大。就算转为红黑树变为树节点，也可能会因为移除或者扩容将 TreeNode 变为 Node，所以 TreeNode 的使用概率不算很大，对于这一点资源空间的浪费是可以接受的。

4.构造方法

LinkedHashMap 构造方法有 4 个实现也比较简单，直接调用父类即 HashMap 的构造方法完成初始化。

public LinkedHashMap() {
    super();
    accessOrder = false;
}

public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

public LinkedHashMap(int initialCapacity,
    float loadFactor,
    boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

我们上面也提到了，默认情况下 accessOrder 为 false，如果我们要让 LinkedHashMap 实现键值对按照访问顺序排序(即将最久未访问的元素排在链表首部、最近访问的元素移动到链表尾部)，需要调用第 4 个构造方法将 accessOrder 设置为 true。

5.源码分析

get 方法是 LinkedHashMap 增删改查操作中唯一一个重写的方法， accessOrder 为 true 的情况下， 它会在元素查询完成之后，将当前访问的元素移到链表的末尾。

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

关键点在于 afterNodeAccess 方法的实现，这个方法负责将元素移动到链表末尾。

void afterNodeAccess(Node<K,V> e) { // move node to last
    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;
    }
}

LinkedHashMap 并没有对 remove 方法进行重写，而是直接继承 HashMap 的 remove 方法，为了保证键值对移除后双向链表中的节点也会同步被移除，LinkedHashMap 重写了 HashMap 的空实现方法 afterNodeRemoval。

void afterNodeRemoval(Node<K,V> e) { // unlink
	//获取当前节点p、以及e的前驱节点b和后继节点a
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    //将p的前驱和后继指针都设置为null，使其和前驱、后继节点断开联系
    p.before = p.after = null;

	//如果前驱节点为空，则说明当前节点p是链表首节点，让head指针指向后继节点a即可
    if (b == null)
        head = a;
    else
    //如果前驱节点b不为空，则让b直接指向后继节点a
        b.after = a;

	//如果后继节点为空，则说明当前节点p在链表末端，所以直接让tail指针指向前驱节点a即可
    if (a == null)
        tail = b;
    else
    //反之后继节点的前驱指针直接指向前驱节点
        a.before = b;
}

同样的 LinkedHashMap 并没有实现插入方法，而是直接继承 HashMap 的所有插入方法交由用户使用，但为了维护双向链表访问的有序性，它做了这样两件事:

1. 重写 afterNodeAccess(上文提到过),如果当前被插入的 key 已存在 map 中，因为 LinkedHashMap 的插入操作会将新节点追加至链表末尾，所以对于存在的 key 则调用 afterNodeAccess 将其放到链表末端。
2. 重写了 HashMap 的 afterNodeInsertion 方法，当 removeEldestEntry 返回 true 时，会将链表首节点移除。

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    //如果evict为true且队首元素不为空以及removeEldestEntry返回true，则说明我们需要最老的元素(即在链表首部的元素)移除。
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        //获取链表首部的键值对的key
        K key = first.key;
        //调用removeNode将元素从HashMap的bucket中移除，并和LinkedHashMap的双向链表断开，等待gc回收
        removeNode(hash(key), key, null, false, true);
    }
}

6.遍历性能

LinkedHashMap 维护了一个双向链表来记录数据插入的顺序，因此在迭代遍历生成的迭代器的时候，是按照双向链表的路径进行遍历的。这一点相比于 HashMap 那种遍历整个 bucket 的方式来说，高效得多。

这一点我们可以从两者的迭代器中得以印证，先来看看 HashMap 的迭代器，可以看到 HashMap 迭代键值对时会用到一个 nextNode 方法，该方法会返回 next 指向的下一个元素，并会从 next 开始遍历 bucket 找到下一个 bucket 中不为空的元素 Node。

final class EntryIterator extends HashIterator
implements Iterator < Map.Entry < K, V >> {
    public final Map.Entry < K, V > next() {
        return nextNode();
    }
}

//获取下一个Node
final Node < K, V > nextNode() {
    Node < K, V > [] t;
    //获取下一个元素next
    Node < K, V > e = next;
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    if (e == null)
        throw new NoSuchElementException();
    //将next指向bucket中下一个不为空的Node
    if ((next = (current = e).next) == null && (t = table) != null) {
        do {} while (index < t.length && (next = t[index++]) == null);
    }
    return e;
}

相比之下 LinkedHashMap 的迭代器则是直接使用通过 after 指针快速定位到当前节点的后继节点，简洁高效需多。

final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator < Map.Entry < K, V >> {
    public final Map.Entry < K, V > next() {
        return nextNode();
    }
}
//获取下一个Node
final LinkedHashMap.Entry < K, V > nextNode() {
    //获取下一个节点next
    LinkedHashMap.Entry < K, V > e = next;
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    if (e == null)
        throw new NoSuchElementException();
    //current 指针指向当前节点
    current = e;
    //next直接当前节点的after指针快速定位到下一个节点
    next = e.after;
    return e;
}