剖析LruCache

  提到Android的缓存策略任何一个Android开发人员都能随口说出LruCache，利用最新最少使用(Least Recently Used)的原则进行缓存,可LRU到底是怎么实现的呢？

LruCache简介

  LruCache是个泛型类，主要算法原理是把最近使用的对象用强引用（即我们平常使用的对象引用方式）存储在 LinkedHashMap 中。当缓存满时，把最近最少使用的对象从内存中移除，并提供了get和put方法来完成缓存的获取和添加操作。

实现原理

LruCache内部维护的是一个LinkedHashMap，最近最少的算法判断逻辑都是由LinkedHashMap来实现，如果对LinkedHashMap原理不了解的童鞋，可以先了解下LinkedHashMap的原理分析这篇文章。

初始化

private final LinkedHashMap<K, V> map;

    /** Size of this cache in units. Not necessarily the number of elements. */
    private int size;    //当前cache的大小
    private int maxSize; //cache最大大小

    private int putCount;       //put的次数
    private int createCount;    //create的次数
    private int evictionCount;  //回收的次数
    private int hitCount;       //命中的次数
    private int missCount;      //未命中次数

    /**
     * @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;
        //将LinkedHashMap的accessOrder设置为true来实现LRU
        this.map = new LinkedHashMap<K, V>(0, 0.75f, true);  
    }

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);  //size加上预put对象的大小
            previous = map.put(key, value);
            if (previous != null) {
                //如果之前存在键为key的对象，则size应该减去原来对象的大小
                size -= safeSizeOf(key, previous);
            }
        }

        if (previous != null) {
            entryRemoved(false, key, previous, value);
        }
        //每次新加入对象都需要调用trimToSize方法看是否需要回收
        trimToSize(maxSize);
        return previous;
    }

由上面的代码可以看出来，首先把size增加，然后判断是否以前已经有元素，如果有，就更新当前的size,并且调用entryRemoved方法,entryRemoved是一个空实现，如果我们使用LruCache的时候需要掌握元素移除的信息，可以重写这个方法。最后就会调用trimToSize，来调整集合中的内容。

trimToSize 方法

/**
     * @param maxSize the maximum size of the cache before returning. May be -1
     *     to evict even 0-sized elements.
     * 此方法根据maxSize来调整内存cache的大小，如果maxSize传入-1，则清空缓存中的所有对象
     */
    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!");
                }
                //如果当前size小于maxSize或者map没有任何对象,则结束循环
                if (size <= maxSize || map.isEmpty()) {
                    break;
                }
                //移除链表头部的元素，并进入下一次循环
                Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
                key = toEvict.getKey();
                value = toEvict.getValue();
                map.remove(key);
                size -= safeSizeOf(key, value);
                evictionCount++;  //回收次数+1
            }

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

这个方法是一个无限循环，跳出循环的条件是，size < maxSize或者 map 为空。主要的功能是判断当前容量时候已经超出最大的容量，如果超出了maxSize的话，就会循环移除map中的第一个元素，直到达到跳出循环的条件。由上面的分析知道，map中的第一个元素就是最近最少使用的那个元素。

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.
     * 通过key获取相应的item，或者创建返回相应的item。相应的item会移动到队列的尾部，
     * 如果item的value没有被cache或者不能被创建，则返回null。
     */
    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) {
                //mapValue不为空表示命中，hitCount+1并返回mapValue对象
                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方法返回null,并没有实现创建对象的方法
         * 如果需要事项创建对象的方法可以重写create方法。因为图片缓存时内存缓存没有命中会去
         * 文件缓存中去取或者从网络下载，所以并不需要创建。
         */
        V createdValue = create(key);
        if (createdValue == null) {
            return null;
        }
        //假如创建了新的对象，则继续往下执行
        synchronized (this) {
            createCount++;  
            //将createdValue加入到map中，并且将原来键为key的对象保存到mapValue
            mapValue = map.put(key, createdValue);   
            if (mapValue != null) {
                // There was a conflict so undo that last put
                //如果mapValue不为空，则撤销上一步的put操作。
                map.put(key, mapValue);
            } else {
                //加入新创建的对象之后需要重新计算size大小
                size += safeSizeOf(key, createdValue);
            }
        }

        if (mapValue != null) {
            entryRemoved(false, key, createdValue, mapValue);
            return mapValue;
        } else {
            //每次新加入对象都需要调用trimToSize方法看是否需要回收
            trimToSize(maxSize);
            return createdValue;
        }
    }

这个方法就先通过key来获取value,如果能获取到就就直接返回，获取不到的话，就调用create()方法创建一个，事实上，如果我们不重写这个create方法的话是return null的，所以整个流程就是获取得到就直接返回，获取不到就返回null。

不要以为LruCache是多么复杂的一个算法，看过之后是不是感觉也就那么回事？^-