Android 缓存策略之LruCache

LruCache使用LinkedHashMap以强引用的方式存储缓存对象，并提供获取、添加和删除方法。每次访问一个缓存对象，该对象都会被移到队列的头部。如果添加一个缓存对象时缓存区已满，那么首先会把队列末尾的缓存移出缓存区，然后再添加新缓存。被移除的对象可能会被垃圾回收器回收。

正式介绍LruCache之前，先来复习一下几个常见的缓存算法，这可是面试经常会问到的！

LRU (Least recently used)

最近最少使用，如果数据最近被访问过，那么将来被访问的几率也更高。实现步骤原理如下：

新数据插入到链表头部；
每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
当链表满的时候，将链表尾部的节点丢弃。

首先我们搞一个双向链表

现在我们定义一个规则：如果有节点插入或者被访问（get或者set），那么直接放入到链表头部，每一个队列都有一个capacity值表示容量，如果新元素加入，现在达到了容量值，就需要淘汰最近最少使用的，就是尾节点。

例如：现在node1被访问，node1插入到头部

如果现在又来了一个新元素noden+1，超过了容量值。所以：剔除node2，noden+1插入到头部

这就是最近最少使用的算法，LruCache 就是使用的这种策略管理缓存的。

LFU (Least frequently used)

最不经常使用，如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小。

新加入数据插入到队列头部（因为引用计数为1）；
队列中的数据被访问后，引用计数增加，队列重新排序；
当需要淘汰数据时，将已经排序的列表最后的数据块删除。

实际上就是一个下面的结构，矩形表示NodeList，圆形表示Node。

我们的数据是字母，上面矩形表示访问（get和set方法）的次数。先解释一下我们的规则：

NodeList只有在下面有节点的时候才会被创建，如果下面的节点被移除，那么删除该NodeList。
NodeList中head和tail分别指向下面圆形双向链表的头跟尾部。他本身也是一个双向链表。
如果现在有一个新节点W被访问。插入到1下面的双向链表的首部

如果此时A被访问：就到2下面的双向链表的首部。

image.png

如果A再次被访问：

image.png

如果此时C被访问。2下面没有元素了，就删除2，然后C放到3下面的双向链表的首部。

image.png

如果此时A再次被访问，那么创建4的NodeList，然后插入A：

image.png

如果这个时候来了一个H，但是现在达到了最大容量，就要剔除一个，我们剔除1下面双向链表的尾节点B，然后插入H。

image.png

这个NodeList的头节点的node双向链表的尾节点就是最近最少使用的节点。

附上以上图解的出处，感谢博主「借汝之光，得以光明」

版权声明：本文为CSDN博主「借汝之光，得以光明」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_44588495/java/article/details/106743802

LruCache 从命名上我们已经知道它是使用LRU 策略管理缓存的，我们通过源码来分析一下Android中LruCache 的具体实现。我们也可以根据需要定制自己的LruCache，这个看个人需求。

private final LinkedHashMap<K, V> map;

private int size;  //如果未实现sizeOf()方法，size的值为cache中entries的数量；否则size的值为所有entries的size总和

private int maxSize;  //size的最大值，与size一样也取决于sizeOf()方法是否被实现

public LruCache(int maxSize) {
    if (maxSize <= 0) {
        throw new IllegalArgumentException("maxSize <= 0");
    }
    this.maxSize = maxSize;
    this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}

我们可以看到LruCache是使用LinkedHashMap来管理缓存对象的。之所以选择LinkedHashMap，是因为它本身是有序链表，可分为插入顺序和访问顺序两种。如果是访问顺序，那put和get操作已存在的Entry时，都会把Entry移动到双向链表的表尾（其实是先删除再插入），这简直就是为LRU量身定做！既然有这么好的东西，如果不用它那就过分了吧哈哈！

接下来逐一分析三个最重要的方法：get(K key)、put(K key, V value) 和 remove(K key)。

LruCache#get(K key)

/**
 * 返回缓存对象:
 * 1.LinkedHashMap中存在key对应的缓存对象，直接返回；
 * 2.LinkedHashMap中不存在key对应的缓存对象，尝试使用create()方法创建一个缓存对象，如果创建成功直接返回；
 * 3.如果1.2都失败，返回null。
 */
public final V get(K key) {
    if (key == null) {  //key为空抛出异常
        throw new NullPointerException("key == null");
    }

    V mapValue;  //保存在map中查找出的缓存对象
    synchronized (this) {
        mapValue = map.get(key);
        if (mapValue != null) {   //成功找到缓存对象，直接返回mapValue 
            hitCount++;   //记录成功找到缓存对象的次数
            return mapValue;
        }
        missCount++;  //记录缓存对象匹配失败的次数
    }

    //调用create()方法创建value，该方法默认返回null，我们需要在子类中重写此方法
    //注意使用此方法需要考虑多线程的情况
    V createdValue = create(key);  
    if (createdValue == null) {
        return null;
    }

    synchronized (this) {
        createCount++;  //记录成功创建value的次数

        mapValue = map.put(key, createdValue);  //将创建的value放入map中
         //如果此时map中的key位置已经存在缓存对象mapValue，使用mapValue 重新覆盖createdValue
        if (mapValue != null) {  
            map.put(key, mapValue);
        } else {
            size += safeSizeOf(key, createdValue); //重新计算size值
        }
    }

    if (mapValue != null) {
        entryRemoved(false, key, createdValue, mapValue);  //释放资源
        return mapValue;
    } else {
        trimToSize(maxSize);  //调整缓存空间
        return createdValue;
    }
}

//子类可以重写此方法
protected V create(K key) {
    return null;
}

//子类可以重写此方法
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {
}

如果使用create(K key)方法时缓存中已经存在{@code key}对应的值，那么createdValue将与{@link #entryRemoved}一起释放并丢弃。在某些特定条件下会发生这种情况：当多个线程请求相同的密钥时，会导致多个createdValue值同时被创建；或者当一个线程在调用{@link #put}方法的同时，另一个线程正在为同一个key创建值。

LruCache#put(K key, V value)

public final V put(K key, V value) {
    if (key == null || value == null) {
        throw new NullPointerException("key == null || value == null");
    }

    V previous;
    synchronized (this) {
        putCount++;  //记录缓存添加成功的次数
        size += safeSizeOf(key, value);  //重新计算size值

        //previous 表示put执行之前key位置上已有的value
        previous = map.put(key, value);  
        //如果previous 不为空，则说明key位置已经存在值，所以previous 会被新的value替代
        if (previous != null) {  
            size -= safeSizeOf(key, previous);  //减掉旧值previous 占用的size值
        }
    }

    if (previous != null) {
        entryRemoved(false, key, previous, value); //释放资源
    }

    trimToSize(maxSize);
    return previous;
}

LruCache#remove(K key)

public final V remove(K key) {
    if (key == null) {
        throw new NullPointerException("key == null");
    }

    V previous;  //存储被移除的value
    synchronized (this) {
        previous = map.remove(key);
        if (previous != null) {  //如果移除成功，重新计算size值
            size -= safeSizeOf(key, previous);
        }
    }

    if (previous != null) {
        entryRemoved(false, key, previous, null);  //释放资源
    }

    return previous;
}

put(K key, V value) 和 remove(K key) 方法比较简短，注释已经很详细不再复述。