Java编程拾遗『LinkedHashMap』_linkedhashmap(16, 0.75f, true)

1. 调用示例

public static void main(String[] args) {
    /*默认构造函数，按照插入顺序有序*/
    System.out.println("按插入顺序有序：");
    Map<Integer, String> linkedHashMap = new LinkedHashMap<>();
    linkedHashMap.put(1, "a");
    linkedHashMap.put(2, "b");
    linkedHashMap.put(3, "c");
    linkedHashMap.put(4, "d");
    /*按插入顺序有序时，put修改操作，并不会改变顺序*/
    linkedHashMap.put(3, "e");
    Iterator iterator = linkedHashMap.entrySet().iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    * public LinkedHashMap(int initialCapacity,
                           float loadFactor,
                           boolean accessOrder)
      构造函数，指定accessOrder为true时，可以按照访问顺序有序
    System.out.println("按访问顺序有序：");
    linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);
    linkedHashMap.put(1, "a");
    linkedHashMap.put(2, "b");
    linkedHashMap.put(3, "c");
    linkedHashMap.put(4, "d");
    /*1 -> 2 -> 3 -> 4*/
    linkedHashMap.get(2);//2被访问了，移动到内部双向链表末尾
    /*1 -> 3 -> 4 -> 2*/
    linkedHashMap.get(4);//4被访问了，移动到内部双向链表末尾
    /*1 -> 3 -> 2 -> 4*/
    linkedHashMap.put(1, "e");//1被访问(put)了，移动到内部双向链表末尾
    /*3 -> 2 -> 4 -> 1*/
    linkedHashMap.put(5, "f");//插入5
    /*3 -> 2 -> 4 -> 1 -> 5*/
    iterator = linkedHashMap.entrySet().iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
运行结果： 
按插入顺序有序：
按访问顺序有序：
1.1 按插入有序使用场景 
LinkedHashMap经常用来处理一些数据，接受一些键值对作为输入，处理，然后输出，输出时希望跟插入的顺序保持一致。比如从数据库查询数据放到内存时，已经使用SQL的order by语句让数据库对数据排序，在数据输入有序的前提下，希望通过Map存储查询结果，并且保持顺序输出，这时候就没必要使用TreeMap了，效率比LinkedHashMap低(TreeMap直接使用红黑树存储，LinkedHashMap使用Hash表)，直接使用LinkedHashMap也能达到相同的排序目标。 
1.2 按访问有序使用场景 
上面的例子，已经讲了按访问有序的示例。那么按访问有序在开发中有什么使用场景？最常见的一个用法就是通过LinkedHashMap的按访问有序实现LRU(Least Recently Used—最近最久未使用)算法。 
 缓存，原始意义是指访问速度比一般随机存取存储器（RAM）快的一种RAM，通常它不像系统主存那样使用DRAM技术，而使用昂贵但较快速的SRAM技术。当CPU处理数据时，它会先到缓存中去寻找，如果数据因之前的操作已经读取而被暂存其中，就不需要再从随机存取存储器（Main memory）中读取数据——由于CPU的运行速度一般比主内存的读取速度快，主存储器周期（访问主存储器所需要的时间）为数个时钟周期。因此若要访问主内存的话，就必须等待数个CPU周期从而造成浪费。 
 CPU的缓存曾经是用在超级计算机上的一种高级技术，不过现今计算机上使用的的AMD或Intel微处理器都在芯片内部集成了大小不等的数据缓存和指令缓存，通称为L1缓存；而比L1更大容量的L2缓存曾经被放在CPU外部（主板或者CPU接口卡上），但是现在已经成为CPU内部的标准组件；更昂贵的CPU会配备比L2缓存还要大的L3缓存（level 3 On-die Cache第三级高速缓冲存储器）。L1容量缓存非常小、价格非常贵、读取速度快，三级缓存容量会大一些、便宜一些、读取速度也慢一些。 
 如今缓存的概念已被扩充，不仅在CPU和主内存之间有Cache，而且在内存和硬盘之间也有Cache（磁盘缓存），乃至在硬盘与网络之间也有某种意义上的Cache──称为Internet临时文件夹或网络内容缓存等。凡是位于速度相差较大的两种硬件之间，用于协调两者数据传输速度差异的结构，均可称之为Cache。 
