Java研究院 Java研究院

人非生而知之者,知之,而后知不知。

目录
基于LinkedHashMap实现LRUCache详解
/    

基于LinkedHashMap实现LRUCache详解

首先需要知道一点,为什么要使用 LinkedHashMap 来实现 LRUCache?

这是因为 LinkedHashMap 是有序的,它保存了 记录的插入顺序,在用 Iterator 遍历LinkedHashMap 时,先得到的记录肯定是先插入的,这样就为我们实现 LRUCache(最近最少使用算法)提供了便利。

LinkedHashMap

何谓有序

为了加深大家对LinkedHashMap的理解,请先看如下代码运行后的输出效果。

image.png

image.png

注意:

1、两段代码的区别在于accessOrder不一致。
2、当遍历的时候用的entrySet而不是keySet,大家可以试试accessOrder为true时,用keySet来遍历会出现什么情况。

我相信,通过上述例子,大家已经能直观的感受到一点,被访问的元素,被移动到了末尾,这就为我们实现LRUCache 打下了基础。

数据结构

LinkedHashMap 是HashMap的子类,并且内部维护了一个双向链表以及是否有序的标志字段accessOrder

如何实现LRUCache

实现LRUCache之前,我们首先要弄明白一点:借助 LinkedHashMap 来实现 LRUCache,是利用了其访问元素会将元素移动到链表尾部,而在插入元素时也是将元素插入到链表尾部,且如果容量溢出会删除链表头部元素这一特性的。

指定缓存个数

除了元素的移动,其中还暗藏一个关键点,就是元素个数是固定的,所以LRUCache有一个唯一的构造方法,参数就是元素的 maxSize。

public LruCache(int maxSize) {

    ...

    this.maxSize = maxSize;
    /*
     * 初始化LinkedHashMap
     * 第一个参数:initialCapacity,初始大小
     * 第二个参数:loadFactor,负载因子=0.75f,即到75%容量的时候就会扩容
     * 第三个参数:①accessOrder=true基于访问顺序排序②accessOrder=false基于插入顺序排序
     */
    this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}

访问元素移动到链尾

大家去看官方提供的 LRUCache 实现的时候,会发现他本身没有体现缓存的逻辑,因为在调用 get方法的时候,是调用量底层 LinkedHashMap 的实现。

而其中的关键点在于私有化的 makeTail 方法,将访问元素移动到链尾。

private void makeTail(LinkedEntry<K, V> e) {
        // Unlink e 在链表中删除该节点e
        e.prv.nxt = e.nxt;
        e.nxt.prv = e.prv;

        // Relink e as tail 在尾部添加
        LinkedEntry<K, V> header = this.header;
        LinkedEntry<K, V> oldTail = header.prv;
        e.nxt = header;
        e.prv = oldTail;
        oldTail.nxt = header.prv = e;
        modCount++;
}

元素溢出处理

上文有提到 maxSize,那新增的时候自然免不了元素溢出的问题。因为元素被访问和新增的时候都是在链尾,所以当新增元素溢出的时候,直接从链首进行元素移除,判断是否溢出即可。

其中的一个关键方法就是 trimToSize :

public void trimToSize(int maxSize) {
    /*
     * 这是一个死循环,
     * 1.只有 扩容 的情况下能立即跳出
     * 2.非扩容的情况下,map的数据会一个一个删除,直到map里没有值了,就会跳出
     */
    while (true) {
        K key;
        V value;
        synchronized (this) {
            // 在重新调整容量大小前,本身容量就为空的话,会出异常的。
            if (size < 0 || (map.isEmpty() && size != 0)) {
                throw new IllegalStateException(getClass().getName() + ".sizeOf() is reporting inconsistent results!");
            }
            // 如果是 扩容 或者 map为空了,就会中断,因为扩容不会涉及到丢弃数据的情况
            if (size <= maxSize || map.isEmpty()) {
                break;
            }

            Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
            key = toEvict.getKey();
            value = toEvict.getValue();
            map.remove(key);
            // 拿到键值对,计算出在容量中的相对长度,然后减去。
            size -= safeSizeOf(key, value);
            // 添加一次收回次数
            evictionCount++;
        }
        /*
         * 将最后一次删除的最少访问数据回调出去
         */
        entryRemoved(true, key, value, null);
    }
}

实际上:

  • put 开始的时候确实是把值放入 LinkedHashMap 了,不管超不超过你设定的缓存容量
  • 然后根据 safeSizeOf 方法计算 此次添加数据的容量是多少,并且加到 size
  • 说到 safeSizeOf 就要讲到 sizeOf(K key, V value) 会计算出此次添加数据的大小
  • 直到 put 要结束时,进行了 trimToSize 才判断 size 是否 大于 maxSize 然后进行最近很少访问数据的移除

才疏学浅,难免有坑,有坑也不填
标题:基于LinkedHashMap实现LRUCache详解
地址:https://studying.icu/articles/2021/10/12/1634002769769.html