LruCache源码解析

LruCache是Android在3.1提供的一个最近最少使用数据缓存算法工具类，本文将梳理一下LruCache的源码。首先我们看一下Android官方文档是怎么样描述LruCache的。

A cache that holds strong references to a limited number of values. Each time a value is accessed, it is moved to the head of a queue. When a value is added to a full cache, the value at the end of that queue is evicted and may become eligible for garbage collection.

LruCache简单介绍

Cache对数量有限的Value持有强引用。每当访问一个Value的时候，它都会被移动到队列的头部。当往已满的cache中加入新内容时，在队列尾部的内容会被当作垃圾删除。这就是LruCache中LRU（最近最少使用算法）算法的实现原理。
下面先看一下，LruCache官方文档对LruCache的介绍。

If your cached values hold resources that need to be explicitly released, override entryRemoved(boolean, K, V, V).

If a cache miss should be computed on demand for the corresponding keys, override create(K). This simplifies the calling code, allowing it to assume a value will always be returned, even when there’s a cache miss.

By default, the cache size is measured in the number of entries. Override sizeOf(K, V) to size the cache in different units. For example, this cache is limited to 4MiB of bitmaps:
1
2
3
4
5
6
int cacheSize = 4 * 1024 * 1024; // 4MiB
LruCache<String, Bitmap> bitmapCache = new LruCache<String, Bitmap>(cacheSize) {
    protected int sizeOf(String key, Bitmap value) {
        return value.getByteCount();
    }
}
This class is thread-safe. Perform multiple cache operations atomically by synchronizing on the cache:
1
2
3
4
5
synchronized (cache) {
  if (cache.get(key) == null) {
      cache.put(key, value);
  }
}
This class does not allow null to be used as a key or value. A return value of null from get(K), put(K, V) or remove(K) is unambiguous: the key was not in the cache.

This class appeared in Android 3.1 (Honeycomb MR1); it’s available as part of Android’s Support Package for earlier releases.

简单解释：
1.如果缓存的数据需要明确的释放那么就需要重写entryRemoved。
2.
3.默认情况下，cach的大小是测量项目的数量。重写sizeOf以不同的单元测量cache的大小。例如：

int cacheSize = 4 * 1024 * 1024; // 4MiB
LruCache<String, Bitmap> bitmapCache = new LruCache<String, Bitmap>(cacheSize) {
    protected int sizeOf(String key, Bitmap value) {
        return value.getByteCount();
    }
}

4.LruCache 是线程安全的。因为LruCache中的方法都利用synchronized关键字进行了同步。
5.LruCache 中的key和value都不能为null，
6.LruCache 在Android3.1中出现，对于之前的发行版提供了Support包。

源码分析

构造方法

通过前面章节的介绍大家应该对于LruCache有了一个大概了解，这一章节就带大家一起分析一下LruCache的源码。
分析源码从哪里开始呢？当然是从LruCache的构建开始吧！首先我们先看看LruCache的构造函数。

/**
     * @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);
    }

这是LruCache唯一的构造方法，在注释中有一些重要的信息，如果没有override sizeOf()方法，maxSize表示的是cache中项目的数量，所以一般情况下都要
override sizeOf()方法.从构造方法中可以看到LruCache的数据是由 LinkedHashMap 存储的， LinkedHashMap 是 HashMap 的子类，它与 HashMap
相比底层使用哈希表与双向链表来保存所有元素。其基本操作与父类 HashMap 相似，它通过重写父类相关的方法，来实现自己的链接列表特性。LinkedHashMap 的主要特点就是可以排序，LinkedHashMap 定义了排序模式 accessOrder，该属性为 boolean 型变量，对于访问顺序，为 true；对于插入顺序，则为 false。一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。因此在LruCache的构造方法中初始化 LinkedHashMap 时，第三个参数就是 accessOrder 所谓的LRU算法也就是由 LinkedHashMap实现的。详情可访问极客学院了解。

get(K key)方法

get方法和put方法是LruCache中的核心方法，我们首先分析get方法。

/**
     * Returns the value for {@code key} if it exists in the cache or can be
     * created by {@code #create}. If a value was returned, it is moved to the
     * head of the queue. This returns null if a value is not cached and cannot
     * be created.
     */
    public final V get(K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }

        V mapValue;
        synchronized (this) {
            mapValue = map.get(key);
            if (mapValue != null) {
                hitCount++;
                return mapValue;
            }
            missCount++;
        }

        /*
         * Attempt to create a value. This may take a long time, and the map
         * may be different when create() returns. If a conflicting value was
         * added to the map while create() was working, we leave that value in
         * the map and release the created value.
         */

        V createdValue = create(key);
        if (createdValue == null) {
            return null;
        }

        synchronized (this) {
            createCount++;
            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;
        }
    }

