Android LruCache实现分析

LruCache 是安卓开发中常用到的缓存技术，LRU 的全名是 Least Recently Used，表示最近最少使用算法，也就是说当内存快到达阈值时，若某个对象最近很少使用的，那么它就会被回收掉以释放内存。

使用

LruCache 的使用方法大致如下 ：

// LruCache 的声明初始化
        int maxMemory = (int) (Runtime.getRuntime().maxMemory() / 1024);
        // 指定缓存的内存大小，一般为当前进程可用内存的 1/8 即可
        int cacheSize = maxMemory / 8 ;
        LruCache<String,Bitmap> cache = new LruCache<String,Bitmap>(cacheSize){

            // 如何计算缓存的资源的内存大小
            @Override
            protected int sizeOf(String key, Bitmap value) {
                return value.getRowBytes() * value.getHeight() / 1024 ;
            }
            // 当缓存对象被回收时执行的回调方法，以便释放一些资源之类的，默认为空
            @Override
            protected void entryRemoved(boolean evicted, String key, Bitmap oldValue, Bitmap newValue) {
                super.entryRemoved(evicted, key, oldValue, newValue);
            }
        };
        // LruCache 添加缓存对象
        cache.put(key,bitmap) ;
        // LruCache 获取缓存对象
        cache.get(key);

LruCache 的声明和使用都比较简单，在它的内部就已经帮我们完成了缓存对象的移除和添加，而我们无需过多的考虑对象的释放问题。

原理分析

既然要缓存对象，必然要有个容器，LruCache 使用的是 LinkedHashMap，以强引用方式存储外界的缓存对象。

LinkedHashMap是一个双向的环形链表，链表中的每个节点都有指向前一个元素和后一个元素的引用。使用链表的好处就在于它的删除和添加操作更加的方便快捷。

而 LRU 的最近最少使用算法思想就体现在LinkedHashMap的元素顺序中了。

LinkedHashMap中的顺序当然是从头到尾的，而一个元素最近的使用情况当然也是从头到尾的一个渐变了。在 LruCache 中，默认是最近最少使用的元素位于链表的头部，而最近使用最多的元素则是位于链表的尾部。这样一来，从头到尾的一个渐变过程也就是一个元素使用最少到多的过程了。

当我们在进行每个get和put操作时，LinkedHashMap中的每个元素使用情况就要发生变化了，毕竟缓存容量是有限的，一些不幸的元素可能就因此而被垃圾回收了，以此来体现 LRU 的最近最少使用算法。

下面就分别介绍其get和put操作。

LruCache 的 get 操作

从 LruCache 中取出一个元素，显然，这个结果是可能为 null 的。

LruCache 使用get操作很简单，有就取出来，没有就返回个 null 。

		V mapValue;
        synchronized (this) {
            mapValue = map.get(key);
            if (mapValue != null) {
                hitCount++;
                return mapValue;
            }
            missCount++;
        }

而重点就在于LinkedHashMap的get方法了。

	int hash = Collections.secondaryHash(key); // 计算 key 的 hash 值
        HashMapEntry<K, V>[] tab = table;
        for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)]; e != null; e = e.next) {
            K eKey = e.key;
            if (eKey == key || (e.hash == hash && key.equals(eKey))) {
                if (accessOrder)
                    makeTail((LinkedEntry<K, V>) e);
                return e.value;
            }
        }

LinkedHashMap的节点类是LinkedEntry，它继承自HashMapEntry，在其继承之上多了指向前后元素的引用。

所以，从上述代码可以看出，无非就是一个遍历，找到 key对应的元素就取出来，并且多了一个操作makeTail。

makeTail的操作又是干什么的呢？它可谓是实现最近最少算法的精髓了。

 private void makeTail(LinkedEntry<K, V> e) {
        // Unlink e 将节点 e 的前节点和后节点进行连接，而将它自己给释放出来
        e.prv.nxt = e.nxt;
        e.nxt.prv = e.prv;

        // Relink e as tail 将节点 e 连接到链表的尾部
        LinkedEntry<K, V> header = this.header;
        LinkedEntry<K, V> oldTail = header.prv;
        e.nxt = header;
        e.prv = oldTail;
        oldTail.nxt = header.prv = e;
        modCount++;
    }

makeTail操作，将一个get的节点，从原本它在链表中的位置移到了整个链表中的尾部，使它的前节点是上一任的尾节点，而后节点则是头结点。

而在上面提到过，LinkedHashMap链表中元素的顺序正是完美的体现了最少最近算法的思想。

get得到的元素必然是最近使用最多的了，每次 get之后都将它移动到链表的尾部，也正是最近最少算法的体现了。

LruCache 的 put 操作

put操作则是向LinkedHashMap中放入一个元素，而缓存的容量又是有限的，这么一来，在有限的情况下，就会有元素被垃圾回收了。

	  V previous;
        synchronized (this) {
            putCount++;
            size += safeSizeOf(key, value);
            previous = map.put(key, value); // 若存在 key 相同的元素，则返回之前的，否则返回 null
            if (previous != null) {    // 存在 key 相同的元素
                size -= safeSizeOf(key, previous);
            }
        }
        // 移除最近最少使用的元素
		trimToSize(maxSize);

当进行put操作时，若放入一个 key 存在的元素，则返回已经存在的对应的值。

同时，在每次put操作之后，都要进行容量的清除工作。

public void trimToSize(int maxSize) {
        while (true) { // 死循环
            K key;
            V value;
            synchronized (this) {
                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);
        }
    }

trimToSize的操作是一个死循环的操作，当size小于maxSize时，直接返回，否则从LinkedHashMap中移除最近最少使用的元素，也就是头节点后的元素。

以上就大致实现了 LRU 的最少最近算法。

同步锁相关操作

在 LruCache 的get和put操作中，都有用到的synchronized锁操作。

这是保证线程安全，因为在get和put方法中进行的都是复合操作，在并发条件下使用缓存时很容易出现脏数据，加上synchronized标识，则保证了操作的原子性，使得成为线程安全的操作。

参考

1、https://github.com/LittleFriendsGroup/AndroidSdkSourceAnalysis/blob/master/article/LruCache%E6%BA%90%E7%A0%81%E8%A7%A3%E6%9E%90.md