LruCache 源码解析

LruCache 概要

LRU (Least Recently Used) 即最近最少使用算法。而LruCache就是基于该算法实现的,在缓存空间使用完的情况下,最久没使用的对象会被清除出缓存中。

最经典的场景就是使用LruCache做图片内存缓存,以此减少网络的请求,用户流量的消耗从而提升用户的体验。

使用案例:

public class BitmapLruCache extends LruCache<String, Bitmap> {
    //设置缓存大小,建议当前应用可用最大内存的八分之一 即(int)(Runtime.getRuntime().maxMemory() / 1024 / 8)
    public BitmapLruCache(int size) {
        super(size);
    }

    //计算当前节点的内存大小 这个方法需要重写 不然返回1
    @Override
    protected int sizeOf(String key, Bitmap value) {
        return value.getByteCount() / 1024;
    }

    //当节点移除时该方法会回调,可根据需求来决定是否重写该方法
    @Override
    protected void entryRemoved(boolean evicted, String key, Bitmap oldValue, Bitmap
            newValue) {
        super.entryRemoved(evicted, key, oldValue, newValue);
    }
}

往缓存中放一张图片:

mLruCache.put(name, bitmap);

获取一张图片:

mLruCache.get(name);

删除一张图片:

mLruCache.remove(name);

LruCache 源码

LruCache源码传送门

成员变量

  //Lru算法实际是通过LinkedHashMap实现
  private final LinkedHashMap map;
  /**
   * 缓存大小的单位。不规定元素的数量。
   */
  // 已经存储的数据大小
  private int size;
  // 最大存储大小
  private int maxSize;
  // 调用put的次数
  private int putCount;
  // 调用create的次数
  private int createCount;
  // 收回的次数 (如果出现)
  private int evictionCount;
  // 命中的次数(取出数据的成功次数)
  private int hitCount;
  // 丢失的次数(取出数据的丢失次数)
  private int missCount;

LruCache的唯一构造方法

/**
 * LruCache的构造方法:需要传入最大缓存个数
 */
public LruCache(int maxSize) {
    ...
    this.maxSize = maxSize;
    /*
     * 初始化LinkedHashMap
     * 第一个参数:initialCapacity,初始大小
     * 第二个参数:loadFactor,负载因子=0.75f
     * 第三个参数:accessOrder=true,基于访问顺序;accessOrder=false,基于插入顺序
     */
    this.map = new LinkedHashMap(0, 0.75f, true);
}

关键在于初始化LinkedHashMap时的第三个参数accessOrder=true,这样的话LinkedHashMap数据排序时就会基于数据的访问顺序,是LruCache的核心工作原理。

主要方法

LruCache.get(K key)

/**
 * 根据 key 查询缓存,如果存在于缓存或者被 create 方法创建了。
 * 如果值返回了,那么它将被移动到双向循环链表的的尾部。
 * 如果如果没有缓存的值,则返回 null。
 */
public final V get(K key) {
    ...  
    V mapValue;
    synchronized (this) {
        // 关键点:LinkedHashMap每次get都会基于访问顺序来重整数据顺序
        mapValue = map.get(key);
        // 计算 命中次数
        if (mapValue != null) {
            hitCount++;
            return mapValue;
        }
        // 计算 丢失次数
        missCount++;
    }
    /*
     * 官方解释:
     * 尝试创建一个值,这可能需要很长时间,并且Map可能在create()返回的值时有所不同。如果在create()执行的时
     * 候,一个冲突的值被添加到Map,我们在Map中删除这个值,释放被创造的值。
     */
    V createdValue = create(key);
    if (createdValue == null) {
        return null;
    }

    /*
     * 正常情况走不到这里(不覆写create方法走不到下面)
     * 走到这里的话 说明 实现了自定义的 create(K key) 逻辑
     * 因为默认的 create(K key) 逻辑为null
     */
    synchronized (this) {
        // 记录 create 的次数
        createCount++;
        // 将自定义create创建的值,放入LinkedHashMap中,如果key已经存在,会返回 之前相同key 的值
        mapValue = map.put(key, createdValue);
        // 如果之前存在相同key的value,即有冲突。
        if (mapValue != null) {
            /*
             * 有冲突
             * 所以 撤销 刚才的 操作
             * 将 之前相同key 的值 重新放回去
             */
            map.put(key, mapValue);
        } else {
            // 拿到键值对,计算出在容量中的相对长度,然后加上
            size += safeSizeOf(key, createdValue);
        }
    }
    // 如果上面 判断出了 将要放入的值发生冲突
    if (mapValue != null) {
        /*
         * 刚才create的值被删除了,原来的 之前相同key 的值被重新添加回去了
         * 告诉 自定义 的 entryRemoved 方法
         */
        entryRemoved(false, key, createdValue, mapValue);
        return mapValue;
    } else {
        // 上面 进行了 size += 操作 所以这里要重整长度
        trimToSize(maxSize);
        return createdValue;
    }
}

因为LinkedHashMapaccessOrder=true,所以当我们调用它的get方法时就可以实现LRU的缓存策略,

LruCache.get(K key, V value)

public synchronized final V put(K key, V value) {
    if (key == null || value == null) {
        throw new NullPointerException("key == null || value == null");
    }
    putCount++;
    // 拿到键值对,计算出在容量中的相对长度,然后加上
    size += safeSizeOf(key, value);
    V previous = map.put(key, value);
    //如果map中已经有该key,则恢复size的值
    if (previous != null) {
        size -= safeSizeOf(key, previous);
    }
    //插入后,判断是否超出maxSize,若超过则进行裁剪
    trimToSize(maxSize);
    return previous;
}

每次经过map.put(key, value)不管是否超过设定的缓存容量,都会确实地将值放入LinkedHashMap,然后再临近结束的时候通过trimToSize进行判断size是否大于maxSize然后再进行最近最少访问数据的移除。

LruCache.trimToSize(int maxSize)

/*
  * 从头部开始移除数据直至满足设置的maxSize为止
  * maxSize为-1则移除所有数据
  */
public void trimToSize(int maxSize) {
    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!");
            }

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

总结

  • LruCache是通过LinkedHashMap构造方法的第三个参数accessOrder=true实现的LRU数据缓存机制。
  • LruCache中的getputremovetrimToSize通过上锁实现线程安全
  • LruCache 自身并没有释放内存,将 LinkedHashMap 的数据移除了,如果数据还在别的地方被引用了,还是有泄漏问题,还需要手动释放内存。
  • maxSizesizeOf(K key, V value) 方法的覆写息息相关,必须相同单位。( 比如 maxSize 是7MB,自定义的 sizeOf 计算每个数据大小的时候必须能算出与MB之间有联系的单位 )
  • 覆写 entryRemoved 方法能知道 LruCache 数据移除是是否发生了冲突,也可以去手动释放资源。

版权声明:

本文标题:LruCache 源码解析

作者:Rabtman

原始链接:https://rabtman.com/2017/04/11/lrucache_analysis/

本文采用署名-非商业性使用-禁止演绎4.0进行许可。

非商业转载请保留以上信息。商业转载请联系作者本人。