主存容量远大于CPU缓存，磁盘容量远大于主存，因此无论是哪一层次的缓存都面临一个同样的问题：当容量有限的缓存的空闲空间全部用完后，又有新的内容需要添加进缓存时，如何挑选并舍弃原有的部分内容，从而腾出空间放入这些新的内容。解决这个问题的算法有几种，如最久未使用算法（LFU）、先进先出算法（FIFO）、最近最少使用算法（LRU）、非最近使用算法（NMRU）等，这些算法在不同层次的缓存上执行时拥有不同的效率和代价，需根据具体场合选择最合适的一种。而本文讲的LinkedHashMap的按访问有序，就可以很容易的实现LRU算法。 
LinkedHashMap中存在一个protected方法，如下： 
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
这个方法用于插入键值对后调用，如果返回true，则会清除LinkedHashMap中“最老”(最久未访问)的键值对，LinkedHashMap的实现总是返回false，所以无论何时插入键值对，都不会对之前的键值对进行清除。所以如果要实现实现LRU算法，只要继承LinkedHashMap类，并按照具体策略重写此方法即可，如下： 
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int maxSize;
    public LRUCache(int maxSize){
        super(16, 0.75f, true);
        this.maxSize = maxSize;
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    public static void main(String[] args) {
        LRUCache<Integer, String> lruCache = new LRUCache<>(3);
        lruCache.put(1, "a");
        lruCache.put(2, "b");
        lruCache.put(3, "c");
        //访问1->a
        //key顺序为：2 -> 3 -> 1
        System.out.println(lruCache.get(1));
        //插入一个新键值对，理论上，由于超过LruCache的maxSize了，所以会删除最老的键值对
        //插入后，删除最老键值对前，key顺序：2 -> 3 -> 1 -> 4
        //所以最老的键值对，key为2
        lruCache.put(4, "d");
        System.out.println(lruCache);
运行结果： 
{3=c, 1=a, 4=d} 
限定缓存容量为3，先后添加了4个键值对，最久没被访问的key是”2″，会被删除。 
2. 方法说明 
LinkedHashMap的设计很巧妙，使用了钩子方法的设计模式，在HashMap中定义了钩子方法，然后再LinkedHashMap中实现，在钩子方法中保证键值对之间的顺序。 
2.1 构造函数 
S.N. 方法 说明
1 public LinkedHashMap() 默认构造函数，调用HashMap默认构造函数，元素保持按插入有序
2 public LinkedHashMap(int initialCapacity) 指定初始化时HashMap的容量，元素保持按插入有序
3 public LinkedHashMap(int initialCapacity, float loadFactor) 指定初始化时HashMap的容量和负载因子，元素保持按插入有序
4 public LinkedHashMap(Map<? extends K, ? extends V> m) 通过Map构建LinkedHashMap，，元素保持按插入有序
5 public LinkedHashMap(int initialCapacity,
 float loadFactor,
 boolean accessOrder) 指定初始化时HashMap的容量和负载因子，以及迭代输出节点的顺序，accessOrder为true时，
 元素间保持按访问有序 
2.2 Map接口 
除了构造函数之外的方法，全部继承自HashMap，但是针对个别方法，进行了重写。 
S.N. 方法 说明
1 void clear() 清除Map中所有的KV映射
2 default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) Java 8新方法，如果key在Map中不存在，则根据Function规则计算key对应的value值，
 并进行put操作(前提计算得到的value值也不为null)
3 default V computeIfPresent(K key,
 BiFunction<? super K, ? super V, ? extends V> remappingFunction) Java 8新方法，如果key在Map中存在，则根据BiFunction规则通过key和对应的value
 计算newValue，如果newValue为null，则删除key对应的键值对，否则替换key对应的value值
4 default V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) Java 8新方法，相当于上述两个方法的综合，根据BiFunction，通过key和对应的value
 计算newValue，如果newValue为null，会删除对应KV映射，否则会插入或替换原KV映射
