理解 LruCache 机制

本人只是 Android 小菜一个，写技术文档只是为了总结自己在最近学习到的知识，从来不敢为人师，如果里面有些不正确的地方请大家尽情指出，谢谢！

1. 概述

由于 Android 为每个进程分配的可用内存空间都是有限的，如果进程使用的内存超过了所分配的限制就会出现内存溢出问题。同时，如果应用每使用一个资源都需要从本地或网络加载，这无疑会影响应用的性能，为了既能保证应用性能又能避免内存溢出，就出现 内存缓存技术 。

所谓 内存缓存技术 指的是把一些资源缓存在内存中，如果需要加载资源，首先到内存中去寻找，寻找到的话就直接使用，否则去本地或者网络去寻找。其中最重要的是 内存缓存技术 要有一个合适的 缓存策略 ,即根据什么策略把缓存中的资源删除，以保证缓存空间始终在一个合理的范围内。

LruCache 是 Android 提供的一个标准的基于 LRU，最近最少使用 算法的缓存技术，它的使用方法已经在其他博文里简单介绍过了，这里主要介绍它的实现机制。

2. LruChche 实现原理

LRU 的全称是 Least Recently Used，最近最少使用 ， LruCache 的实现原理就是在其内部维护一个队列，内部元素按照最近使用时间进行排序，队首是最近最常使用的元素，队尾是最近最少使用的元素，当缓存中元素达到最大数量后，把最近最少使用的元素即队尾元素从缓存队列中移除，从而保证缓存始终在一个合理内存范围内。

下图简单演示 LruCache 的过程：

1. 每次新入队的元素总是位于队首；
2. 队尾元素是最久没有使用过的元素；
3. 当队列中的元素被再次使用后，就会把该元素重新插入到队首。

LruCache 中使用 LinkedHashMap 来保存元素，而 LinkedHashMap 内部使用双向链表来实现这样的一个 LRU 队列，其具体实现在这里就不详细描述了，大家只要了解这点就可以了。

3. LruCache 关键实现

内存缓存技术 中最关键的实现主要包含三部分：

• 如何把元素加入缓存
• 如何从缓存中获取元素
• 如何在缓存满时删除元素

3.1 LruCache 的初始化

在详细讲解 LruCache 的三个关键实现部分前，首先要知道 LruCache 的初始化。 首先看下是如何在代码里使用 LruCache 的：

int maxMemory = (int) Runtime.getRuntime().maxMemory();
    LruCache<String, Bitmap> mCache = new LruCache<String, Bitmap>(maxMemory / 4) {
        @Override
        protected int sizeOf(String key, Bitmap value) {
            return value.getByteCount();
        }
    };
复制代码

在这段示例代码里，创建了一个 LruCache 示例并重写了 sizeOf 方法。重写 sizeOf 方法是因为它会被用来判断缓存的当前大小是否已经达到了预定义的缓存大小，如果超过就需要从中移除最久没有使用的元素。默认情况下 sizeOf 返回的时候元素个数，所以如果在创建 LruCache 时指定的缓存中的元素个数而非内存空间就可以不重新 sizeOf 方法。

现在来看在创建 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);
    }
复制代码

从构造函数里发现，除了根据传入的参数确定了缓存的最大内存空间(也可能是元素数量)外，还定义了一个 LinkedHashMap 并把其中的第三个参数设置为 true ， LinkedHashMap 的构造函数如下：

/**
     * Constructs an empty <tt>LinkedHashMap</tt> instance with the
     * specified initial capacity, load factor and ordering mode.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @param  accessOrder     the ordering mode - <tt>true</tt> for
     *         access-order, <tt>false</tt> for insertion-order
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
复制代码

其中，参数分别是 初始容量, 负载因子和 排序 方式 ，如果 accessOrder 被设置为 true 就表示是按照访顺序进行排序的，这也就保证了 LruCache 中的原生是按照访问顺序排序的。

所以在 LruCache 的初始化过程中，一方面确定了缓存的最大空间，另一方面利用 LinkedHashMap 实现了 LRU 队列。

3.2 LruCache 缓存元素

要使用 LruCache ，首先需要把需要缓存的资源加入到 LruCache 缓存空间，在 LruCache 实现这一功能的是 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);
            }
        }
        // 如果是更新元素，需要发出通知，默认 entryRemoved 没有实现。
        if (previous != null) {
            entryRemoved(false, key, previous, value);
        }
        // 检查缓存大小是否达到限制，如果达到需要移除最久没使用的元素。
        trimToSize(maxSize);
        return previous;
    }
复制代码

put 方法整体逻辑比较简单，就是把新元素放在队首，更新当前缓存大小，并使用 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 的逻辑也很简单明了，在缓存队列中找到最近最久没有使用的元素，把它从队列中移除，直到缓存大小满足限制。由于最近最久没有使用的元素一直位于队尾，所以只要找到队尾元素并把它移除即可。

3.3 LruCache 取元素

缓存元素的最终目的是为了方便后续能从缓存中更快地获取需要元素， 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.
         */
        // 如果找不到元素就调用 create 去创建一个元素，默认 create 返回 null.
        V createdValue = create(key);
        if (createdValue == null) {
            return null;
        }

        synchronized (this) {
            createCount++;
            mapValue = map.put(key, createdValue);
            // 新创建的元素和队列中已存在元素冲突，这个已存在元素是在 create的过程中新加入队列的。
            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;
        }
    }
复制代码

get 方法的逻辑也是很简洁明了的，就是直接从缓存队列中获取元素，如果查找到就返回并更新元素位置到队首，如果查不到就自己创建一个加入队列，但考虑到多线程的情况，加入队列是需要考虑冲突情况。

3.4 LruCache 移除元素

虽然 LruCache 可以在缓存空间达到限制是自动把最近最久没使用的元素从队列中移除，但也可以主动去移除元素，使用的方法就是 remove ，其代码如下：

/**
     * Removes the entry for {@code key} if it exists.
     *
     * @return the previous value mapped by {@code key}.
     */
    public final V remove(K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }

        V previous;
        synchronized (this) {
            // 找到元素后移除，并更新缓存大小。
            previous = map.remove(key);
            if (previous != null) {
                size -= safeSizeOf(key, previous);
            }
        }

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

        return previous;
    }
复制代码

remove 的逻辑更加简单，到缓存队列中找到元素，移除，并更新缓存大小即可。