Java类集框架 —— LinkedHashMap源码分析

前言

我们知道HashMap底层是采用数组+单向线性链表/红黑树来实现的，HashMap在扩容或者链表与红黑树转换过程时可能会改变元素的位置和顺序。如果需要保存元素存入或访问的先后顺序，那就需要采用LinkedHashMap了。

LinkedHashMap结构

LinkedHashMap继承自HashMap，它的所有操作和HashMap类似，底层结构也和HashMap一样，只不过为了维护元素的存入/访问顺序，增加了一个双向链表。

LinkedHashMap结构图

LinkedHashMap由数组、单向线性链表、红黑树、双向线性链表组成。如上图：灰色区域为数组，蓝色节点和蓝色箭头为单向链表的引用关系，绿色节点和绿色箭头为红黑树的引用关系，节点中的数字依次表示元素的存入/访问顺序，由橙色的双向箭头表示双向链表的引用关系。

注：在JDK1.7及之前HashMap中没有红黑树，LinkedHashMap中也不存在红黑树。另在JDK1.6及之前，HashMap中的链表为单向环形链表，LinkedHashMap中中的单向链表和双向链表都是环形链表。在JDK1.8，LinkedHashMap中可能会存在红黑树，同时单向链表和双向链表都是线性的。本文是基于JDK1.8来分析的。

LinkedHashMap源码分析

基本属性：

transient LinkedHashMap.Entry<K,V> head;    // 双向链表头节点
transient LinkedHashMap.Entry<K,V> tail;    // 双向链表尾节点
final boolean accessOrder;                  // 是否按照访问顺序排序

head和tail分别记录了双向链表的头节点和尾节点，遍历时通过head或tail就可以按照存入/访问的顺序来取数据。

accessOrder用以表示LinkedHashMap是否按照访问顺序来排序，为true的话表示按照访问顺序排序，为false表示按照存入顺序排序，默认为false。

构造函数：

// 无参构造
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;
}

构造函数都是调用父类HashMap的构造函数。前3个都默认accessOrder为false，LinkedHashMap内部按照存入顺序排序。最后一个构造函数可以指定accessOrder的值。

增：

LinkedHashMap添加数据要调用了父类的HashMap的put方法，在HashMap的源码中，put方法存入元素后，调用了afterNodeAccess和afterNodeInsertion方法，这两个方法在HashMap中都是空方法，LinkedHashMap实现了这两个方法：

void afterNodeAccess(Node<K,V> e) { 
    LinkedHashMap.Entry<K,V> last;
    // 如果按照访问顺序排序，并且添加的元素e不是双向链表的尾节点
    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;
    }
}

afterNodeAccess方法的逻辑就是将当前节点e移动到双向链表的尾部。每次LinkedHashMap中有元素被访问时，就会按照访问先后来排序，先访问的在双向链表中靠前，越后访问的越接近尾部。当然只有当accessOrder为true时，才会执行这个操作。

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

afterNodeInsertion方法意思是evict为true时删除双向链表的头节点。

通过afterNodeAccess和afterNodeInsertion这两个方法，如果当LinkedHashMap的容量达到一定量时，需要保存它的size不变，那么每次添加一个元素到双向链表的尾部，就要删除一个双向链表头部的元素，这相当于实现了LruCache的策略。

删：

删除元素同样也是调用了HashMap的remove方法，在remove方法中，调用了afterNodeRemoval方法。

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

afterNodeRemoval方法就是将e节点从双向链表中删除，更改e前后节点引用关系，使之重新连成完整的双向链表。

改：

LinkedHashMap更改元素的value值，仍是调用put方法，涉及到的逻辑可以看上面的afterNodeAccess和afterNodeInsertion这两个方法。

查：

LinkedHashMap自己实现了get方法。

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

逻辑非常简单，直接调用HashMap的getNode方法，如果需要按照访问先后排序，调用afterNodeAccess更新双向链表排序。

总结

LinkedHashMap继承了HashMap的所有特性，唯一的区别就是LinkedHashMap是一个有序的映射集合，而HashMap则是无序的。LinkedHashMap实现排序的原理就是再内部增加了一个双向链表来记录元素的存入/访问顺序。LinkedHashMap内部是记录的是存入还是访问顺序取决于关键属性accessOrder，默认是按存入顺序记录。