LinkedHashMap的整体架构

LinkedHashMap 本身继承 HashMap，所以它拥有 HashMap 的所有特性，再此基础上，还提供了两大特性：

• 按照插入 / 访问顺序进行访问
• 实现了访问最少最先删除功能，其目的是：把很久都没有访问的 key 自动删除

LinkedHashMap 通过新增头节点、尾节点，给每个节点增加 before、after 属性，
每次 put() 新增时，都把节点追加到链表的尾部等手段，在新增时，就已经维护了按照插入顺序的链表结构了。
若属性 accessOrder == true ，则每次 get() 查找时，都会把查找到的节点移动到链表尾部，从而维护了按照访问顺序的链表结构。
LinkedHashMap 的数据结构很像是把 LinkedList 的每个元素换成了 HashMap 的 Node，像是两者的结合体，也正是因为增加了这些结构，从而能把 Map 的元素都串联起来，形成一个链表，而链表就可以保证顺序了。

public class LinkedHashMap<K,V> extends HashMap<K,V>
    implements Map<K,V> {
    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;
    // 此 LinkedHashMap 的迭代排序方法
    // 值为 true 表示按照访问排序，false 表示按照插入顺序
    // 值默认 false
    final boolean accessOrder;
    // 构造一个空的按照插入顺序迭代的 LinkedHashMap 实例，具有指定的初始容量和负载因子
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }
    // 构造一个空的按照插入顺序迭代的 LinkedHashMap 实例，具有指定的初始容量和默认负载因子(0.75)
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }
    // 构造一个空的按照插入顺序迭代的 LinkedHashMap 实例，具有默认的初始容量(16)和负载因子(0.75)
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }
    // 构造一个按照插入顺序的 LinkedHashMap 实例，实例具有与指定 map 相同的映射 
    // 实例使用默认的负载因子(0.75)和足够容纳指定 map 中的映射的初始容量  
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }
    // 构造一个空的 LinkedHashMap 实例，该实例具有指定的初始容量、负载因子和排序模式  
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
}

LinkedHashMap按照插入顺序（新增）

LinkedHashMap 只提供了单向访问，不能像LinkedList 那样双向访问。主要通过迭代器进行访问。
LinkedHashMap 初始化时，属性 accessOrder 默认为 false，就是会按照插入顺序提供访问。
LinkedHashMap 本身是没有 put() 实现的，调用的是父类 HashMap 的 put()，但 LinkedHashMap 重写了 putVal() 中的调用 newNode()、newTreeNode()、afterNodeAccess()、afterNodeInsertion() 方法

• newNode() / newTreeNode() 增加逻辑：新增节点追加到链表尾部，保证可以按照插入顺序访问
• afterNodeAccess()：如果属性 accessOrder == true ，此方法将当前节点移动到链表尾部
• afterNodeInsertion()：如果属性 accessOrder == true ，此方法可能会删除头节点（满足一定条件）
  • 只有当 evict == true && 头节点不为 null && 重写的 removeEldestEntry() 返回 true 都满足时，才会删除头节点

HashMap 的笔记引用如下：
HashMap

LinkedHashMap 中重写的 newNode() 底层源码实现如下：

// LinkedHashMap 中重写的 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;
}
// HashMap 中的 newNode()
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}
// 将节点追加到链表的尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    // 暂存旧的尾节点
    LinkedHashMap.Entry<K,V> last = tail;
    // 新增节点作为新的尾节点
    tail = p;
    // 旧的尾节点为 null，说明链表之前为空
    if (last == null)
        // 新增第一个节点后，首尾节点都指向第一个节点
        head = p;
    // 链表之前有数据，则直接建立新增节点和旧的尾节点的前后关系
    else {
        p.before = last;
        last.after = p;
    }
}

LinkedHashMap 中重写的 newTreeNode() 底层源码实现如下：

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);
    // 该方法在上面 newNode() 笔记中已说明
    linkNodeLast(p);
    return p;
}
// HashMap 中的 newTreeNode()
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
    return new TreeNode<>(hash, key, value, next);
}

