LruCache源码解析

LruCache是Android中的一个缓存工具类，它采用了一种最近最少使用算法，可以将一些对象进行内存缓存，当缓存满后，会优先删除近期最少使用的对象。LruCache在实际开发中是使用率非常高的一个工具类，许多著名的图片加载，网络请求等框架内部都是使用的LruCache对象进行数据缓存，因此我们有必要了解LruCache内部的工作原理。

基本使用

LruCache本身是一个泛型类，使用起来也非常简单，如果我们想要使用LruCache对象，首先要实例化一个LruCache对象，并重写它的sizeOf方法，我们以缓存Bitmap对象为例：

    int maxMemory = (int) (Runtime.getRuntime().maxMemory() / 1024);
    int maxSize = maxMemory / 8;
    LruCache<String, Bitmap> lruCache = new LruCache<String, Bitmap>(maxSize) {
        @Override
        protected int sizeOf(String key, Bitmap value) {
            return value.getRowBytes() * value.getHeight() / 1024;
        }
    };

LruCache的构造方法需要传入一个maxSize参数，这个参数代表可以缓存的最大值。而sizeOf方法用来计算要缓存的对象的大小。

如果我们想要缓存一个对象，只需要调用LruCache对象的put(K key, V value)方法即可，而当我们想要拿取一个缓存时，则需要调用get(K key)方法：

    lruCache.put(key, bitmap);
        
    Bitmap cache = lruCache.get(key);

LinkedHashMap对象

我们通过分析LruCache的源码来分析LruCache的工作原理。首先看LruCache的构造方法：

    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其实就是LruCache的核心部分，使用LruCache缓存的对象其实是存储在这个LinkedHashMap中的。

LinkedHashMap是HashMap的一个子类，与HashMap不同的是，LinkedHashMap能够记住每条记录的插入顺序。LinkedHashMap类有许多重载的构造方法，而在LruCache中使用的是LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)这个构造方法，其中最关键的就是accessOrder这个参数，它代表着LinkedhashMap中每条记录的排序规则。当accessOrder为false时，LinkedHashMap是按照插入顺序来对每条记录进行排序的，而当accessOrder为true时，LinkedHashMap则会采用每条记录的访问顺序来进行排序。

举个例子：

    Map<Integer, String> hashMap = new HashMap<>();
    hashMap.put(3, "第一条");
    hashMap.put(2, "第二条");
    hashMap.put(1, "第三条");
    System.out.println("HashMap:\n" + hashMap);

    //采用这个无参的构造方法创建LinkedHashMap时，accessOrder默认为false
    Map<Integer, String> linkedHashMap = new LinkedHashMap<>();
    linkedHashMap.put(3, "第一条");
    linkedHashMap.put(2, "第二条");
    linkedHashMap.put(1, "第三条");
    System.out.println("\nLinkedHashMap:\n" + linkedHashMap);

    Map<Integer, String> linkedHashMap2 = new LinkedHashMap<>(0, 0.75f, true);
    linkedHashMap2.put(3, "第一条");
    linkedHashMap2.put(2, "第二条");
    linkedHashMap2.put(1, "第三条");
    linkedHashMap2.get(2);//在这里访问了一下"第二条"
    System.out.println("\nLinkedHashMap2:\n" + linkedHashMap2);

输出结果：

HashMap:
{1=第三条, 2=第二条, 3=第一条}

LinkedHashMap:
{3=第一条, 2=第二条, 1=第三条}

LinkedHashMap2:
{3=第一条, 1=第三条, 2=第二条}

可以看到默认情况下LinkedHashMap是按照顺序来存储每条记录的，先插入的在前，后插入的在后，而当accessOrder为true时，最近访问的记录会被排到后面。LruCache就是根据LinkedHashMap这个特性来判断哪些缓存数据需要被优先清除的。

插入缓存

LruCache使用put方法来插入一个缓存数据，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); //将数据插入到LinkedHashMap中
            if (previous != null) {
                size -= safeSizeOf(key, previous);
            }
        }

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

        trimToSize(maxSize);
        return previous;
    }

put方法的源码非常好理解，首先盘点key和value是否为null，如果为null就直接抛出异常了。然后使用了synchronized关键字来保证线程安全。size变量代表当前已经使用的缓存的大小，使用sizeOf方法来计算本次提交的缓存数据的大小，并与size相加来更新已经使用的缓存大小。之后将本次提交的数据插入到LinkedHashMap里。

在调用LinkedHashMap的put方法时，如果LinkedHashMap中已经存在以这个"Key"为键的数据，则会用新插入的数据覆盖旧的数据，然后将旧的数据返回，返回的旧数据被保存在了previous这个变量内，如果LinkedHashMap中不存在以这个"Key"为键的数据则返回null。因此，当previous不为null时，说明有旧数据被覆盖了，我们要减去这个旧数据所占用的空间大小。

entryRemoved方法会在某个缓存数据被移除时被调用，默认情况下该方法是个空方法。我们可以根据需求来重写这个方法，在缓存对象要被清除时做一些处理。

最后调用了trimToSize方法来计算当前缓存数据的大小是否超过了缓存允许的最大值的限制，trimToSize方法的源码如下：

    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停止循环
                    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);
        }
    }

当已用缓存大小超过最大缓存时，通过map.eldest()来获取访问时间最早的那个元素，然后将它从LinkedHashMap中删除，并重新计算已用缓存的大小，如果已用缓存的大小仍然大于最大缓存大小，则进行下一次循环继续进行删除，否则打断循环。

获取缓存

LruCache对象通过get方法来获取一个缓存。get方法的源码如下：

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

        V mapValue;
        synchronized (this) {
            mapValue = map.get(key);//从LinkedHashMap中拿取缓存对象
            if (mapValue != null) {
                hitCount++;
                return mapValue;
            }
            missCount++;
        }

        V createdValue = create(key);//通过create方法试图创建一个对象
        if (createdValue == null) {
            return null;
        }

        //以下代码与put方法类似
        synchronized (this) {
            createCount++;
            mapValue = map.put(key, createdValue);

            if (mapValue != null) {
                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方法的代码略长，但理解起来其实非常简单。依旧是宣判断key是否为null。之后通过map.get(key)来从LinkedHashMap中获取缓存的数据。如果获取的数据不为null，则直接将其返回，并且LinkedHashMap会自动将这个缓存对象排列到最后面。

如果map.get(key)获取的值为空，则会试图调用create方法来创建一个对象，create默认情况下直接返回null。我们可以根据需求重写create方法来实现自己想要的结果。如果create成功的创建了一个对象，LruCache则会将这个对象添加到LinkedHashMap中，并返回该对象。

remove方法

remove方法用来移除一个缓存对象，源码如下：

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

在理解了put和get方法后，remove的源码读起来就毫无压力了。通过map.remove(key)来直接从LinkedHashMap中移除该对象，并更新size的值，然后调用entryRemoved方法进行处理。代码很简单，就不再多说了。