/**

 * <p>Hash table and linked list implementation of the <tt>Map</tt> interface,

 * with predictable iteration order.  This implementation differs from

 * <tt>HashMap</tt> in that it maintains a doubly-linked list running through

 * all of its entries.  This linked list defines the iteration ordering,

 * which is normally the order in which keys were inserted into the map

 * (<i>insertion-order</i>).  Note that insertion order is not affected

 * if a key is <i>re-inserted</i> into the map.  (A key <tt>k</tt> is

 * reinserted into a map <tt>m</tt> if <tt>m.put(k, v)</tt> is invoked when

 * <tt>m.containsKey(k)</tt> would return <tt>true</tt> immediately prior to

 * the invocation.)

 *

 * <p>This implementation spares its clients from the unspecified, generally

 * chaotic ordering provided by {@link HashMap} (and {@link Hashtable}),

 * without incurring the increased cost associated with {@link TreeMap}.  It

 * can be used to produce a copy of a map that has the same order as the

 * original, regardless of the original map's implementation:

 * <pre>

 *     void foo(Map m) {

 *         Map copy = new LinkedHashMap(m);

 *         ...

 *     }

 * </pre>

 * This technique is particularly useful if a module takes a map on input,

 * copies it, and later returns results whose order is determined by that of

 * the copy.  (Clients generally appreciate having things returned in the same

 * order they were presented.)

 *

 * <p>A special {@link #LinkedHashMap(int,float,boolean) constructor} is

 * provided to create a linked hash map whose order of iteration is the order

 * in which its entries were last accessed, from least-recently accessed to

 * most-recently (<i>access-order</i>).  This kind of map is well-suited to

 * building LRU caches.  Invoking the {@code put}, {@code putIfAbsent},

 * {@code get}, {@code getOrDefault}, {@code compute}, {@code computeIfAbsent},

 * {@code computeIfPresent}, or {@code merge} methods results

 * in an access to the corresponding entry (assuming it exists after the

 * invocation completes). The {@code replace} methods only result in an access

 * of the entry if the value is replaced.  The {@code putAll} method generates one

 * entry access for each mapping in the specified map, in the order that

 * key-value mappings are provided by the specified map's entry set iterator.

 * <i>No other methods generate entry accesses.</i>  In particular, operations

 * on collection-views do <i>not</i> affect the order of iteration of the

 * backing map.

 *

 * <p>The {@link #removeEldestEntry(Map.Entry)} method may be overridden to

 * impose a policy for removing stale mappings automatically when new mappings

 * are added to the map.

 *

 * <p>This class provides all of the optional <tt>Map</tt> operations, and

 * permits null elements.  Like <tt>HashMap</tt>, it provides constant-time

 * performance for the basic operations (<tt>add</tt>, <tt>contains</tt> and

 * <tt>remove</tt>), assuming the hash function disperses elements

 * properly among the buckets.  Performance is likely to be just slightly

 * below that of <tt>HashMap</tt>, due to the added expense of maintaining the

 * linked list, with one exception: Iteration over the collection-views

 * of a <tt>LinkedHashMap</tt> requires time proportional to the <i>size</i>

 * of the map, regardless of its capacity.  Iteration over a <tt>HashMap</tt>

 * is likely to be more expensive, requiring time proportional to its

 * <i>capacity</i>.

 *

 * <p>A linked hash map has two parameters that affect its performance:

 * <i>initial capacity</i> and <i>load factor</i>.  They are defined precisely

 * as for <tt>HashMap</tt>.  Note, however, that the penalty for choosing an

 * excessively high value for initial capacity is less severe for this class

 * than for <tt>HashMap</tt>, as iteration times for this class are unaffected

 * by capacity.

 *

 * <p><strong>Note that this implementation is not synchronized.</strong>

 * If multiple threads access a linked hash map concurrently, and at least

 * one of the threads modifies the map structurally, it <em>must</em> be

 * synchronized externally.  This is typically accomplished by

 * synchronizing on some object that naturally encapsulates the map.

 *

 * If no such object exists, the map should be "wrapped" using the

 * {@link Collections#synchronizedMap Collections.synchronizedMap}

 * method.  This is best done at creation time, to prevent accidental

 * unsynchronized access to the map:<pre>

 *   Map m = Collections.synchronizedMap(new LinkedHashMap(...));</pre>

 *

 * A structural modification is any operation that adds or deletes one or more

 * mappings or, in the case of access-ordered linked hash maps, affects

 * iteration order.  In insertion-ordered linked hash maps, merely changing

 * the value associated with a key that is already contained in the map is not

 * a structural modification.  <strong>In access-ordered linked hash maps,

 * merely querying the map with <tt>get</tt> is a structural modification.

 * </strong>)

 *

 * <p>The iterators returned by the <tt>iterator</tt> method of the collections

 * returned by all of this class's collection view methods are

 * <em>fail-fast</em>: if the map is structurally modified at any time after

 * the iterator is created, in any way except through the iterator's own

 * <tt>remove</tt> method, the iterator will throw a {@link

 * ConcurrentModificationException}.  Thus, in the face of concurrent

 * modification, the iterator fails quickly and cleanly, rather than risking

 * arbitrary, non-deterministic behavior at an undetermined time in the future.

 *

 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed

 * as it is, generally speaking, impossible to make any hard guarantees in the

 * presence of unsynchronized concurrent modification.  Fail-fast iterators

 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.

 * Therefore, it would be wrong to write a program that depended on this

 * exception for its correctness:   <i>the fail-fast behavior of iterators

 * should be used only to detect bugs.</i>

 *

 * <p>The spliterators returned by the spliterator method of the collections

 * returned by all of this class's collection view methods are

 * <em><a href="Spliterator.html#binding">late-binding</a></em>,

 * <em>fail-fast</em>, and additionally report {@link Spliterator#ORDERED}.

 *

 * <p>This class is a member of the

 * <a href="{@docRoot}/../technotes/guides/collections/index.html">

 * Java Collections Framework</a>.

 *

 * @implNote

 * The spliterators returned by the spliterator method of the collections

 * returned by all of this class's collection view methods are created from

 * the iterators of the corresponding collections.

 *

 * @param <K> the type of keys maintained by this map

 * @param <V> the type of mapped values

 *

 * @author  Josh Bloch

 * @see     Object#hashCode()

 * @see     Collection

 * @see     Map

 * @see     HashMap

 * @see     TreeMap

 * @see     Hashtable

 * @since   1.4

 */

    /**

     * HashMap.Node subclass for normal LinkedHashMap entries.

     * LinkedHashMap 的内部节点实现类，这里增加了 before 和 after 节点，用于维护 doubly-linked list

     * 这里继承了 HashMap.Node ，保证新节点的类型一致，都是 HashMap.Node

     */

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

        }

    }

    /**

     * 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.

     * 迭代器的顺序控制

     * true:根据访问顺序

     * false:默认场景，根据插入顺序

     * @serial

     */

    final boolean accessOrder;

    /**

     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance

     * with the specified initial capacity and load factor.

     *

     * 指定 初始容量 和 负载因子 ，同时默认为 插入顺序

     * @param  initialCapacity the initial capacity

     * @param  loadFactor      the load factor

     * @throws IllegalArgumentException if the initial capacity is negative

     *         or the load factor is nonpositive

     */

    public LinkedHashMap(int initialCapacity, float loadFactor) {

        super(initialCapacity, loadFactor);

        accessOrder = false;

    }

    /**

     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance

     * with the specified initial capacity and a default load factor (0.75).

     *

     * 指定 初始容量 ，默认负载因子 0.75，同时默认为 插入顺序

     * @param  initialCapacity the initial capacity

     * @throws IllegalArgumentException if the initial capacity is negative

     */

    public LinkedHashMap(int initialCapacity) {

        super(initialCapacity);

        accessOrder = false;

    }

    /**

     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance

     * with the default initial capacity (16) and load factor (0.75).

     *

     * 空构造函数，默认初始容量 16，默认负载因子 0.75，同时默认为 插入顺序

     */

    public LinkedHashMap() {

        super();

        accessOrder = false;

    }

    /**

     * Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with

     * the same mappings as the specified map.  The <tt>LinkedHashMap</tt>

     * instance is created with a default load factor (0.75) and an initial

     * capacity sufficient to hold the mappings in the specified map.

     *

     * 通过指定 Map 构造默认为 插入顺序 的 LinkedHashMap

     * @param  m the map whose mappings are to be placed in this map

     * @throws NullPointerException if the specified map is null

     */

    public LinkedHashMap(Map<? extends K, ? extends V> m) {

        super();

        accessOrder = false;

        putMapEntries(m, false);

    }

    /**

     * Constructs an empty <tt>LinkedHashMap</tt> instance with the

     * specified initial capacity, load factor and ordering mode.

     *

     * 指定 初始容量、负载因子、排序模式

     * @param  initialCapacity the initial capacity

     * @param  loadFactor      the load factor

     * @param  accessOrder     the ordering mode - <tt>true</tt> for

     *         access-order, <tt>false</tt> for insertion-order

     * @throws IllegalArgumentException if the initial capacity is negative

     *         or the load factor is nonpositive

     */

    public LinkedHashMap(int initialCapacity,

                         float loadFactor,

                         boolean accessOrder) {

        super(initialCapacity, loadFactor);

        this.accessOrder = accessOrder;

    }