LinkedHashMap 中重写的 afterNodeAccess() 底层源码实现如下：

// 把节点移动到链表尾部
void afterNodeAccess(Node<K,V> e) { // move node to last
    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;
    }
}

LinkedHashMap 中重写的 afterNodeInsertion() 底层源码实现如下：

// 可能会删除头节点
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // removeEldestEntry 来控制删除策略，如果链表不为空，并且删除策略允许删除的情况下，删除
    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;
}

LinkedHashMap按照访问顺序（查询）

public V get(Object key) {
    Node<K,V> e;
    // 调用父类 HashMap 中的 getNode()
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 如果设置了 LRU 策略
    if (accessOrder)
        // 把查询到的节点移动到链表尾部（底层源码见上面新增部分）
        afterNodeAccess(e);
    return e.value;
}

通过 afterNodeAccess() 把当前访问节点移动到链表尾部，不仅是 get() 方法，执行 getOrDefault()、compute()、computeIfAbsent()、computeIfPresent()、merge() 方法时，也会这么做，通过不断的把经常访问的节点移动到链表尾部，那么靠近链表头部的节点，自然就是很少被访问的元素了。

LinkedHashMap的访问最少删除策略

访问最少删除策略也叫做 LRU（Least recently used，最近最少使用）
访问最少删除策略大概的意思就是：经常访问的元素会被追加到队尾，这样不经常访问的数据自然就靠近队头，然后可以通过设置删除策略，比如当 Map 元素个数大于多少时，把头节点删除。
以下 demo 用于演示 LinkedHashMap 的删除策略：

@Test
public void test19() {
    LinkedHashMap<Integer, Integer> linkedHashMap
        = new LinkedHashMap<Integer, Integer>(4, 0.75f, true) {
        {
            put(10, 10);
            put(9, 9);
            put(20, 20);
            put(1, 1);
        }
        // 重写删除策略的方法，我们设定当节点个数大于 3 时，就开始删除头节点
        // 父类中直接返回 false，如果返回 false 代表
        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() >= 4;
        }
    };
    // 打印结果：{9=9, 20=20, 1=1}
    System.out.println(linkedHashMap);
    Integer integer = linkedHashMap.get(9);
    // 打印结果：{20=20, 1=1, 9=9}
    System.out.println(linkedHashMap);
}

可以看到，map 初始化的时候，放进去四个元素，但结果只有三个元素，10 不见了，当 put(1, 1) 执行的时候，正好把队头的 10 删除，这个体现了达到我们设定的删除策略时，会自动的删除头节点。
当我们调用 map.get(9) 方法时，元素 9 移动到队尾，这个体现了经常被访问的节点会被移动到队尾。

LinkedHashMap的迭代器

HashMap 的笔记引用如下：
HashMap

LinkedHashMap 的迭代器源码实现如下：

abstract class LinkedHashIterator {
    // 下一个要返回的节点
    LinkedHashMap.Entry<K,V> next;
    // 当前节点，用于 remove() 
    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;
        // 通过链表的 after 结构，找到下一个迭代的节点
        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;
    }
}
final class LinkedKeyIterator extends LinkedHashIterator
    implements Iterator<K> {
    public final K next() { return nextNode().getKey(); }
}
final class LinkedValueIterator extends LinkedHashIterator
    implements Iterator<V> {
    public final V next() { return nextNode().value; }
}
final class LinkedEntryIterator extends LinkedHashIterator
    implements Iterator<Map.Entry<K,V>> {
    public final Map.Entry<K,V> next() { return nextNode(); }
}

LinkedHashMap的常见问题

说一下你对 LinkedHashMap 的了解

LinkedHashMap 继承了 HashMap，因此它拥有 HashMap 的所有特性。
LinkedHashMap 相较于 HashMap 多了成员属性 head、tail、accessOrder，LinkedHashMap 的节点相较于 HashMap 的节点多了 before、after，因此 LinkedHashMap拥有一些特性：

• 按照插入 / 访问顺序进行访问
• 实现了访问最少最先删除功能，其目的是：把很久都没有访问的 key 自动删除