LinkedHashMap

HashMap和双向链表合二为一即是LinkedHashMap。所谓LinkedHashMap，其落脚点在HashMap，同HashMap不同的是，LinkedHashMap维护了一个Entry的双向链表，保证了插入的Entry中的顺序，这也是Linked的含义。

LinkedHashMap有序，可分为插入顺序和访问顺序两种。如果是访问顺序，那put和get操作已存在的Entry时，都会把Entry移动到双向链表的表尾(其实是先删除再插入)

为了实现双向链表，LinkedHashMap中提供了如下的Entry：

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

主要元素

  /**
     * 头指针，指向第一个node
     */
    transient LinkedHashMap.Entry<K,V> head;
    /**
     * 尾指针，指向最后一个node
     */
    transient LinkedHashMap.Entry<K,V> tail;
    /**
     * 一个条件变量，它控制了是否在get操作后需要将新的get的节点重新放到链表的尾部
     * LinkedHashMap可以维持了插入的顺序，但是这个顺序不是不变的，可以被get操作打乱。
     *
     * @serial
     */
    final boolean accessOrder;

构造函数如果不明确传入accessOrder的话，默认都是按插入序的。

HashMap声明的三个方法

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

声明了三个方法供LinkedHashMap实现，afterNodeRemoval，afterNodeInsertion，afterNodeAccess。这三个方法的主要作用是，在删除，插入，获取节点之后，对链表进行维护。简单来说，这三个方法中执行双向链表的操作：

afterNodeRemoval

顾名思义，在节点remove操作后进行调用：

    //在节点删除后，维护链表，传入删除的节点
    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;
        //这里执行双向链表删除p节点操作，很简单。
        p.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

afterNodeAccess

  //在节点被访问后根据accessOrder判断是否需要调整链表顺序
    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        //如果accessOrder为false，什么都不做
        if (accessOrder && (last = tail) != e) {
            //p指向待删除元素，b执行前驱，a执行后驱
            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;
            //这里执行将p放到尾部
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            //保证并发读安全。
            ++modCount;
        }
    }

afterNodeInsertion

这是一个很奇葩的方法，虽然名字是在插入之后进行的维护链表的操作，但是默认实际上这个什么都没做，看代码：

    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        //removeEldestEntry(first)默认返回false，所以afterNodeInsertion这个方法其实并不会执行
        if (evict && (first = 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;
    }

为什么不执行也可以呢，这个要到put操作的时候就能看出来了

那么removeEldestEntry这个方法有什么用呢，看名字可以知道是删除最久远的节点，也就是head节点，这个方法实际是给我们自己扩展的。默认是没有用的，用LinkedHashMap实现LRU的代码中将可以看到它的作用

怎么记录的插入节点？

HashMap put 方法里会有创建Node的过程，LinkedHashMap复写了相关方法，实现了记录，然后添加到链表末位

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

get(Object key)

LinkedHashMap 重写了 get 方法，根据 accessOrder 实现访问记录

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