// 创建新节点 并将 新节点 链接 到最后

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;

}

// link at the end of list

// 将 新节点 链接 到最后

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {

    LinkedHashMap.Entry<K,V> last = tail;

    tail = p;

    if (last == null)

        head = p;

    else {

        p.before = last;

        last.after = p;

    }

}

// Callbacks to allow LinkedHashMap post-actions

void afterNodeAccess(Node<K,V> p) { }            // 访问节点后需要进行的操作，如果指定了根据访问顺序控制，则在这里将节点挪到最后

void afterNodeInsertion(boolean evict) { }       // 插入节点后需要进行的操作，比如 LRU cache 中移除最早的节点

void afterNodeRemoval(Node<K,V> p) { }           // 移除指定节点

// 移除 e 节点元素后的操作，对于 HashMap ，removeNode 函数已经是移除了节点，这里是 LinkedHashMap 处理节点中和双向链表有关的的 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;

    // 移除 e 节点本身的链接

    p.before = p.after = null;

    if (b == null)        // 重置 e 节点上一个节点的 after 链接

        head = a;

    else

        b.after = a;

    if (a == null)        // 重置 e 节点下一个节点的 before 链接

        tail = b;

    else

        a.before = b;

}

// 是否移除最早插入/访问的节点元素

void afterNodeInsertion(boolean evict) { // possibly remove eldest

    LinkedHashMap.Entry<K,V> first;

    // 最简单的 LRU cache 其实就是重写 removeEldestEntry 什么时候返回 true 的逻辑（比如超过容量限制），然后移除最早插入/访问的节点

    if (evict && (first = head) != null && removeEldestEntry(first)) {

        K key = first.key;

        removeNode(hash(key), key, null, false, true);

    }

}