5 boolean containsKey(Object key) 判断Map中是否存在key键
6 boolean containsValue(Object value) 判断Map中是否存在value值
7 Set<Map.Entry<K, V>> entrySet() 将Map所有的键值对转换为Set集合
8 boolean equals(Object o) equals方法
9 default void forEach(BiConsumer<? super K, ? super V> action) Java 8新方法，遍历Map，通过BiConsumer处理Map中每一个键值对的key、value
10 V get(Object key) 获取Map中key对应的value
11 default V getOrDefault(Object key, V defaultValue) Java 8新方法，获取Map中key对应的value，如果key不存在，则返回defaultValue
12 int hashCode() hashCode方法
13 boolean isEmpty() 判断Map是否为空
14 Set<K> keySet() 将Map中所有的key转化为Set集合
15 default V merge(K key, V value,
 BiFunction<? super V, ? super V, ? extends V> remappingFunction) 如果key在Map中不存在或者对应的值为null，则给其一个对应的非null值value。否则根据
 BiFunction规则通过oldValue和value计算一个newValue，替换或删除(newValue为null)原
 键值对
16 V put(K key, V value); 为Map添加一个键值对
17 void putAll(Map<? extends K, ? extends V> m) 将另一个Map的所有键值对添加到该Map中
18 default V putIfAbsent(K key, V value) Java 8新方法，如果Map中key不存在，则添加一个key-value键值对
19 V remove(Object key) 从Map中移除key对应的键值对
20 default boolean remove(Object key, Object value) Java8新方法，删除key-value键值对
21 default V replace(K key, V value) Java8新方法，将Map中key对应的值替换为value
22 default boolean replace(K key, V oldValue, V newValue) Java8新方法，将Map中key-oldValue键值对的value值替换为newValue
23 default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) Java8新方法，将Map中所有的键值对的value，替换为根据BiFunction规则通过key-value
 得到的新值
24 int size() 返回Map中EntrySet的数目
25 Collection<V> values() 返回Map中所有value组成的集合 
3. 实现源码分析 
3.1 LinkedHashMap类声明 
public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
     * LinkedHashMap键值对类
    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);
     * 双向链表头(最老的元素)
    transient LinkedHashMap.Entry<K,V> head;
     * 双向链表尾(最新的元素)
    transient LinkedHashMap.Entry<K,V> tail;
     * LinkedHashMap访问顺序:
     * true: 按访问有序
     * false: 按插入有序
     * @serial
    final boolean accessOrder;
    //成员方法
相比于HashMap，LinkedHashMap中的每一个节点Entry除了有一个next指针(继承自HashMap.Node)外，还有一个指向当前Entry前驱和后继的before、after指针。除此之外，还添加了一个成员变量accessOrder，表示LinkedHashMap访问顺序。LinkedHashMap可以说是通过数组 + 链表 + 红黑树 + 双向链表实现的。假设hash算法就是简单的用key mod 一下表的大小（也就是数组的长度），其中的哈希桶数组table的size=4，负载因子loadFactor=1，通过put顺序添加如下四个元素（5、1、9、3为键值对的key），则LinkedHashMap存储结构如下： 

 由上图可以清楚的看到，LinkedHashMap = HashMap + before&after构成的双向链。当LinkedHashMap发生改变时，当前双向链表结构也会发生改变，保证head始终指向“最老”的节点，tail始终指向“最新”的节点。比如按访问有序前提下，现有LinkedHashMap结构如上图，这时候代码调用了linkedHashMap.get(1)操作，那么节点1会移动到双向链表的尾部，tail指向节点1，节点5的后继变为节点9。下面讲实现时，会详细讲解。 
