一、LinkedHashMap的属性

二、LinkedHashMap的构造方法

三、LinkedHashMap的重要函数

1. afterNodeAccess函数

2. afterNodeInsertion函数

3. afterNodeRemoval函数

4. transferLinks函数

5. linkNodeLast函数

6. 其他方法

四、LinkedHashMap的迭代器

1. 基础迭代器--LinkedHashIterator

2. 键迭代器--LinkedKeyIterator

3. 值迭代器--LinkedValueIterator

4. 结点迭代器--LinkedEntryIterator

LinkedHashMap<K,V>继承HashMap<K,V>类，实现了 Map<K,V>接口。

LinkedHashMap是HashMap的子类，与HashMap有着同样的存储结构，但它加入了一个双向链表的头结点，将所有put到LinkedHashmap的节点一一串成了一个双向循环链表，因此它保留了节点插入的顺序，可以使节点的输出顺序与输入顺序相同。

LinkedHashMap可以用来实现LRU算法（这会在下面的源码中进行分析）。

LinkedHashMap同样是非线程安全的，只在单线程环境下使用。

1. LinkedHashMap的属性

    /**
     * 静态内部类Entry表示双向链表，继承自HashMap的Node，在其基础上加上了before和after两个指针
     * 双向循环链表的头结点，整个LinkedHashMap中只有一个header
     * 它将哈希表中所有的Entry贯穿起来，header中不保存key-value对，只保存前后节点的引用  
     */
    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;
序列化
transient LinkedHashMap.Entry<K,V> head;
链表头结点
transient LinkedHashMap.Entry<K,V> tail;
链表尾结点
final boolean accessOrder;
双向链表中元素排序规则的标志位；
false：表示按插入顺序排序；true：表示按访问顺序排序

2. LinkedHashMap的构造方法

2.1 LinkedHashMap(int, float)型构造函数

    /**
     * 总是会在构造函数的第一行调用父类构造函数，使用super关键字，    
     * accessOrder默认为false，access为true表示之后访问顺序按照元素的访问顺序进行
     * 即不按照之前的插入顺序了，access为false表示按照插入顺序访问。
     */
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

2.2 LinkedHashMap(int)型构造函数

    /**
     * 加载因子取默认的0.75f
     */    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

2.3 LinkedHashMap()型构造函数

    /**
     * 加载因子取默认的0.75f，容量取默认的16 
     */
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

2.4 LinkedHashMap(Map<? extends K, ? extends V>)型构造函数

    /**
     * putMapEntries是调用到父类HashMap的构造函数
     */
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }

2.5 LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)型构造函数

    /**
     * 可以指定accessOrder的值，从而控制访问顺序
     */
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

3. LinkedHashMap的重要函数

afterNodeAccess、afterNodeInsertion、afterNodeRemoval这三个方法都是重写父类HashMap的方法。

3.1 afterNodeAccess函数

    /**
     * 把当前节点e放到双向链表尾部
     */
    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        /* accessOrder就是我们前面说的LRU控制，当它为true，同时e对象不是尾节点
        （如果访问尾节点就不需要设置，该方法就是把节点放置到尾节点）
        */
        if (accessOrder && (last = tail) != e) {
            // 用a和b分别记录该节点前面和后面的节点
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            // 释放当前节点与后节点的关系 
            p.after = null;
            // 如果当前节点的前节点是空
            if (b == null)
                // 那么头节点就设置为a
                head = a;
            else
                // 如果b不为null，那么b的后节点指向a
                b.after = a;
            // 如果a节点不为空
            if (a != null)
                // a的后节点指向b
                a.before = b;
            else
                // 如果a为空，那么b就是尾节点
                last = b;
            // 如果尾节点为空
            if (last == null)
                // 那么p为头节点
                head = p;
            else {
                // 否则就把p放到双向链表最尾处
                p.before = last;
                last.after = p;
            }
            // 设置尾节点为P  
            tail = p;
            // LinkedHashMap对象操作次数+1
            ++modCount;
        }
    }

此函数在很多函数（如put）中都会被回调，LinkedHashMap重写了HashMap中的此函数。若访问顺序为true，且访问的对象不是尾结点

访问结点3的前后状态