// 节点访问后是否将节点挪到最后

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)        // 重置 e 节点上一个节点的 after 链接

            head = a;

        else

            b.after = a;

        if (a != null)        // 重置 e 节点下一个节点的 before 链接

            a.before = b;

        else

            last = b;

        if (last == null)        // 只有一个 e 节点的场景

            head = p;

        else {

            p.before = last;    // 把 e 节点挪到最后

            last.after = p;

        }

        tail = p;            // 尾节点处理

        ++modCount;

    }

}

/**

 * Returns <tt>true</tt> if this map should remove its eldest entry.

 * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after

 * inserting a new entry into the map.  It provides the implementor

 * with the opportunity to remove the eldest entry each time a new one

 * is added.  This is useful if the map represents a cache: it allows

 * the map to reduce memory consumption by deleting stale entries.

 *

 * <p>Sample use: this override will allow the map to grow up to 100

 * entries and then delete the eldest entry each time a new entry is

 * added, maintaining a steady state of 100 entries.

 * <pre>

 *     private static final int MAX_ENTRIES = 100;

 *

 *     protected boolean removeEldestEntry(Map.Entry eldest) {

 *        return size() &gt; MAX_ENTRIES;

 *     }

 * </pre>

 *

 * <p>This method typically does not modify the map in any way,

 * instead allowing the map to modify itself as directed by its

 * return value.  It <i>is</i> permitted for this method to modify

 * the map directly, but if it does so, it <i>must</i> return

 * <tt>false</tt> (indicating that the map should not attempt any

 * further modification).  The effects of returning <tt>true</tt>

 * after modifying the map from within this method are unspecified.

 *

 * <p>This implementation merely returns <tt>false</tt> (so that this

 * map acts like a normal map - the eldest element is never removed).

 *

 * @param    eldest The least recently inserted entry in the map, or if

 *           this is an access-ordered map, the least recently accessed

 *           entry.  This is the entry that will be removed it this

 *           method returns <tt>true</tt>.  If the map was empty prior

 *           to the <tt>put</tt> or <tt>putAll</tt> invocation resulting

 *           in this invocation, this will be the entry that was just

 *           inserted; in other words, if the map contains a single

 *           entry, the eldest entry is also the newest.

 * @return   <tt>true</tt> if the eldest entry should be removed

 *           from the map; <tt>false</tt> if it should be retained.

 */

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {

    return false;

}

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {...}

    /**

     * Returns the value to which the specified key is mapped,

     * or {@code null} if this map contains no mapping for the key.

     *

     * <p>More formally, if this map contains a mapping from a key

     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :

     * key.equals(k))}, then this method returns {@code v}; otherwise

     * it returns {@code null}.  (There can be at most one such mapping.)

     *

     * <p>A return value of {@code null} does not <i>necessarily</i>

     * indicate that the map contains no mapping for the key; it's also

     * possible that the map explicitly maps the key to {@code null}.

     * The {@link #containsKey containsKey} operation may be used to

     * distinguish these two cases.

     */

    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;

    }