【Java容器源码】LinkedHashMap 实现 LRU 策略源码分析-蒲公英云

HashMap 是无序的，TreeMap 可以按照 key 进行排序，那有木有 Map 是可以维护插入的顺序的呢？接下来我们一起来看下 LinkedHashMap。

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

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

LinkedHashMap 继承关系，核心成员变量，主要构造函数：

// LinkedHashMap继承了HashMap
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{
    // 链表头
    transient LinkedHashMap.Entry<K,V> head;
    // 链表尾
    // 如果head=tail=null，则链表为空
    transient LinkedHashMap.Entry<K,V> tail;
    //--------------------------------Node-----------------------------------------
    // 在LinkedHashMap的节点叫Entry，继承HashMap的Node
    static class Entry<K,V> extends HashMap.Node<K,V> {
        // 为数组的每个元素增加了 before 和 after 属性
        Entry<K,V> before, after;
        // 但是构造函数没变，没有将链表的before和after加进去
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
    // 控制LRU是否开启的元素之一，表示是否允许在访问（get）后，将当前节点移动到链表尾部，默认是false
    // 注：另一个开启元素是put时的删除策略是否允许删除头节点，默认返回false
    final boolean accessOrder;
    //-------------------------------构造函数-------------------------------------
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false; // 将accessOrder置为false
    }    
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }
    public LinkedHashMap() {
        super();
        accessOrder = false;
    } 
    // 可以通过此构造方法设置 accessOrder，即要开启LRU策略必须通过该构造函数
     public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
}

从上述 Map 新增的属性可以看到，LinkedHashMap 的数据结构很像是把 LinkedList 的每个元素换成了 HashMap 的 Node，像是两者的结合体，也正是因为增加了这些结构，从而能把 Map 的元素都串联起来，形成一个链表，而链表就可以保证顺序了，就可以维护元素插入进来的顺序。

LinkedHashMap 是通过双向链表和散列表这两种数据结构组合实现的，其中的“Linked”实际上是指的是双向链表，并非指用链表法解决散列冲突。

在这里插入图片描述

1.增加元素时实现LRU

LinkedHashMap 本身是没有 put 方法实现的，由于继承了 HashMap，所以会调用 HashMap 的 put 与 putVal 方法。但仅仅这样是不够的还要考虑 LinkedHashMap 的 2 个特性

1）LinkedHashMap 要有链表特性，所以还要将新加入的节点尾插到链表中

2）LinkedHashMap 可以实现 LRU，原因是已经实现链表，但需要考虑以下两个问题：

具体实现策略是什么？要从 get 和 put 两方面入手
- get：当每访问一个节点（get）后，就将当前节点置于链表尾部
  - 重置于尾部的原因：新节点尾插到链表，意味着尾部本来就新
  - 这也等同于越往前的节点越久，且没访问
- put：当插入一个节点（put）后，且满足所有删除条件，就删除头节点
  - 这里的一定条件其实就是删除策略，一般需要用户自定义，比如 size>3 等
如何设置开启执行 LRU？同样要从 get 和 put 入手，但默认是关闭的
- get：要将 accessOrder 置为 true，表示同意 get 过的节点移到链表最后，默认是false，需构造时开启
- put：removeEldestEntry 方法要能返回 true，表示删除策略允许删除，默认是 false，一般需要重写
  
  注：其实还有两个因素 evict=true（put时默认），队列不为空（一般不涉及）

put()

HashMap 的 put 方法

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
}

注：因为是直接调用 HashMap 的 hash，所以 LinkedHashMap 也可以放入 key 为 null 的 Node。

putVal()

HashMap 的 putVal 方法

// evict:决定是否删除最少访问元素，默认true
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
       .......
        // 调用newNode新增节点，但在LInkedHashMap中，重写了newNode方法，因为节点
        tab[i] = newNode(hash, key, value, null);
       ......
       // 在HashMap中是空实现，但linkedListMap中具体实现了
       afterNodeInsertion(evict);
 }

PS：这里本质是依赖倒置的设计原则，上层定义接口，下层实现

newNode()

LinkedHashMap 重写了 HashMap 的 newNode 方法

新增节点 Entry

调用 linkNodeLast 追加到链表的尾部

