[数据结构与算法]LinkedHashMap源码解析

写在前面的话:本文是基于读者已经了解了一部分HashMap源码的基础上写的，如果还没有看过HashMap的源码，可以点击链接跳转:HashMap详解，拿过来吧你（部分）

1、LinkedHashMap介绍

这个类是HashMap的子类，只不过在原有的Node类之上，增加了两个指针域before和after，before用于指向这个节点最近之前添加的节点，after将指向其之后再添加的节点，由于大部分内容继承于HashMap，所以它也是线程不安全的。

它不仅解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题，而且LinkedHashMap 对访问顺序也提供了相关支持。在一些场景下，该特性很有用，比如缓存。

2、属性

// 允许对象被序列化
private static final long serialVersionUID = 3801124242820219131L;

// 序列化后对象的内部存储的元素不会序列化出去
transient LinkedHashMap.Entry<K,V> head;

// 序列化后对象的内部存储的元素不会序列化出去
transient LinkedHashMap.Entry<K,V> tail;

// 
final boolean accessOrder;

3、构造器

/**
 * 指定初始化容量和负载因子创建集合对象
 * 并指定不要按照访问的顺序排序，要默认使用插入顺序排序
 */
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

/**
 * 指定集合容量创建集合对象
 * 并指定不要按照访问的顺序排序，要默认使用插入顺序排序
 */
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

/**
 * 默认的构造器，指指定负载因子为0.75
 * 并指定不要按照访问的顺序排序，要默认使用插入顺序排序
 */
public LinkedHashMap() {
    super();
    accessOrder = false;
}

/**
 * 使用一个集合去初始化LinkedHashMap
 * 并指定不要按照访问的顺序排序，要默认使用插入顺序排序
 */
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;
}

4、节点类

是继承于HashMap.Node类的，之所以要继承重写这个类，主要是为了既能增加两个指针域，而且不需要编写重复代码；而且重写这个类，方便后续的newNode方法的重写。

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) {
        // 初始化HashMap$node的原有属性
        super(hash, key, value, next);
    }
}

5、put方法

LinkedHashMap中没有重写put方法，功能性代码几乎完全继承了HashMap类，但是重写了newNode方法；

// 返回值类型，正是HashMap中的那个HashMap$Node；在HsahMap中，put方法调用newNode方法获取节点，现在被子类覆盖了
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;
}

// 把新节点跟末节点连接起来的具体实现
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    // 获取末节点
    LinkedHashMap.Entry<K,V> last = this.tail;
    // 先保存末节点
    this.tail = p;
    // 如果容器中没有最后一个节点，说明该容器刚初始化完不久
    if (last == null)
        // 让新节点作为头指针指向的节点，即新节点作为头节点
        this.head = p;
    // 如果集合有元素
    else {
        // 让新节点的before指向原末节点
        p.before = last;
        // 让新节点的pre指向上一个节点
        last.after = p;
    }
}

6、关于几个后置方法

afterNodeInsertion(putVal中被调用)、afterNodeAccess(putVal、get中被调用)、afterNodeRemoval(removeNode中被调用)分别是在节点进行增删查，即在putVal、get、removeNode方法中回调执行执行；这三个方法都是重写了父类HashMap中的，只不过在HashMap中，这几个方法都为空方法，这三个方法设计的目的，就是为了支持LinkedHashMap.

用于增加节点后回调的方法：

根据需要把头节点删除。

// 在节点新增后执行，具体调用查看HashMap的putVal方法
// 传入的evict如果是true，表示这个集合要始终保持创建模式
// 简单说，就是同意在每次放入元素后把this.head头节点指向的节点删除，即把最不常用的节点删除
void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K,V> first;
    // evict就是putVal方法的evict参数，removeEldestEntry方法有默认实现，返回false
    if (evict && (first = this.head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

// 这是默认实现，允许子类重写
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

用于删除节点后回调的方法：

就是在双向链表中，把被删除的节点去掉。

// 在节点删除之后调用，具体调用查看removeNode
// e为被删除的节点
void afterNodeRemoval(Node<K,V> e) { // unlink
    // p指向被删除的节点；b指向被删除节点的前一个节点；a指向被删除节点的后一个节点
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // 让被删除的节点的before属性和after属性都置为空
    p.before = p.after = null;
    // 如果b是空，说明被删除的是头节点
    if (b == null)
        // 让head指针指向下一个节点
        this.head = a;
    // 被删除节点不是头节点
    else
        // 让被删除节点的前驱节点的after指针指向被删除节点的下一个节点
        b.after = a;
    // 如果a是null，说明被删除节点是末节点
    if (a == null)
        // 让尾指针指向被删除节点的前驱节点
        this.tail = b;
    // 如果不是最后的节点
    else
        // 让被删除节点的下一个节点的before指针指向被删除节点的前一个节点
        a.before = b;
}

用于查询节点后回调的方法：

如果指定这个LinkedHashMap是按照访问进行排序的话，那么访问后的排序工作在这里完成，即将被访问的节点移动到链表的末尾。

void afterNodeAccess(Node<K,V> e) {
    // 用于指向被访问节点的before应该指向的节点
    LinkedHashMap.Entry<K,V> last;
    // 根据this.accessOrder属性，判断当前LinkedHashMap是按照什么来进行排序的
    // 如果是true的话，那么就按照访问来进行排序，即最近被访问的节点一律排在最后
    if (this.accessOrder && (last = this.tail) != e) {
        // p指向被访问的节点
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, 
        // b指向被访问节点的前一个节点
        b = p.before, 
        // a指向被访问节点的后一个节点
        a = p.after;
        // 让被访问节点的after属性指向null
        p.after = null;
        
        // 如果被访问的节点的前一个节点是null，说明被访问的是头节点
        if (b == null)
            // 让head指针指向被访问节点的下一个节点
            this.head = a;
        // 如果被访问节点不是头节点的话
        else
            // 就让被访问节点的前一个节点的after属性指向被访问节点的下一个节点
            b.after = a;
        
        // 如果被访问节点的下一个节点不是null，说明被访问节点不是末节点
        if (a != null)
            // 让被访问节点的后一个节点的before属性指向被访问节点的前一个节点
            a.before = b;
        // 如果是被访问的是末节点
        else
            // 让指向链表末节点的last变量指向原本的倒数第二个节点
            last = b;
        
        // 如果指向链表末节点的last变量是null,说明集合只有一个元素，并且被访问节点是头节点
        if (last == null)
            // 让head指针指向被访问的节点
            this.head = p;
        // 如果被访问的节点不是头节点
        else {
            // 让被访问节点的before属性指向last
            p.before = last;
            // 让last指向的节点的after属性指向被访问节点
            last.after = p;
        }
        // 让tail指针指向被访问节点
        this.tail = p;
        ++modCount;
    }
}