1、使用场景

1.1 构造函数中的accessOrder

LinkedHashMap的构造函数中，有这么一种重载形式：

  1. public LinkedHashMap(int initialCapacity,
  2.                          float loadFactor,
  3.                          boolean accessOrder) {
  4.         super(initialCapacity, loadFactor);
  5.         this.accessOrder = accessOrder;
  6.     }

这也是传入accessOrder这个boolean类型值的唯一的一个重载类型。对accessOrder入参做个说明：

  • accessOrder作为构造函数的入参之一，决定了LinkedHashMap是否开启LRU机制；
  • accessOrder为true代表开启了LRU机制，对应模式为access-order；为false代表遍历顺序是插入顺序，并不是最近访问的顺序，对应模式为insertion-order；

  • accessOrder默认为false，即默认没有开启LinkedHashMap的LRU机制。

    1.1.1 关闭LRU机制

    当创建LinkedHashMap没有指定accessOrder（默认为false）时，此时的LinkedHashMap可以按照插入（put）的顺序进行访问（get），举例如下：

    1. public static void main(String[] args) {
    2.   Map<String, String> map = new LinkedHashMap<String, String>(9);
    4.   map.put("化学","93");
    5.   map.put("数学","98");
    6.   map.put("生物","92");
    7.   map.put("英语","97");
    8.   map.put("物理","94");
    9.   map.put("历史","96");
    10.   map.put("语文","99");
    11.   map.put("地理","95");
    13.   map.forEach((k, v) -> {
    14.       System.out.println(k + ":" + v);
    15.   });
    16. }

    结果：
    image.png
    从上图可以看出，遍历LinkedHashMap的结果正是按照插入的顺序来的，而HashMap并不存在保证插入顺序的机制，因此当开发过程中需要保持k-v的集合能保持k-v插入顺序时，首先想到的就是LinkedHashMap。

    1.1.2 开启LRU机制

    当构造函数中accessOrder参数指定为true时就开启了LinkedHashMap的LRU机制，如下：

    1. public static void main(String[] args) {
    2.       Map<String, String> map = new LinkedHashMap<>(8, 0.75f, true);
    4.       map.put("化学","93");
    5.       map.put("数学","98");
    6.       map.put("生物","92");
    7.       map.put("英语","97");
    8.       map.put("物理","94");
    9.       map.put("历史","96");
    10.       map.put("语文","99");
    11.       map.put("地理","95");
    13.       map.get("英语");
    14.       map.get("化学");
    15.       map.forEach((k, v) -> System.out.println(k + ":" + v));
    16.   }

    结果：
    image.png
    从上图可以看出，LinkedHashMap将最近访问的k-v放置到了双向链表的尾部，因此遍历时最近访问的k-v都在最后面。

    1.2 用LinkedHashMap实现LRU

    LRU是Least Recently Used 的缩写，即最近最少使用。如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

现在我们就基于LinkedHashMap来实现一个LRU机制的k-v存储类。
LRUMap：

  1. public class LRUMap<K, V> extends LinkedHashMap<K, V> {
  2.     /**
  3.      * LRUMap里最大容纳的元素个数
  4.      */
  5.     int maxSize;
  7.     public LRUMap(int maxSize) {
  8.         // 这里调用父类LinkedHashMap的构造函数，其中第三个入参accessOrder必须指定为true
  9.         // 这样才能开启LinkedHashMap的LRU机制
  10.         super(16, 0.75f, true);
  11.         this.maxSize = maxSize;
  12.     }
  14.     @Override
  15.     public boolean removeEldestEntry(Map.Entry<K, V> eldest) {
  16.         // 当底层的LinkedHashMap的容量size大于LRUMap定义的最大容量maxSize时，开始淘汰最久没有被访问到的元k-v
  17.         return super.size() > maxSize;
  18.     }
  19. }

Main：

  1. public class Main {
  2.     public static void main(String[] args) {
  3.         // 初始化一个LRUMap实例，指定最大容纳量为4，
  4.         // 即lruMap中的元素个数超过4时开启淘汰
  5.         LRUMap<String, Integer> lruMap = new LRUMap<>(4);
  7.         lruMap.put("化学",93);
  8.         lruMap.put("数学",98);
  9.         lruMap.put("生物",92);
  10.         lruMap.put("英语",97);
  11.         // 开启淘汰前打印lruMap，此时lruMap中元素顺序时按照插入顺序打印的
  12.         System.out.println(lruMap);
  14.         lruMap.put("物理",94);
  15.         lruMap.put("历史",96);
  16.         // 开启淘汰后打印lruMap，此时lruMap中key为"化学"、"数学"的k-v对被淘汰
  17.         System.out.println(lruMap);
  18.     }
  19. }

结果：

{化学=93, 数学=98, 生物=92, 英语=97}
{生物=92, 英语=97, 物理=94, 历史=96}

