介绍

LinkedHashMap继承自HashMap，同时内部用双向链表维护了元素的顺序，使得她的迭代是可以预测的。
类图如下：

数据结构

LinkedHashMap的内部结构如下：

 // 内部的节点，继承自HashMap的node，增加了before，after前后的指针用于实现链表。
 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);
        }
    }
    private static final long serialVersionUID = 3801124242820219131L;
    /**
     * The head (eldest) of the doubly linked list.
     */
    // 链表的头节点 / 最久访问的节点
    transient LinkedHashMap.Entry<K,V> head;
    /**
     * The tail (youngest) of the doubly linked list.
     */
    // 链表的尾节点 / 最近访问的节点
    transient LinkedHashMap.Entry<K,V> tail;
    /**
     * The iteration ordering method for this linked hash map: <tt>true</tt>
     * for access-order, <tt>false</tt> for insertion-order.
     *
     * @serial
     */
    // 迭代排序的方法，true代表按访问顺序，false代表按插入顺序
    final boolean accessOrder;

可以看出元素的顺序是有两种模式可供选择，一种是插入的顺序，即插入时是按什么顺序，迭代就是什么顺序，一种是元素访问的顺序，当访问一个元素时，这个元素会被放到链表的尾部，迭代的顺序就是从最久访问到最近访问的顺序。
为什么HashMap.Node有了next指针，LinkedHashMap.Entry还要增加after指针?

// HashMap的Node 定义
 static class Node<K,V> implements Map.Entry<K,V> {
     final int hash;
     final K key;
     V value;
     Node<K,V> next;
  }

注意这里HashMap的Node里面是有一个next指针，维护的是一个单向的链表，这个链表是解决Hash冲突时用的，所以是和before，after有区别的，LinkedHashMap的after指针是用来控制访问顺序的。

构造方法

    // 默认构造，accessOrder=false，按插入时顺序访问
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }
    // 指定初始容量，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;
    }

put方法

直接调用hashmap的put函数，不同的是最后一个参数evict为true，在put完之后会触发LinkedHashMap的钩子函数afterNodeInsertion

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    // 在putVal最后触发
    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        // evict为true，头节点不为null，并且removeEldestEntry返回true，就会移除头节点
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            // 移除头节点
            removeNode(hash(key), key, null, false, true);
        }
    }

这里涉及到一个removeEldestEntry函数，默认是直接返回false，也就是说这个判断是永远走不进去，默认是不会删除最久的元素。

    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

removeEldestEntry这个函数其实是扩展用，我们可以自定义一个子类，覆盖它的逻辑来实现一个类似LRU的算法，比如限定最多允许100个元素，超过100个就删除最老的元素。
代码如下：

    private static final int MAX_ENTRIES = 100;
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }

这样的话，put元素超过MAX_ENTRIES时就会移除头节点的元素，再加上accessOrder = true时，移除的就是最久没有被访问的元素，利用这个可以非常简单的实现LRU（最近最少访问）算法。

newNode方法

那么双向链表，before，after是在哪里维护的？
LinkedHashMap覆盖了HashMap的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 = tail;
        // 新增节点p变成尾节点
        tail = p;
        // 之前的尾节点是空，说明之前链表根本没有元素
        if (last == null)
            // p即是头节点也是尾节点
            head = p;
        else {
            // last不为空，将last和p进行连接，p的before是last，last的after是p
            p.before = last;
            last.after = p;
        }
    }

get方法

LinkedHashMap重写了HashMap的get方法，重写是为了添加访问顺序的逻辑，当accessOrder为true时，最后调用afterNodeAccess方法，当前访问的节点会移动到末尾。

    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;
    }
    // 在某个节点访问之后，移动该节点到末尾
    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        // e本身不是尾节点才进行移动
        if (accessOrder && (last = tail) != e) {
            // e赋值为p，b是p的before节点，a是p的after节点
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            // p要转移到尾节点，所以p的after是null
            p.after = null;
            // 如果没有before节点，说明p是头节点
            if (b == null)
                // 头节点是p的after节点
                head = a;
            else
                // p有before节点，b节点的after指向a，跳过p
                b.after = a;
            // 判断after节点不是null
            if (a != null)
                // after节点的before指向b，跳过p
                a.before = b;
            else
                // afte是null，last指向b，b有可能是null
                last = b;
            // last为null，那么p是头节点
            if (last == null)
                head = p;
            else {
                // last不为null，把p挂到last的后面
                p.before = last;
                last.after = p;
            }
            // p变成了尾节点
            tail = p;
            ++modCount;
        }
    }

remove方法

LinkedHashmap没有重写remove方法，直接调用了HashMap的remove，移除完成后最后会调用钩子函数afterNodeRemoval。

    // 移除节点后要维护e前后的before和after指针
     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;
        // e的before为null，head指向e的after
        if (b == null)
            head = a;
        else
             // e的before不为null，before的after指向e的after
            b.after = a;
        // e的after为null，说明e是尾节点，tail指向e的before，这样e就被移除了
        if (a == null)
            tail = b;
        else
            // e的after不为null，e的after节点的before指针指向e的before节点，跳过e
            a.before = b;
    }