【Java容器源码】LinkedHashMap 实现 LRU 策略源码分析

向右看齐 2022-12-05 12:16 235阅读 0赞

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

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

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

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

  1. // LinkedHashMap继承了HashMap
  2. public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{
  3. // 链表头
  4. transient LinkedHashMap.Entry<K,V> head;
  5. // 链表尾
  6. // 如果head=tail=null,则链表为空
  7. transient LinkedHashMap.Entry<K,V> tail;
  8. //--------------------------------Node-----------------------------------------
  9. // 在LinkedHashMap的节点叫Entry,继承HashMap的Node
  10. static class Entry<K,V> extends HashMap.Node<K,V> {
  11. // 为数组的每个元素增加了 before 和 after 属性
  12. Entry<K,V> before, after;
  13. // 但是构造函数没变,没有将链表的before和after加进去
  14. Entry(int hash, K key, V value, Node<K,V> next) {
  15. super(hash, key, value, next);
  16. }
  17. }
  18. // 控制LRU是否开启的元素之一,表示是否允许在访问(get)后,将当前节点移动到链表尾部,默认是false
  19. // 注:另一个开启元素是put时的删除策略是否允许删除头节点,默认返回false
  20. final boolean accessOrder;
  21. //-------------------------------构造函数-------------------------------------
  22. public LinkedHashMap(int initialCapacity, float loadFactor) {
  23. super(initialCapacity, loadFactor);
  24. accessOrder = false; // 将accessOrder置为false
  25. }
  26. public LinkedHashMap(int initialCapacity) {
  27. super(initialCapacity);
  28. accessOrder = false;
  29. }
  30. public LinkedHashMap() {
  31. super();
  32. accessOrder = false;
  33. }
  34. // 可以通过此构造方法设置 accessOrder,即要开启LRU策略必须通过该构造函数
  35. public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
  36. super(initialCapacity, loadFactor);
  37. this.accessOrder = accessOrder;
  38. }
  39. }

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

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

在这里插入图片描述

1.增加元素时实现LRU

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

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

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

  1. 具体实现策略是什么?要从 get 和 put 两方面入手

    • get:当每访问一个节点(get)后,就将当前节点置于链表尾部

      • 重置于尾部的原因:新节点尾插到链表,意味着尾部本来就新
      • 这也等同于越往前的节点越久,且没访问
    • put:当插入一个节点(put)后,且满足所有删除条件,就删除头节点

      • 这里的一定条件其实就是删除策略,一般需要用户自定义,比如 size>3 等
  2. 如何设置开启执行 LRU?同样要从 get 和 put 入手,但默认是关闭的

    • get:要将 accessOrder 置为 true,表示同意 get 过的节点移到链表最后,默认是false,需构造时开启
    • put:removeEldestEntry 方法要能返回 true,表示删除策略允许删除,默认是 false,一般需要重写

      注:其实还有两个因素 evict=true(put时默认),队列不为空(一般不涉及)

put()

HashMap 的 put 方法

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

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

putVal()

HashMap 的 putVal 方法

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

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

newNode()

LinkedHashMap 重写了 HashMap 的 newNode 方法

  1. 新增节点 Entry
  2. 调用 linkNodeLast 追加到链表的尾部

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

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

    }

linkNodeLast()

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

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

afterNodeInsertion()*

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

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

removeEldestEntry()

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

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

    protected boolean removeEldestEntry(Map.Entry eldest) {

    1. return false;

    }

2.获取元素时实现LRU

get()

LinkedHashMap 重写了 HashMap 的 get 方法:

  1. 获取具体节点还是调用HashMap的getNode方法
  2. 只不过在获取到node后,加入了移动node到队尾以实现LRU的操作

    public V get(Object key) {

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

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

afterNodeAccess()*

将访问的节点移到队尾

  1. void afterNodeAccess(Node<K,V> e) {
  2. // move node to last
  3. LinkedHashMap.Entry<K,V> last;
  4. // accessOrder 为 true,并且 e 不为队尾的时候
  5. if (accessOrder && (last = tail) != e) {
  6. LinkedHashMap.Entry<K,V> p =
  7. (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
  8. p.after = null;
  9. if (b == null)
  10. head = a;
  11. else
  12. b.after = a;
  13. if (a != null)
  14. a.before = b;
  15. else
  16. last = b;
  17. if (last == null)
  18. head = p;
  19. else {
  20. p.before = last;
  21. last.after = p;
  22. }
  23. tail = p;
  24. ++modCount;
  25. }
  26. }

LRU示例

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

打印出的结果如下

  1. 初始化:{9:9,20:20,1:1}
  2. map.get(9):{20:20,1:1,9:9}
  3. 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 被移动到队尾,这个体现了经常被访问的节点会被移动到队尾。

发表评论

表情:
评论列表 (有 0 条评论,235人围观)

还没有评论,来说两句吧...

相关阅读