LruCache源码解析

什么是 LruCache

LruCache (此类在android-support-v4的包中提供) 。这个类非常适合用来缓存图片，它的主要算法原理是把最近使用的对象用强引用存储在 LinkedHashMap 中，并且把最近最少使用的对象在缓存值达到预设定值之前从内存中移除。

源码解读

先上源码「Lrucache 源码( Google Git )」。
Android 提供了 LruCache 类，我们来看看源码是怎么实现的。

构造器

private final LinkedHashMap<K, V> map;
    /** Size of this cache in units. Not necessarily the number of elements. */
    private int size; //map大小
    private int maxSize;//设定的最大容量
    private int putCount;//插入计数
    private int createCount;//新建计数
    private int evictionCount;//回收计数
    private int hitCount;//命中计数
    private int missCount;//未命中计数
    /**
     * @param maxSize for caches that do not override {@link #sizeOf}, this is
     *     the maximum number of entries in the cache. For all other caches,
     *     this is the maximum sum of the sizes of the entries in this cache.
     */
     //构造器
    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);
    }

从上面代码可以看出，类中实例化了一个「LinkedHashMap」对象，没错，「LruCache」就是借助「LinkedHashMap」来实现「LRU算法」的。
再看构造器中，非常简单，先做了一个非空判断，然后给「maxSize」赋值，初始化 map。

「LinkedHashMap」有三个参数：

参数	解释	作用
initialCapacity	容量	0
loadFactor	装载因子	0.75f
accessOrder	排序规则	true：访问排序 false: 默认排序

当「LinkedHashMap」排序规则为访问排序时，在每次调用 get() 方法获取集合中的值时，会将被访问的键值放到链表的尾部，「LruCache」正是利用「LinkedHashMap」的访问排序，将链表头部的对象（不常用的对象）移除，来实现最近最少访问的算法的。

put方法

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); //加上该键值的大小
            previous = map.put(key, value); //插入新键值，key 已存在则覆盖并返回旧值，反之为空
            if (previous != null) {//之前已经插入过相同的key
                size -= safeSizeOf(key, previous);//那么减去该entry的容量，因为发生覆盖
            }
        }
        if (previous != null) {
            entryRemoved(false, key, previous, value);//这个方法默认空实现
        }
        trimToSize(maxSize);//若容量超过maxsize，将会删除最近很少访问的entry
        return previous;
    }

put 方法实际上就是调用「LinkedHashMap」的 put 方法，将新的对象插入其中，注意，这里先对传入的键值做了非空判断，说明「LruCache」是不允许空键和空值的。

trimToSize 方法：

public void trimToSize(int maxSize) {
       while (true) {//不断删除linkedHashMap头部entry，也就是最近最少访问的条目，直到size小于最大容量
           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<K, V> toEvict = map.entrySet().iterator().next();//指向链表头
               key = toEvict.getKey();
               value = toEvict.getValue();
               map.remove(key);//删除最少访问的entry
               size -= safeSizeOf(key, value);
               evictionCount++;
           }
           entryRemoved(true, key, value, null);
       }
   }

该方法维持了一个不断循环的代码，删除位于链表头部的数据，直至 map 的大小小于 maxSize 才跳出循环。

get 方法

public final V get(K key) {
        if (key == null) {//不允许空键
            throw new NullPointerException("key == null");
        }
        V mapValue;
        synchronized (this) {//线程安全
            mapValue = map.get(key);//调用LinkedHashMap的get方法
            if (mapValue != null) {
                hitCount++;//命中次数加1
                return mapValue;//返回value
            }
            missCount++;//未命中
        }

        V createdValue = create(key);//默认返回为false
        if (createdValue == null) {
            return null;
        }
        synchronized (this) {
            createCount++;//如果创建成功，那么create次数加1
            mapValue = map.put(key, createdValue);//放到哈希表中
            if (mapValue != null) {
                // There was a conflict so undo that last put
                map.put(key, mapValue);
            } else {
                size += safeSizeOf(key, createdValue);
            }
        }
        if (mapValue != null) {
            entryRemoved(false, key, createdValue, mapValue);
            return mapValue;
        } else {
            trimToSize(maxSize);
            return createdValue;
        }
    }

可以注意到源码中如果没有找到 key 对应的 value ，会继续调用 create 方法 ，尝试创建新的键值， 这个方法默认是返回 null ， 需要开发根据需求自行重写这个方法。

remove 方法

public final V remove(K key) {
      if (key == null) {
          throw new NullPointerException("key == null");
      }
      V previous;
      synchronized (this) {
          previous = map.remove(key);//调用LinkedHashMap的remove方法
          if (previous != null) {
              size -= safeSizeOf(key, previous);
          }
      }
      if (previous != null) {
          entryRemoved(false, key, previous, null);
      }
      return previous;//返回value
  }

也可以手动删除其中的键值对。

总结

• LruCache封装了LinkedHashMap，提供了LRU缓存的功能

• LruCache通过trimToSize方法自动删除最近最少访问的键值对

• LruCache不允许空键值

• LruCache线程安全

• 继承LruCache时，必须要复写sizeof方法，用于计算每个条目的大小