1. 简介

Map是一种关联容器，其中键是唯一的，每个键都有与之对应的值，我们可以通过键获取到唯一的值。JDK中，HashMap是其中的一种实现，只不过HashMap是无序的，不能记录插入顺序与访问顺序，而LinkedHashMap恰好能记录插入顺序或访问顺序，至于为什么能够实现，是因为它在内部维护了一个链表专门来记录插入顺序或访问顺序，接着我们来剖析其内部实现。

2. 实现

类继承关系

从下面的类继承关系可以看出LinkedHashMap是继承了HashMap的，内部复用了HashMap的代码。

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

结点结构

这里的Entry类继承了HashMap.Node类，并增加了两个引用字段before, after，可以看出该链表是一个双向链表,这个类其实是为链表准备的，两个引用分别指向当前链表结点前后结点。

1
2
3
4
5
6
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);
    }
}

因为从JDK8开始，HashMap开始采用红黑树，当每个桶中的链表长度大于8时会转为红黑树存储。所以为了保证TreeNode能够插入到LinkedHashMap维护的链表，TreeNode需要继承LinkedHashMap.Entry。

1
2
3
4
5
6
7
8
9
10
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}

属性

1
2
3
4
5
6
// 链表的头结点
transient LinkedHashMap.Entry<K,V> head;
// 链表的尾结点
transient LinkedHashMap.Entry<K,V> tail;
// 为false表示链表中结点按照键值对的插入顺序排序，为true表示按照访问顺序，即最近插入与访问的结点都在链表尾部
final boolean accessOrder;

构造函数

以下构造函数都是先调用父类的构造函数创建一个HashMap，接着将accessOrder设置为false表示按照链表按照键值对插入顺序排序

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

// 这里讲accessOrder设置为给定值
public LinkedHashMap(int initialCapacity,
                        float loadFactor,
                        boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

创建结点

每次我们创建HashMap使用的结点都使用以下两个方法创建，内部实现会维护双向链表

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
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);
    // 将该结点添加到双向链表尾部
    linkNodeLast(p);
    return p;
}


TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
    // 创建一个红黑树结点
    TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
    // 将该结点添加到双向链表尾部
    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.before = last;
        last.after = p;
    }
}

get方法

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
public V get(Object key) {
    Node<K,V> e;
    // 找到key对应的Node结点，为null则不存在，返回null
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 如果accessOrder为true则调用afterNodeAccess方法将最近访问的结点从链表中移动到链表尾部
    if (accessOrder)
        afterNodeAccess(e);
    //返回找到的值
    return e.value;
}

// 将结点e移动到链表尾部
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // 当按accessOrder为true按访问次序排序并且尾结点不是当前需要移动的结点才需要移动
    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;
    }
}

其他方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 执行remove方法从哈希表中删除键值对后调用，将该结点从链表中移除
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;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

// 执行put方法成功插入后调用，目的是移除最旧的结点，即头结点
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}