import java.util.*;
import java.util.function.Consumer;
 java.util.function.BiConsumer;
 java.util.function.BiFunction;
 java.io.IOException;


 * Map 接口的哈希表和链表实现，具有可预测的迭代顺序。此实现与 HashMap 的不同之处在于它维护了一个贯穿其所有条目的双向链表。
 * 此链接列表定义迭代排序，通常是键插入映射的顺序（插入顺序）。 请注意，如果将键重新插入到Map中，则插入顺序不会受到影响。
 * （如果在m.containsKey时调用 m.put（k，v），则将键k 重新插入到map m 中,会在调用之前立即返回true 。）
 *
 * 这种实现使客户免于{@link HashMap}（以及{ Hashtable}）提供的不确定的，通常是混乱的排序，并且不会导致类似{ TreeMap}相关的成本增加。
 * 无论原始Map的实现如何，它都可用于生成与原始Map具有相同顺序的Map副本：
 *
 *     void foo(Map m) {
 *         Map copy = new LinkedHashMap(m);
 *         ...
 *     }
 *
 * 如果模块在输入上获取map，复制它，然后返回其顺序由副本确定的结果，则此技术特别有用。 （客户通常会欣赏按照提交的顺序返回的内容。）
 *
 * 提供了一个特殊的{ #LinkedHashMap（int，float，boolean）构造函数}来创建一个链接的哈希映射，其迭代顺序是其条目最后一次访问的顺序，
 * 从最近最少访问到最近最多访问（按存取顺序）。这种地图非常适合构建LRU缓存。调用{@code put}，{ putIfAbsent}，{ get}，
 * { getOrDefault}，{ compute}，{ computeIfAbsent}，{ computeIfPresent}或{ merge}方法
 * 导致访问相应的条目（假设它在调用完成后存在）。 { replace}方法仅在替换值时才会访问该条目。 { putAll}方法为指定映射中的
 * 每个映射生成一个条目访问，按照指定映射的条目集迭代器提供键 - 值映射的顺序。没有其他方法可以生成条目访问。
 * 特别是，对集合视图的操作不会影响支持映射的迭代顺序。
 *
 * TODO LRU缓存
 *
 * 可以重写{ #removeEldestEntry（Map.Entry）}方法，以强制在将新映射添加到Map中时自动删除过时映射的策略。
 *
 * 此类提供所有可选的Map操作，并允许null元素。 与HashMap一样，假设哈希函数在桶之间正确地分散元素，它将为基本操作（添加，包含和删除）提供了恒定时间
 * 性能，由于维护链表的额外费用，性能可能略低于HashMap的性能，但有一个例外：
 * 无论其容量如何，对LinkedHashMap的集合视图进行迭代需要与映射大小成比例的时间。而对HashMap的迭代可能更昂贵，需要与其容量成比例的时间。
 *
 * 链接的哈希映射有两个影响其性能的参数：初始容量和加载因子。它们的定义与 HashMap 完全相同。
 * 但请注意，对于此类，选择过高的初始容量值的惩罚不如 HashMap ，因为此类的迭代次数不受容量影响。
 *
 * 请注意，此实现未同步。如果多个线程同时访问链接的哈希映射，并且至少有一个线程在结构上修改了映射，则<em>必须</ em>外部同步。
 * 这通常通过在自然封装地图的某个对象上进行同步来实现。如果不存在此类对象，
 * 则应使用{ Collections＃synchronizedMap Collections.synchronizedMap}方法“包装”映射。这最好在创建时完成，
 * 以防止意外地不同步访问地图：
 *  Map m = Collections.synchronizedMap（new LinkedHashMap（...））;
 *
 * 结构修改是指任何添加或删除一个或多个映射的操作，或者在访问顺序链接的哈希映射的情况下，影响迭代顺序。
 * 在插入有序链接散列映射中，仅更改与已包含在映射中的键相关联的值不是结构修改。在访问顺序链接哈希映射中，仅使用 get 查询地图是一种结构修改。
 *
 * 由该类的所有集合视图方法<tt> iterator </ tt>方法返回的迭代器是 “fail-fast” 的：
 * 如果map在创建迭代器之后的任何时候进行结构修改，（除了通过迭代器自己的<tt> remove </ tt>方法之外），
 * 迭代器将抛出{ ConcurrentModificationException}。因此，在并发修改的情况下，迭代器快速而干净地失败，
 * 而不是在未来的未确定时间冒任意，非确定性行为的风险。
 *
 * 请注意，迭代器的快速失败行为无法得到保证，因为一般来说，在存在非同步并发修改的情况下，不可能做出任何硬性保证。
 * 失败快速的迭代器会尽最大努力抛出<tt> ConcurrentModificationException </ tt>。因此，编写依赖于此异常的程序以确保其正确性是错误的：
 * 迭代器的故障快速行为应仅用于检测错误。
 *
 * 分裂器返回的分裂器所有此类的集合视图方法返回的集合的方法是后期绑定的，失败快速的和附加报告的{ Spliterator #OrderED}。
 *
 */
class LinkedHashMap<K,V>
        extends HashMap<K,1)">implements Map<K,1)"> {

    
     * 实现说明。 此类的先前版本的内部结构略有不同。 因为超类HashMap现在为其某些节点使用树节点，所以类Entry现在被视为中间节点类，
     * 也可以转换为树形式。 这个类的名称Entry在其当前上下文中以多种方式混淆，但无法更改。 否则，即使它未被导出到此包之外，
     * 已知一些现有的源代码依赖于对removeEldestEntry的调用中的符号解析角案例规则，该删除由于模糊使用而抑制了编译错误。
     * 因此，我们保留名称以保留未修改的可编译性。 节点类的更改还需要使用两个字段（头部，尾部）而不是指向标头节点的指针来维护列表之前/之后的双向链接。
     * 此类以前还在访问，插入和删除时使用了不同类型的回调方法。
     */

    
     * 普通 LinkedHashMap 条目的HashMap.Node子类.
     long serialVersionUID = 3801124242820219131L
     * 第一个条目
     transient Entry<K,1)"> head;

    
     * 最后一个条目
      tail;

    
     * 迭代顺序，true代表使用访问顺序进行迭代，false代表使用插入顺序进行迭代
      accessOrder;

     内部工具方法

     链接到链表尾部
    void linkNodeLast(Entry<K,1)"> p) {
        Entry<K,1)"> p;
        }
    }

     用dst条目代替src条目
    void transferLinks(Entry<K,1)"> src,Entry<K,1)"> dst) {
        Entry<K,V> b = dst.before = src.before;
        Entry<K,V> a = dst.after = src.after;
         dst;
         dst;
    }

     重载 HashMap 中的方法

     reinitialize() {
        .reinitialize();
        head = tail =  新建条目并链接到链表尾部
    Node<K,1)"> e) {
        Entry<K,V> p =
                new Entry<K,e);
        linkNodeLast(p);
         p;
    }

     代替节点
    Node<K,V> replacementNode(Node<K,V> p,1)"> next) {
        Entry<K,V> q = (Entry<K,1)">)p;
        Entry<K,V> t =
                (q.hash,q.key,q.value,next);
        transferLinks(q,t);
         t;
    }

    TreeNode<K,V> newTreeNode( next) {
        TreeNode<K,V> p = new TreeNode<K,next);
        linkNodeLast(p);
         p;
    }

    TreeNode<K,V> replacementTreeNode(Node<K,1)">)p;
        TreeNode<K,V> t =  t;
    }

     节点移除之后，将其从双链表中拆分出来
     unlink
        Entry<K,1)">
                (Entry<K,1)"> 节点插入之后判断是否需要将最早的元素进行删除
     possibly remove eldest
        Entry<K,1)"> 要同时满足三个条件才能在插入元素后对最早插入条目进行删除
         在节点被访问之后，判断是否需要将被访问过的节点移动到双链表的最末尾
     move node to last
        Entry<K,1)"> 当accessOrder成员变量为true并且该访问元素不是最后一个元素时，将其移动到双链表的末尾
         e) {
            Entry<K,1)">
                    (Entry<K,1)">modCount;
        }
    }

     重写hashmap的internalWriteEntries方法，进行输出流的写入
    void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
        for (Entry<K,1)"> e.after) {
            s.writeObject(e.key);
            s.writeObject(e.value);
        }
    }

     accessOrder;
    }


    
     * Returns <tt>true</tt> if this map maps one or more keys to the
     * specified value.
     *
     *  value value whose presence in this map is to be tested
     *  <tt>true</tt> if this map maps one or more keys to the
     *         specified value
      containsValue(Object value) {
         TODO 与hashmap的遍历方式进行比较
         LinkedHashMap中遍历元素时都是使用链表的方式进行遍历
         e.after) {
            V v = e.value;
            if (v == value || (value !=  value.equals(v)))
                
     * 获取指定key对应的value，不存在则返回null
     * 返回null时有两种可能，一种是该key没有对应的映射，另一种是该key对应的value是null，可以使用containsKey方法对这两种情况进行区分
      V get(Object key) {
        Node<K,1)"> e;
        if ((e = getNode(hash(key),key)) == )
            if (accessOrder)
            afterNodeAccess(e);
         e.value;
    }

    
     * 获取指定key对应的value，如果不存在则返回默认值
      V getOrDefault(Object key,V defaultValue) {
        Node<K,1)"> defaultValue;
        
     * 清除元素
      clear() {
        .clear();
        head = tail = 
     * 如果此map应删除其最旧的条目，则返回true 。在将新条目插入Map后，put 和 putAll 将调用此方法。
     * 它为实现者提供了在每次添加新条目时删除最旧条目的机会。如果映射表示高速缓存，则此选项非常有用：它允许映射通过删除过时条目来减少内存消耗。
     *
     * 示例：此覆盖实现将允许map增长到100个条目，
     * 然后在每次添加新条目时删除最旧的条目，保持100个条目的稳定状态。
     *
     * private static final int MAX_ENTRIES = 100;
     * protected boolean removeEldestEntry（Map.Entry eldest）{
     * return size（）; MAX_ENTRIES;
     * }
     *
     * 此方法通常不会以任何方式修改地图，而是允许地图按其返回值的指示修改自身。 此方法直接修改map是允许的，但如果它这样做，
     * 它必须返回false（表示map不应该尝试任何进一步的修改）。在此方法中修改地图后返回 true 的效果未指定。此实现仅返回 false
     * （因此此映射的行为类似于普通映射 - 永远不会删除最旧的元素）。
     *
     *  eldest map中最近插入的条目，或者如果这是访问顺序地图，则是最近访问的条目。这是将被删除的条目，此方法返回 true 。
     *               如果在 put 或 putAll 调用之前映射为空，从而导致此调用，则这将是刚刚插入的条目;换句话说，如果map包含单个条目，
     *               则最老的条目也是最新的。
     *
     *  true 表示应从map中删除最年长的条目;  false 表示应该保留。
      eldest) {
        
     * 返回包含该map所有key的{ Set}视图。 该集合由map支持，因此对map的更改将反映在集中，反之亦然。 如果在对集合进行迭代时修改了映射
     * （除了通过迭代器自己的remove 操作），迭代的结果是未定义的。 该集支持元素删除，它通过 Iterator.remove ，Set.remove ， removeAll
     * ，从地map中删除相应的映射。 retainAll 和 clear 操作。 它不支持 add 或 addAll 操作。 它的{ Spliterator}通常提供更快的顺序性能，
     * 但并行性能比{ HashMap}差得多。
     public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == ) {
            ks =  LinkedKeySet();
            keySet = ks;
        }
         ks;
    }

    void clear()               { 
                    Spliterator.ORDERED |
                    Spliterator.DISTINCT);
        }
         ConcurrentModificationException();
        }
    }


    public Collection<V> values() {
        Collection<V> vs = values;
        if (vs == ) {
            vs =  LinkedValues();
            values = vs;
        }
         vs;
    }

    
                    Spliterator.ORDERED);
        }
         ConcurrentModificationException();
        }
    }

    
     * 返回包含该map中所有映射的Set视图，该set由map支持，因此对map的更改将反映在set中，反之亦然。 如果在对集合进行迭代时修改了映射
     * （除非通过迭代器自己的 remove 操作，或者对迭代器返回的映射条目执行 setValue 操作） ）迭代的结果是未定义的。 该集支持元素删除，
     * 它通过 Iterator.remove  Set.remove ， removeAll ，从地图中删除相应的映射。 retainAll 和 clear 操作。 它不支持 add 或
     *  addAll 操作。 它的{ Spliterator}通常提供更快的顺序性能，但并行性能比{public Set<Map.Entry<K,1)"> entrySet() {
        Set<Map.Entry<K,1)"> es;
        return (es = entrySet) == null ? (entrySet =  LinkedEntrySet()) : es;
    }

     Map overrides

    void forEach(BiConsumer<? super K,1)"> action) {
         NullPointerException();
         modCount;
         e.after)
            action.accept(e.key,e.value);
         mc)
             ConcurrentModificationException();
    }

    void replaceAll(BiFunction<? super V,1)"> function) {
        if (function ==  e.after)
            e.value = function.apply(e.key,1)"> 迭代器

     LinkedHashIterator {
        Entry<K,1)"> next;
        Entry<K,1)">final Entry<K,1)"> nextNode() {
            Entry<K,1)"> modCount;
        }
    }

     LinkedHashIterator
             nextNode(); }
    }


}

　　至此，本篇就算完结啦，一周一篇的小目标也算是完成了，周末要去浪浪浪了，哈哈哈哈。

　　后续还会继续更新，欢迎继续关注！