Android中使用的LruCache

LRU 是 Least Recently Used 的缩写，即“最近最少使用”，说明 LRU 缓存算法的淘汰策略是把最近最少使用的数据移除，让出内存给最新读取的数据。下面看一下 Android开发中的LruCache 。

Android.util.LruCache

这个LruCache 在 android.util 包下，是 API level 12 引入的，对于 API level 12 之前的系统可以使用 support library 中的 LruCache 。先来看看 android.util.LruCache 的源码。

首先是成员变量：

private final LinkedHashMap<K, V> map;

    /** Size of this cache in units. Not necessarily the number of elements. */

    private int size;

    private int maxSize;

    private int putCount;

    private int createCount;

    private int evictionCount;

    private int hitCount;

    private int missCount;

LruCache 内部使用一个 LinkedHashMap 作为存储容器，并对各种操作进行计次。

构造器：

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);

    }

构造器的参数maxSize 用于指定缓存的最大容量，并初始化一个 LinkedHashMap ，顺便看看这个 LinkedHashMap 的构造函数：

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {

        super(initialCapacity, loadFactor);

        init();

        this.accessOrder = accessOrder;

    }

initialCapacity 即初始容量设为 0 ，装填因子 loadFactor 设为 0.75 ， accessOrder 设为 true ，即链表中的元素按照最近最少访问到最多访问排序。这里设置的装填因子为 0.75 ，设置其它值行不行呢？在 LinkedHashMap 这个构造器中只是将 loadFactor 作为参数传给了父类构造器，该父类构造器如下：

public HashMap(int capacity, float loadFactor) {

        this(capacity);

        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {

            throw new IllegalArgumentException("Load factor: " + loadFactor);

        }

        /*

         * Note that this implementation ignores loadFactor; it always uses

         * a load factor of 3/4. This simplifies the code and generally

         * improves performance.

         */

    }

调用了HashMap 的构造器，可以看到只是对 loadFactor 进行了合法检查，除此之外没有其他调用或赋值操作， Note 中解释了，这个 loadFactor 没用，装填因子永远使用 3/4 ，也就是 0.75 。所以在构造 LinkedHashMap 时，设了装填因子也没什么用。

继续看LruCache ， resize 方法更新链表容量，调用 trimToSize 方法。

public void resize(int maxSize) {

        if (maxSize <= 0) {

            throw new IllegalArgumentException("maxSize <= 0");

        }

        synchronized (this) {

            this.maxSize = maxSize;

        }

        trimToSize(maxSize);

    }

先看get 方法， key 为空会抛异常，取出对应的 value ，若不为空则命中次数 hitCount 加 1 并 return 这个 value ，否则 missCount 加 1 。该 value 为空时继续向下执行，根据 key 尝试创建 value ，如果创建返回的 createdValue 是 null ，那就确实没有该值，若创建操作返回的 createdValue 不为 null ，则尝试把 createdValue 放回 map ，若存在旧值则返回旧值，否则返回这个 createdValue 。

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++;

        }

        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;

        }

    }

put 方法将键值对放入 map ，重新计算大小之后调用 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) {

            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;

    }

trimToSize 方法中会一直尝试删除队首元素即访问次数最少的元素，直到 size 不超过最大容量或将要删除的对象为空。

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) {

                    break;

                }

                Map.Entry<K, V> toEvict = map.eldest();

                if (toEvict == null) {

                    break;

                }

                key = toEvict.getKey();

                value = toEvict.getValue();

                map.remove(key);

                size -= safeSizeOf(key, value);

                evictionCount++;

            }

            entryRemoved(true, key, value, null);

        }

    }

android.support.v4.util.LruCache

support v4 包中的 LruCache 可以用于 API level 12 之前的系统，和 android.util 包的 LruCache 的区别是在 trimToSize 中获取将要删除元素的方法不一样：

· android.util.LruCache

Map.Entry<K, V> toEvict = map.eldest();

· android.support.v4.util.LruCache

Map.Entry<K, V> toEvict = map.entrySet().iterator().next();

LinkedHashMap 的 eldest() 方法已经被标注为 @hide ，所以使用 android.support.v4.util.LruCache 更加保险一点。

来源：简书