首先看一下注释是怎样介绍这个方法的，如果cache中存在key对应的值或者这个值可以用create()方法创建，则return 这个值，否则return null 。如果一个值被return了，则此值被移动到队列的头部。这就是这个方法的作用。可以看到此方法通过使用 synchronized 关键字进行了同步，所以这个方法是线程安全的。大家可能有些奇怪，因为没有看到将命中的值移动到队首啊，其实这个操作是在LinkedHashMap 的 get 方法中，大家可以自行查看其源码，其主要操作就是双向链表的操作，如果数据结构基础好的话，看懂这些代码应该不是问题。

put方法

/**
   * Caches {@code value} for {@code key}. The value is moved to the head of
   * the queue.
   *
   * @return the previous value mapped by {@code key}.
   */
  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);
          if (previous != null) {
              size -= safeSizeOf(key, previous);
          }
      }

      if (previous != null) {
          entryRemoved(false, key, previous, value);
      }

      trimToSize(maxSize);
      return previous;
  }

put方法的功能是将key 和 value 插入队列，并将其移动到队头，最后return key 之前对应的value，如果之前不存在此key，则返回null。最后通过 trimToSize 方法将最近最少访问的数据移除。

trimToSize方法

/**
   * @param maxSize the maximum size of the cache before returning. May be -1
   *     to evict even 0-sized elements.
   */
  private 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) {
                  break;
              }

              // BEGIN LAYOUTLIB CHANGE
              // get the last item in the linked list.
              // This is not efficient, the goal here is to minimize the changes
              // compared to the platform version.
              Map.Entry<K, V> toEvict = null;
              for (Map.Entry<K, V> entry : map.entrySet()) {
                  toEvict = entry;
              }
              // END LAYOUTLIB CHANGE

              if (toEvict == null) {
                  break;
              }

              key = toEvict.getKey();
              value = toEvict.getValue();
              map.remove(key);
              size -= safeSizeOf(key, value);
              evictionCount++;
          }

          entryRemoved(true, key, value, null);
      }
  }

可以看到trimToSize方法比较简单，主要流程是如果当前size大于maxSize则remove掉队尾项目。

总结

1.LruCache 是通过 LinkedHashMap 构造方法的第三个参数的 accessOrder=true 实现了 LinkedHashMap 的数据排序基于访问顺序（最近访问的数据会在链表尾部），在容量溢出的时候，将链表头部的数据移除。从而，实现了 LRU 数据缓存机制。
2.LruCache 在内部的get、put、remove包括 trimToSize 都是安全的（因为都上锁了）。
3.LruCache 自身并没有释放内存，将 LinkedHashMap 的数据移除了，如果数据还在别的地方被引用了，还是有泄漏问题，还需要手动释放内存。
4.覆写 entryRemoved 方法能知道 LruCache 数据移除是是否发生了冲突，也可以去手动释放资源。
5.maxSize 和 sizeOf(K key, V value) 方法的覆写息息相关，必须相同单位。（比如 maxSize 是7MB，自定义的 sizeOf 计算每个数据大小的时候必须能算出与MB之间有联系的单位）

参考资料：
LruCache 源码解析
 LinkedHashSet 的实现原理