说明：

  • LRUMap继承了LinkedHashMap，增删改查操作基本是使用了LinkedHashMap的继承实现类HashMap提供的public的增删改查方法（LinkedHashMap的get方法还是区别于HashMap的get方法）。LRUMap中仅引入了LRU机制的触发条件，即覆写了LinkedHashMap的removeEldestEntry方法，在该方法里定义了LRU机制的触发条件；
  • LinkedHashMap的removeEldestEntry方法里定义了LRU机制的触发条件，该方法在LinkedHashMap中直接返回false，即默认情况下LinkedHashMap没有开启LRU机制（LinkedHashMap的构造函数里accessOrder为false也代表默认没有打开LRU机制）。该方法返回一个boolean值，令触发LRU的情景返回true即可；

  • 开启了LRU机制后，最近访问的节点在LinkedHashMap的底层双向链表的尾部，很久没访问的节点在双向链表的头部，这是LinkedHashMap的get方法里定义并实现的。

    2、源码浅析

    LinkedHashMap的继承实现关系如下：

    public class LinkedHashMap<K,V>
  extends HashMap<K,V>
  implements Map<K,V>{}

    由于继承自HashMap实现类，HashMap中对外提供的接口LinkedHashMap也同样提供，尤其是增删改查方法就是使用的HashMap的增删改查方法。

    2.1 底层数据结构

    LinkedHashMap之所以能维护元素的插入顺序，原因是LinkedHashMap底层是一个双向链表，相比HashMap中底层单元是Node实例，有一个指向下一个Node实例的next指针，LinkedHashMap底层单元是Entry实例，这个Entry里多了双向链表结构的前指针（before）和后指针（after），这两个指针记录了LinkedHashMap中上一个Entry节点和下一个Entry节点（即插入顺序）。
    LinkedHashMap数据结构如下图所示：
    image.png
    LinkedHashMap中存储k-v的基本单元Entry类源码如下：

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

    说明：

  • Entry类继承自父类HashMap中的基本数据单元Node类；

  • 新增指向上一个节点的指针before，和指向下一个节点的指针after。

    2.2 重要成员属性

    ```java // 双向链表的头节点，也是最早访问的节点 transient LinkedHashMap.Entry head;

// 双向链表的尾节点，也是最近访问的节点 transient LinkedHashMap.Entry tail;

// 初始化时可以显式指定该字段，当为true时代表访问顺序，当为false时代表插入顺序 final boolean accessOrder;

<a name="o2vkd"></a>
## 2.3 构造方法
```java
// 初始化时指定初始容量和负载因子
public LinkedHashMap(int initialCapacity, float loadFactor) {
    // 调用父类HashMap的构造函数
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

// 初始化时仅指定初始容量
public LinkedHashMap(int initialCapacity) {
    // 调用父类HashMap的构造函数，默认的负载因子为0.75f
    super(initialCapacity);
    accessOrder = false;
}

// 无参构造函数
public LinkedHashMap() {
    // 调用父类HashMap的无餐构造函数
    super();
    accessOrder = false;
}

// 基于传入的Map实现类的实例m初始化
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

// 参数最多的有参构造函数，也是唯一一个传入了accessOrder的构造函数，其他的四个构造函数accessOrder默认为false
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

总结：

  • LinkedHashMap的构造函数，底层都是调用的其父类HashMap的构造函数；

  • LinkedHashMap的accessOrder字段默认为false，即默认情况下LinkedHashMap都是按插入顺序保持k-v。

    2.4 get方法

    与put方法不同，LinkedHashMap的get方法并没有直接使用HashMap的get方法，源码如下：

    public V get(Object key) {
  Node<K,V> e;
  // getNode方法直接使用了HashMap的getNode方法，因为粒度没有细化到底层的数据结构，只到了哈希桶数组这一层
  if ((e = getNode(hash(key), key)) == null)
      return null;

  // 这一块的判断逻辑是LinkedHashMap区别于HashMap的get方法的重要部分
  // 如果指定了要按照访问顺序，则将本次get的节点移到双向链表的尾部
  if (accessOrder)
      afterNodeAccess(e);
  return e.value;
}

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

    看到这个方法仅有的一行注释：“move node to last”也可以知道这个方法要做的事是将入参e挪到双向链表的尾部。

    2.5 put方法

    LinkedHashMap和HashMap的put方法是一样的，LinkedHashMap继承自HashMap，没有重写HashMap的put方法，但是覆写了HashMap里的newNode方法，即LinkedHashMap实例调用put方法时，put方法里的newNode方法是LinkedHashMap覆写的（因为LinkedHashMap的底层数据结构变了，是Entry不是Node，因此新建底层数据节点的方法一定要覆写适配）。

LinkedHashMap的newNode方法源码如下：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        // 调用Entry内部类的构造方法初始化一个p，注意此时p的before和after指针都没初始化，都是null
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);

    // 将p尾插到双向链表中
    linkNodeLast(p);
    return p;
}

linkNodeLast：

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    // 如果链表中没有元素，则头节点的引用head指向p
    if (last == null)
        head = p;
    else {
        // p的after指针不用被初始化，因为p就是新的尾节点，after指针就应该是null
        p.before = last;
        // 之前尾节点的before指针不用更新，只需将after指针指向p即可
        last.after = p;
    }
}

参考

LinkedHashMap原理和底层实现
LinkedHashMap就这么简单【源码剖析】
如何用LinkedHashMap实现LRU缓存算法