一个专注音视频领域的小圈子

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 中,默认是最近最少使用的元素位于链表的头部,而最近使用最多的元素则是位于链表的尾部。这样一来,从头到尾的一个渐变过程也就是一个元素使用最少到多的过程了。

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

下面就分别介绍其getput操作。

LruCache 的 get 操作

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

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

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

而重点就在于LinkedHashMapget方法了。

	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 的getput操作中,都有用到的synchronized锁操作。

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

参考

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

原创文章,转载请注明来源:    Android LruCache实现分析