3.2 构造函数 
* 调用HashMap默认构造函数初始化HashMap，访问顺序按插入有序
public LinkedHashMap() {
    super();
    accessOrder = false;
* 指定HashMap初始容量，访问顺序按插入有序
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
* 通过Map初始化LinkedHashMap
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    //调用HashMap默认构造函数初始化HashMap
    super();
    accessOrder = false;
    //通过调用putMapEntries方法，将Map中的键值对插入到默认构造函数构造的HashMap中
    //putMapEntries方法第二个参数控制插入后是否进行检查，清除最老元素
    //按插入有序，所以在插入元素后，不用考虑是否需要删除最老元素，直接赋值false即可
    putMapEntries(m, false);
* 初始化一定容量，负载因子的HashMap，并指定LinkedHashMap的访问顺序
* 这个构造函数也是唯一一个能够指定访问顺序的构造函数
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
3.3 put操作 
LinkedHashMap类中没有重写HashMap的put和putAll，那么它是怎么实现上面讲的双向链表元素顺序的？我们可能有两个显而易见的疑问，第一LinkedHashMap的节点类型是内部类LinkedHashMap.Entry而非HashMap.Node，LinkedHashMap内部的Entry节点是如何初始化出来的；第二LinkedHashMap没有重写put/putAll方法，是通过什么方式维护双向链表的； 
第一个问题，LinkedHashMap内部的Entry节点是如何实例化出来的。在之前讲HashMap的文章中，我们讲过在putVal方法中，通过调用newNode方法，构建一个待插入的Node对象，而LinkedHashMap重写了newNode方法，构建一个带插入的LinkedHashMap.Entry对象。在HashMap类中，newNode方法被putVal方法调用，而putVal方法会在put及putAll方法中调用，所以当LinkedHashMap对象调用put或putAll方法时，就能保证插入的节点是LinkedHashMap.Entry对象。 
第二个问题，LinkedHashMap对象在调用put或putAll方法后，是如何保证双向链表顺序的。LinkedHashMap.newNode方法中，调用了一个linkNodeLast的linkNodeLast方法，新节点链接在内部双向链表的尾部。下面结合源码来看一下： 
public V put(K key, V value) {
    // 对key的hashCode()做hash
    return putVal(hash(key), key, value, false, true);
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 1：tab为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2：计算index，并对null做处理 
    if ((p = tab[i = (n - 1) & hash]) == null) 
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 3：节点key存在，直接覆盖value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 4：判断该链为红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 5：该链为链表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key,value,null);
                     //链表长度大于8转换为红黑树进行处理
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
                        treeifyBin(tab, hash);
                    break;
                 // key已经存在直接覆盖value
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) 
                           break;
                p = e;
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
    ++modCount;
    // 6：超过最大容量 就扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