从图中可以看到，结点3链接到了尾结点后面
LinkedHashMap重写了HashMap的get方法：

    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)    // 如果启用了LRU规则
            afterNodeAccess(e);  // 那么把该节点移到双向链表最后面
        return e.value;
    }

注： LinkedHashMap压根没有重写put方法，每次用LinkedHashMap的put方法的时候，其实你调用的都是HashMap的put方法。但它也会执行afterNodeAccess()方法，因为这个方法HashMap就是存在的，但是没有实现，LinkedHashMap重写了afterNodeAccess()这个方法。

3.2 afterNodeInsertion函数

    /**
     * 在哈希表中插入了一个新节点时调用的，它会把链表的头节点删除掉，删除的方式是通过调用HashMap的removeNode方法
     */
    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);
        }
    }

3.3 afterNodeRemoval函数

    /**
     * 当HashMap删除一个键值对时调用的，它会把在HashMap中删除的那个键值对一并从链表中删除，保证了哈希表和链表的一致性。
     */
    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);
        }
    }

3.4 transferLinks函数

    /**
     * 用dst替换src
     */
    private void transferLinks(LinkedHashMap.Entry<K,V> src,
                               LinkedHashMap.Entry<K,V> dst) {
        LinkedHashMap.Entry<K,V> b = dst.before = src.before;
        LinkedHashMap.Entry<K,V> a = dst.after = src.after;
        if (b == null)
            head = dst;
        else
            b.after = dst;
        if (a == null)
            tail = dst;
        else
            a.before = dst;
    }

使用结点7替换结点3

3.5 linkNodeLast函数

在看linkNodeLast函数之前先看看newNode和newTreeNode这两个函数

3.5.1 newNode函数

    /**
     * 当桶中结点类型为HashMap.Node类型时，调用此函数
     */
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        // 生成Node结点    
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        // 将该结点插入双链表末尾
        linkNodeLast(p);
        return p;
    }

3.5.2 newTreeNode函数

    /**
     * 当桶中结点类型为HashMap.TreeNode时，调用此函数
     */
    TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
        // 生成TreeNode结点
        TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
        // 将该结点插入双链表末尾
        linkNodeLast(p);
        return p;
    }

3.5.3 linkNodeLast函数

    /**
     * 把新加的节点放在链表的最后面
     */
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        // 将tail给临时变量last
        LinkedHashMap.Entry<K,V> last = tail;
        // 把new的Entry给tail
        tail = p;
        // 若没有last，说明p是第一个节点，head=p
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

3.6 其他方法

internalWriteEntries方法

    /**
     * 该方法也是重写父类HashMap的方法，也是为了LinkedHashMap键和值被序列化的存储顺序
     */
    void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
            s.writeObject(e.key);
            s.writeObject(e.value);
        }
    }

其他方法就不一一介绍的官方API中都有详细的说明。

4. LinkedHashMap的迭代器

4.1基础迭代器--LinkedHashIterator

为抽象类，用于对LinkedHashMap进行迭代

    /**
     * LinkedHashIterator是LinkedHashMap的迭代器，为抽象类，用于对LinkedHashMap进行迭代
     */
    abstract class LinkedHashIterator {
        // 下一个结点
        LinkedHashMap.Entry<K,V> next;
        // 当前结点
        LinkedHashMap.Entry<K,V> current;
        // 期望的修改次数
        int expectedModCount;

        LinkedHashIterator() {
            // next赋值为头结点
            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;
        }
    }

4.2 键迭代器--LinkedKeyIterator

继承自LinkedHashIterator，实现了Iterator接口，对LinkedHashMap中的键进行迭代

    final class LinkedKeyIterator extends LinkedHashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().getKey(); }
    }

4.3 值迭代器--LinkedValueIterator

继承自LinkedHashIterator，实现了Iterator接口，对LinkedHashMap中的值进行迭代

    final class LinkedValueIterator extends LinkedHashIterator
        implements Iterator<V> {
        public final V next() { return nextNode().value; }
    }

4.4 结点迭代器--LinkedEntryIterator

继承自LinkedHashIterator，实现了Iterator接口，对LinkedHashMap中的结点进行迭代

    final class LinkedEntryIterator extends LinkedHashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }

JDK1.8源码阅读--LinkedHashMap