LruCache源码分析

LruCache的原理

LruCache主要靠LinkedHashMap的一个按访问排序的特性实现的，LinkedHashMap在构造时可传入accessOrder参数，为true时，LinkedHashMap在每次get方法时，会将获取到的当前节点移至末尾，从而实现LRU的思想。

LruCache源码分析

1、构造函数

/** 唯一的构造函数，需要传入缓存的最大值 */
public LruCache(int maxSize) {
   if (maxSize <= 0) {
      throw new IllegalArgumentException("maxSize <= 0");
   }
   this.maxSize = maxSize;
   /** 初始化LinkedHashMap
   *  第一个参数：初始容量，传0的话HashMap默认初始容量为16
   *  第二个参数：负载因子，0.75f,表示LinkedHashMap在当前容量的75%已填充的情况下扩容
   *  第三个参数，accessOrder,为true时，LinkedHashMap的数据按访问顺序排序，为flase时，按插入顺序排序
   *  正是因为LinkedHashMap这数据排序的特性，LruCache很轻易实现了LRU算法的缓存*/
     this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}

2、get方法

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

        V mapValue;
        /** 线程同步，get,put,remove、trimToSize方法都有实现线程同步*/
        synchronized (this) {
            /** 从LinkedHashMap中获取key所对应的value,
             *  LinkedHashMap的get方法，如果获取到value不为null时，在accessOrder=true时
             *  会把<key,value>对应的节点移至链表的结尾 */
            mapValue = map.get(key);
            if (mapValue != null) {
                /** 如果mapValue不为空，命中成功次数+1*/
                hitCount++;
                /** 返回mapValue*/
                return mapValue;
            }
            /** 如果mapValue为空，命中失败次数+1*/
            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.
         */

        /** 当key所获取的value为空时，会调用create方法自定义创建value值，该方法需要重写，不然默认返回空*/
        V createdValue = create(key);
        if (createdValue == null) {
            return null;
        }

        synchronized (this) {
            /** 调用create方法次数+1*/
            createCount++;
            /** 把createValue存放进LinkedHashMap*/
            mapValue = map.put(key, createdValue);

            /** 如果mapValue不为空，则发生冲突，这里为什么会发生冲突，是因为当我们调用create方法（这里没有上锁）创建
             * createValue时，可能需要很长时间，当调用LruCache的数据量很大时，可能之前的key对所应的位置已经有值，那么
             * 就发生冲突了*/
            if (mapValue != null) {
                /** 发生冲突，则把旧值重新放进LinkedHashMap中，mapValue是旧值，createdValue是新值*/
                map.put(key, mapValue);
            } else {
                /** 没有发生冲突，则计算当前缓存的容量大小*/
                size += safeSizeOf(key, createdValue);
            }
        }

        if (mapValue != null) {
            /** entryRemoved的作用主要是在数据被回收了、被删除或者被覆盖的时候回调
             * 因为刚才发生冲突了，产生数据被覆盖的情况，因为调用entryRemoved方法*/
            entryRemoved(false, key, createdValue, mapValue);
            return mapValue;
        } else {
            /** 没有发生冲突，新数据添加到缓存中，因此调用trimToSize方法判断是否容量不足需要删除最近最少使用的数据*/
            trimToSize(maxSize);
            return createdValue;
        }
    }

注释已经把整个方法的逻辑都说得很清楚，其实get方法最关键的一行是：

  mapValue = map.get(key);

调用的是LinkedHashMap的get方法

    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            /** 如果是按访问顺序排序，则将当前节点移至链表的末尾 */
            afterNodeAccess(e);
        return e.value;
    }

    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMapEntry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMapEntry<K,V> p =
                (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

可以看见一开始构造函数初始化LinkedHashMap传入的accessOrder为true时起作用了，当accessOrder为true时会将获取到的非空节点移至末尾，具体操作由afterNodeAccess方法实现，afterNodeAccess方法的逻辑简单画个图就能明白是将双向链表的其中一个节点移至末尾。

3、put方法,trimToSize方法

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

        /** 旧值 */
        V previous;
        synchronized (this) {
            /** put次数+1 */
            putCount++;
            /** 计算当前缓存的容量大小 */
            size += safeSizeOf(key, value);
            /** 存储新的value值，如果有旧值，则返回 */
            previous = map.put(key, value);
            if (previous != null) {
                /** 因为旧值被覆盖，所以缓存容量大小要减去旧值所的空间 */
                size -= safeSizeOf(key, previous);
            }
        }

        if (previous != null) {
            /** 发生了数据被覆盖的情况，回调entryRemoved方法 */
            entryRemoved(false, key, previous, value);
        }

        /** 重整缓存空间 */
        trimToSize(maxSize);
        /** put方法所返回的值是被覆盖的旧值或者是null */
        return previous;
    }

    /** 根据传入参数调整缓存空间 */
    private void trimToSize(int maxSize) {
        /** 死循环，只有在size <= maxSize即当前容量大小小于最大值时，或者没有可删除的数据时跳出循环 */
        while (true) {
            K key;
            V value;
            synchronized (this) {
                /** 当前容量大小<0，或者map为空但容量大小等于0时，抛出异常 */
                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();
                /** 从LinkedHashMap中移除 */
                map.remove(key);
                /** 当前容量大小减去移除数据所占的空间 */
                size -= safeSizeOf(key, value);
                /** 移除的数据+1 */
                evictionCount++;
            }

            /** 因为发生数据被回收了，回调entryRemoved方法 */
            entryRemoved(true, key, value, null);
        }
    }

每次put操作都会进行trimToSize方法重新整理缓存空间，trimToSize方法主要是对缓存空间不足了，不断移除LinkedHashMap内部链表的头部节点，直到size < maxSize。

4、sizeOf方法

一般都要覆盖该方法，该方法主要是计算当前数据所占的空间大小，如果不覆盖，则每存一个数据，则占的空间是1。

    protected int sizeOf(K key, V value) {
        return 1;
    }

5、完整的源码注释文件

源码注释文件

总结

1、LruCache内部数据存储结构是LinkedHashMap，依赖LinkedHashMap按访问顺序排序数据的特性实现最近最少使用算法的缓存策略。
2、LinkedHashMap是一个双向链表，表头是最近最少未使用的数据，表尾是最近使用过的数据，因此LruCache调用trimToSize方法是移除的数据是表头的数据。
3、LruCache是线程安全的，get,put,remove、trimToSize方法都有同步锁。