Node newNode(int hash, K key, V value, Node e) {

// 新增节点，这里是new LinkedHash.Entry
LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
// 追加到链表的尾部
linkNodeLast(p);
return p;

}

linkNodeLast()

因为 LinkedHashMap 还有链表特性，所以不能只是 HashMap 那样添加到哈希表上，而是还要添加到链表上

// 入参是新创建的节点
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail; // 暂存tail    
    tail = p; // 将tail置为新节点p
    if (last == null) // last 为空，说明链表为空，所以还要将head设为新节点p
        head = p;    
    else {
     // 链表非空，直接建立新增节点和上个尾节点之间的前后关系即可
        p.before = last;
        last.after = p;
    }
}

afterNodeInsertion()*

afterNodeInsertion 方法在HashMap中是空实现，在 LinkedHashMap 中是为了实现 LRU 策略

void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K,V> first;
    // 要删除头节点要满足三个条件
    // 1.evict=true，在put方法中默认是true
    // 2.队列不为空，但一般不牵扯这个问题，因为节点加入后才会执行该方法
    // 3.删除策略策略允许删除，默认false
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true); // removeNode 删除头节点
    }
}

removeEldestEntry()

removeEldestEntry一般用于自定义删除策略，返回true表示执行删除头结点，返回false表示不删除

该方法一般需要用户重写，比如 return size>3时删除
在LinkedHashMap中提供了默认实现，即直接返回false（不删除，也可以理解成默认无法执行lru）

protected boolean removeEldestEntry(Map.Entry eldest) {
```
    return false;
```
}

2.获取元素时实现LRU

get()

LinkedHashMap 重写了 HashMap 的 get 方法：

获取具体节点还是调用HashMap的getNode方法

只不过在获取到node后，加入了移动node到队尾以实现LRU的操作

public V get(Object key) {

    Node<K,V> e;
    // 调用 HashMap.getNode()获取具体节点
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 如果设置了 LRU 策略
    if (accessOrder)
        // 这个方式把当前 key 移动到队尾
        afterNodeAccess(e);
    return e.value;
}

不仅仅是 get 方法，执行 getOrDefault、compute、computeIfAbsent、computeIfPresent、merge 方法时，也会不断的把经常访问的节点移动到队尾，那么靠近队头的节点，自然就是很少被访问的元素了。

afterNodeAccess()*

将访问的节点移到队尾

void afterNodeAccess(Node<K,V> e) {
     // move node to last
        LinkedHashMap.Entry<K,V> last;
        // accessOrder 为 true，并且 e 不为队尾的时候
        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;
        }
    }

LRU示例

public void testAccessOrder() {
  // 构建 LinkedHashMap，这里必须使用唯一的能设置accessOrder的构造函数
  LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>(4,0.75f,true) {
      // 注：可以在构造函数后初始化（必须加大括号）或重写方法（直接重写）， new A() { {初始化} / 重写方法 };
    {
      put(10, 10); // 注：调用容器具体函数初始化时，必须再加{}
      put(9, 9);
      put(20, 20);
      put(1, 1);
    }
    @Override
    // 覆写了删除策略的方法，允许返回true；即当已经有大于3个槽点被使用时，开始删除链表头结点
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
      return size() > 3;
    }
  };
  log.info("初始化：{}",JSON.toJSONString(map));
  Assert.assertNotNull(map.get(9));
  log.info("map.get(9)：{}",JSON.toJSONString(map));
  Assert.assertNotNull(map.get(20));
  log.info("map.get(20)：{}",JSON.toJSONString(map));
}

打印出的结果如下

初始化：{9:9,20:20,1:1}
map.get(9)：{20:20,1:1,9:9}
map.get(20)：{1:1,9:9,20:20}

可以看到，map 初始化的时候，我们放进去四个元素，但结果只有三个元素，10 不见了，这个主要是因为我们覆写了 removeEldestEntry 方法，我们实现了如果 map 中元素个数大于 3 时，我们就把队头的元素删除，当 put(1, 1) 执行的时候，正好把队头的 10 删除，这个体现了达到我们设定的删除策略时，会自动的删除头节点。

当我们调用 map.get(9) 方法时，元素 9 移动到队尾，调用 map.get(20) 方法时，元素 20 被移动到队尾，这个体现了经常被访问的节点会被移动到队尾。