上面是HashMap的put方法，在putVal方法中，如果需要插入节点，则调用newNode方法生成待插入的节点对象。LinkedHashMap类中重写的newNode如下： 
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    //调用LinkedHashMap.Entry的构造函数，生成Entry节点
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    //调整双向链表结构，是新插入的节点p插入到双向链表尾部
    linkNodeLast(p);
    return p;
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    //tail指针移到p节点
    tail = p;
    //如果插入p节点之前链表为null，则讲head指针指向新插入的节点p
    if (last == null)
        head = p;
    else {
        //讲新插入的节点p插入到双向链表尾部
        p.before = last;
        last.after = p;
这就是为什么调用HashMap的put/putAll方法，可以生成LinkedHashMap.Entry类型的节点插入，同时可以维护双向链表顺序的原因，如下图所示： 
 下面看一下HashMap类putVal方法两个比较“别致”的方法afterNodeAccess和afterNodeInsertion。这两个方法是钩子方法，在HashMap中并没有具体实现，只是一个空方法，LinkedHashMap中重写了这两个方法。 
afterNodeAccess：负责当LinkedHashMap按访问有序时，节点被访问后，调整双向链表结构，讲最新访问的节点移动到双向链表的尾部。
afterNodeInsertion：负责在插入节点后检查是否需要清除最老的节点(就是上文讲的实现LRU) 
LinkedHashMap中afterNodeAccess实现如下： 
void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    //如果LinkedHashMap按访问有序，并且刚被访问的节点e不是双向链表尾节点，则调整双向链表
    if (accessOrder && (last = tail) != e) {
        //p为刚被访问的节点，b为p的前驱节点，a为p的后继节点
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        //首先将p的后继指针断开
        p.after = null;
        //如果p为双向链表头结点，则将head指针指向p的后继节点a
        if (b == null)
            head = a;
            //如果p不是双向链表头结点，则将p的前驱节点的后继指针指向p的后继节点a
            b.after = a;
        //如果p的后继节点a不为null，则将a的前驱指针指向p的前驱节点b
        if (a != null)
            a.before = b;
            last = b;
        if (last == null)
            head = p;
        else {
            //将p节点连接到双向链表尾部
            p.before = last;
            last.after = p;
        tail = p;
        ++modCount;

 afterNodeAccess除了在HashMap类的put方法中调用外，在replace、merge、compute方法中也有调用，保证按访问有序情况下，最后被访问的节点会被移到双向链表尾部。 
LinkedHashMap中afterNodeInsertion实现如下： 
void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K,V> first;
    //如果evit为tur(需要删除最老元素)，并且双向链表不为null，并且removeEldestEntry方法返回true
    //则清除head指向的节点(最老的节点)
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
这里回头看一下本文开头讲的LRUCache类，重写了removeEldestEntry方法，因为LinkedHashMap中默认返回false，如下： 
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
如果想要实现LRU，子类中要重写该方法。 
3.4 remove操作 
LinkedHashMap也没有重写remove()方法，remove操作是通过调用HashMap的remove方法实现的，根据上节讲的LinkedHashMap要维护双向链表，那么是不是HashMap的remove方法中定义了钩子方法，然后在LinkedHashMap中实现，删除双向链表中的相应节点，答案是肯定的。 
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    p = e;
                } while ((e = e.next) != null);
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
    return null;
afterNodeRemoval就是钩子方法，LinkedHashMap中实现如下： 
* LinkedHashMap删除节点后，将节点从双向链表中移除
void afterNodeRemoval(Node<K,V> e) {
    //当前删除的节点是p，b是删除节点的前驱节点，a是删除节点的后继节点1
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    //首先将p的前驱指针和后继指针清空
    p.before = p.after = null;
    //如果p为双向链表头结点，则直接将head指针指向p的后继节点a
    if (b == null)
        head = a;
    //如果p不是双向链表头结点，则将p的前驱节点的后继指针指向p的后继节点a
        b.after = a;
    //如果p为双向链表尾节点，则直接将tail指针指向p的前驱节点b
    if (a == null)
        tail = b;
    //如果p不是双向链表的尾节点，则将p的后继节点的前驱指针指向p的前驱节点b
        a.before = b;
 也就是讲当LinkedHashMap删除节点，是通过调用HashMap的remove方法实现的，在HashMap删除节点后，会调用afterNodeRemoval方法，该方法在LinkedHashMap中实现，讲待删除节点从双向链表中移除。 
3.5 get方法 
LinkedHashMap中重写了HashMap的get方法，如果LinkedHashMap按访问有序，则在访问后会调用上面讲的afterNodeAccess方法，调整双向链表结构。实现如下： 
public V get(Object key) {
    Node<K,V> e;
    //调用HashMap的getNode方法，获取key对应的Node节点
    if ((e = getNode(hash(key), key)) == null)
        return null;
    //如果LinkedHashMap按访问有序，则将刚访问的节点e，移动到双向链表的尾部
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
同样，getOrDefault的实现思想也是一样的，如下： 
public V getOrDefault(Object key, V defaultValue) {
   Node<K,V> e;
   if ((e = getNode(hash(key), key)) == null)
       return defaultValue;
   if (accessOrder)
       afterNodeAccess(e);
   return e.value;
其实对比HashMap的实现，可以发现，LinkedHashMap其实就是比HashMap多了个如果按访问有序，则维护双向链表的逻辑。 
3.6 containsKey方法 
LinkedHashMap中没有重写containsKey方法，完全复用HashMap的containsKey方法，因为判断key是否存在，不涉及双向链表的维护，且HashMap的containsKey方法的时间复杂度为O(1)，效率较高，没必要重写。 
3.7 containsValue方法 
HashMap中判断value是否存在，是通过遍历hash桶数组的每个元素，然后依次判断链表/红黑树中是否存在相等的value得到的，如下： 
public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
    return false;
两层for循环，时间复杂度应该在O(n) ~ O(n^2)之间。虽然判断value在Map中是否存在也不涉及双向链表的改变，但LinkedHashMap依然没有采用这种方式，因为LinkedHashMap内部维护了一个双向链表，直接通过双向链表访问HashMap所有节点，依次判断即可，时间复杂度为O(n)。LinkedHashMap中重写的containsValue方法如下： 
public boolean containsValue(Object value) {
    //遍历双向链表，判断value是否存在
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    return false;
4. LinkedHashMap特点 
LinkedHashMap是基于HashMap实现的，除了HashMap键值对之间无序这一特点之外的特点，LinkedHashMap都有
LinkedHashMap可以保证插入有序或访问有序，访问有序可以很方便地实现LRU算法 
 参考链接： 
 Java API源码
《Java编程的逻辑》 
1、继承扩展HashMap，实现Map接口，基于双链表实现有序，支持插入有序和访问顺序
2、允许NULL元素，基本操作(add、contrains、remove)与HashMap一样有稳定性能（hash分布均匀情况下）
3、由于需要维护链表，性能较HashMap差，而迭代可能不一定，LinkedHashMap的迭代所需时间与 大小 成比例，HashMap迭代所需时间与 容量 成比例...
源码基于jdk 1.7.81
LinkedHashMap 继承自 HashMap，实现了 Map 接口，所以它具有 Map 的所有方法和特性，同时 LinkedHashMap 继承了 HashMap 所有非私有的成员变量方法。
public class LinkedHashMap&lt;K,V&gt; extends HashMap&lt;K,V&g...
在Map集合框架中，除了HashMap以外，TreeMap也是我们工作中常用到的集合对象之一。
与HashMap相比，TreeMap是一个能比较元素大小的Map集合，会对传入的key进行了大小排序。其中，可以使用元素的自然顺序，也可以使用集合中自定义的比较器来进行排序；
不同于HashMap的哈希映射，TreeMap底层实现了树形结构，至于具体形态，你可以简单的理解为一颗倒过来的树---根在上--叶在下。如果用计算机术语来说的话，TreeMap实现了红黑树的结..
				LinkedHashMap是基于HashMap实现的一种集合，具有HashMap 集合的所有特点，除了 HashMap 无序的特点，LinkedHashMap 是有序的。
#include<iostream
import java.util.LinkedHashMap;
Map<Integer,Integer>mp = new LinkedHashMap<Integer, Integer>();
mp.put(key,value);
				我们总说哈希表（HashMap）是以O（1）的时间插入，然后遍历时是无序的，也就是说，hash过后就不一定插在了数组什么位置了。这样导致我们无法保证获取到的键顺序。
但是LinkedHashMap就不一样，按照我们的理解，里面应该还有一个线性结构，来保存HashMap的插入顺序，以至于遍历时能够获得按插入顺序得到的顺序。
接下来我们就分析一下它的源码。
public class Linke...
				LinkedHashMap是HashMap的子类，但内部还有一个双向链表维护键值对的顺序，每个键值对既位于哈希表中，也位于这个双向链表中。LinkedHashMap支持两种顺序：一种是插入顺序；另外一种是访问顺序。
插入顺序容易理解，先添加的在前面，后添加的在后面，修改操作不影响顺序。
        LinkedHashMap<String, Integer> seqMap = new LinkedHashMap<>();
        seqMap.put(
                    一行代码能搞定的事情，没必要写个工具类
// List<Shop>转换为List<ShopQueryDto> 
        List<Shop> shopList= getXxxList(shop);
        List<ShopQueryDto> list = shopList.stream().map(x -> dozer.map(x,ShopQueryDto.class)).collect(Collectors.toList());
                Spring Boot + Mybatis数据源配置的三种方式
                    Sharon~: 
                    同问3.3@Import注解是必须加的吗？
                golang websocket编程
                    Nihility/: 
                    能跑起来吗
                Spring Boot + Mybatis数据源配置的三种方式
                    征途黯然.: 
                    感谢博主，你的文章让我得到一些收获！(￣ˇ￣)

S.N.	方法	说明
1	public LinkedHashMap()	默认构造函数，调用HashMap默认构造函数，元素保持按插入有序
2	public LinkedHashMap(int initialCapacity)	指定初始化时HashMap的容量，元素保持按插入有序
3	public LinkedHashMap(int initialCapacity, float loadFactor)	指定初始化时HashMap的容量和负载因子，元素保持按插入有序
4	public LinkedHashMap(Map<? extends K, ? extends V> m)	通过Map构建LinkedHashMap，，元素保持按插入有序
5	public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)	指定初始化时HashMap的容量和负载因子，以及迭代输出节点的顺序，accessOrder为true时，元素间保持按访问有序

S.N.	方法	说明
1	void clear()	清除Map中所有的KV映射
2	default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)	Java 8新方法，如果key在Map中不存在，则根据Function规则计算key对应的value值，并进行put操作(前提计算得到的value值也不为null)
3	default V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)	Java 8新方法，如果key在Map中存在，则根据BiFunction规则通过key和对应的value 计算newValue，如果newValue为null，则删除key对应的键值对，否则替换key对应的value值
4	default V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)	Java 8新方法，相当于上述两个方法的综合，根据BiFunction，通过key和对应的value 计算newValue，如果newValue为null，会删除对应KV映射，否则会插入或替换原KV映射
5	boolean containsKey(Object key)	判断Map中是否存在key键
6	boolean containsValue(Object value)	判断Map中是否存在value值
7	Set<Map.Entry<K, V>> entrySet()	将Map所有的键值对转换为Set集合
8	boolean equals(Object o)	equals方法
9	default void forEach(BiConsumer<? super K, ? super V> action)	Java 8新方法，遍历Map，通过BiConsumer处理Map中每一个键值对的key、value
10	V get(Object key)	获取Map中key对应的value
11	default V getOrDefault(Object key, V defaultValue)	Java 8新方法，获取Map中key对应的value，如果key不存在，则返回defaultValue
12	int hashCode()	hashCode方法
13	boolean isEmpty()	判断Map是否为空
14	Set<K> keySet()	将Map中所有的key转化为Set集合
15	default V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)	如果key在Map中不存在或者对应的值为null，则给其一个对应的非null值value。否则根据 BiFunction规则通过oldValue和value计算一个newValue，替换或删除(newValue为null)原键值对
16	V put(K key, V value);	为Map添加一个键值对
17	void putAll(Map<? extends K, ? extends V> m)	将另一个Map的所有键值对添加到该Map中
18	default V putIfAbsent(K key, V value)	Java 8新方法，如果Map中key不存在，则添加一个key-value键值对
19	V remove(Object key)	从Map中移除key对应的键值对
20	default boolean remove(Object key, Object value)	Java8新方法，删除key-value键值对
21	default V replace(K key, V value)	Java8新方法，将Map中key对应的值替换为value
22	default boolean replace(K key, V oldValue, V newValue)	Java8新方法，将Map中key-oldValue键值对的value值替换为newValue
23	default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function)	Java8新方法，将Map中所有的键值对的value，替换为根据BiFunction规则通过key-value 得到的新值
24	int size()	返回Map中EntrySet的数目
25	Collection<V> values()	返回Map中所有value组成的集合