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

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

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”实际上是指的是双向链表，并非指用链表法解决散列冲突。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center]

## 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 方法

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 方法

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

Node<K,V> newNode(int hash, K key, V value, Node<K,V> 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<K,V> eldest) {
        
            return false;
    }

## 2.获取元素时实现LRU ##

### get() ###

LinkedHashMap 重写了 HashMap 的 get 方法：

1.  获取具体节点还是调用HashMap的getNode方法
2.  只不过在获取到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 被移动到队尾，这个体现了经常被访问的节点会被移动到队尾。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/ac593e00e2f84483ba89f12181c2b2cc.png