靠别人不如靠自己（2）——LinkedHashMap源码总结

1. LinkedHashMap

1.1. 概述

HashMap类的定义如下：

//HashMap的子类
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

特点

• 继承了HashMap所有的特点
• 节点有序
• LinkedHashMap是在HashMap的基础上多维护了一套双向链表结构

1.2. 属性 & 构造方法

// 双向链表的头部（最年长的）
transient LinkedHashMap.Entry<K,V> head;
// 双向链表的头部（最年轻的）
transient LinkedHashMap.Entry<K,V> tail;
// true：访问顺序(put和get都算访问)，false：插入顺序
final boolean accessOrder;

// 其他的构造函数与hashMap一致，accessOrder默认false
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

1.3. HashMap中回调方法的实现

看了源码后发现，LinkedHashMap继承了HashMap，主要方法都是HashMap中的方法，只是实现了一些回调方法，如afterNodeRemoval、afterNodeInsertion、afterNodeAccess等方法。

1.3.1. afterNodeRemoval & afterNodeInsertion & afterNodeAccess

void afterNodeRemoval(Node<K,V> e) { // 从链表中删去节点
    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;
}
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);
    }
}
// 如果此映射应删除其最旧的条目，则返回true 
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}
void afterNodeAccess(Node<K,V> e) { // 将访问的节点移到链表尾部，会增加modcount
    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;
    }
}

• afterNodeRemoval方法是在remove方法后调用，是将节点从双向链表中删除
• afterNodeInsertion方法是在put后调用，这里调用removeEldestEntry回调方法，由子类判断是否需要删除旧节点，默认不删除，可用于实现LRU
• afterNodeAccess方法在get和put后调用，当accessOrder设置为true时调用，同时modcount加1

1.3.2. newNode & replacementNode& newTreeNode & replacementTreeNode

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;
}
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
    LinkedHashMap.Entry<K,V> t =
        new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
    transferLinks(q, t); //将q的链接指针应用到 t
    return t;
}
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;
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
    TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
    transferLinks(q, t);
    return t;
}

• 新建一个新的节点时，链接到双向链表尾部，所以双向链表的默认的顺序时插入顺序。
• 在看HashMap源码时对Entry的继承关系产生过疑惑，继承顺序是TreeNode -> LinkedHashMap.Entry ->Node，为什么TreeNode不在中间？如果TreeNode在中间的话，那么在LinkedHashMap每个Entry都将同时是TreeNode

1.3.3.

abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next;
    LinkedHashMap.Entry<K,V> current;
    int expectedModCount;
    LinkedHashIterator() {
        next = head;
        expectedModCount = modCount;
        current = null;
    }
    public final boolean hasNext() {
        return next != null;
    }
    final LinkedHashMap.Entry<K,V> nextNode() {
        LinkedHashMap.Entry<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        current = e;
        next = e.after;
        return e;
    }
    public final void remove() {
        Node<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null;
        K key = p.key;
        removeNode(hash(key), key, null, false, false);
        expectedModCount = modCount;
    }
}

与HashMap相比，HashMap对单链表遍历，LinkedHashMap对双向链表进行遍历