JDK源码——LinkedHashMap类

摘要

本博文将详细的介绍LinkedHashMap类。

一、LinkedHashMap基础数据结构

我们知道HashMap是无序的，即迭代器的顺序与插入顺序没什么关系。而LinkedHashMap 在 HashMap的基础上增加了顺序：分别为插入顺序和访问顺序。即遍历LinkedHashMap时，可以保持与插入顺序一致的顺序；或者与访问顺序一致的顺序。LinkedHashMap 内部如何实现这两种顺序的呢？它是通过一个双链表来维持的。因此可以将 LinkedHashMap 理解为双链表 + 散列表，或者“有序的散列表”。

一、LinkedHashMap的成员变量

/**
 * 头指针
 */
transient LinkedHashMap.Entry head;

/**
 * 尾指针
 */
transient LinkedHashMap.Entry tail;

/**
 * LinkedHashMap 的迭代顺序：true 为访问顺序；false 为插入顺序。
 */
final boolean accessOrder;

二、LinkedHashMap的节点类

LinkedHashMap 内部有一个嵌套类 Entry，它继承自 HashMap 中的 Node 类，如下：

static class Entry extends HashMap.Node {
    Entry before, after;

    Entry(int hash, K key, V value, Node next) {
        super(hash, key, value, next);
    }
}
static class Node implements Map.Entry {
    final int hash;
    final K key;
    V value;
    Node next;
    Node(int hash, K key, V value, Node next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    // ...
}

该 Entry 类就是 LinkedHashMap 中的节点类。可以看到，它在 Node 类的基础上又增加了 before 和 after 两个变量，它们保存的是节点的前驱和后继（从字面意思也可以进行推测），从而来维护 LinkedHashMap 的顺序。

三、LinkedHashMap的构造器

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

这里的 super() 方法调用了 HashMap 的无参构造器。该构造器方法构造了一个容量为 16（默认初始容量）、负载因子为 0.75（默认负载因子）的空 LinkedHashMap，其顺序为插入顺序。

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

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

public LinkedHashMap(Map