概述
Android开发艺术探索上并没有对LruCache的实现方法以及原理作出介绍,我觉得有必要去了解一下LruCache的具体实现,因此记录一下学习过程。
源码分析
首先来看LruCache的官方介绍说明:
A cache that holds strong references to a limited number of values. Each time a value is accessed, it is moved to the head of a queue. When a value is added to a full cache, the value at the end of that queue is evicted and may become eligible for garbage collection.
一个以强引用持有外界对象的缓存,每次当一个value被使用时,它会移动到队列的头部。当缓存满时,在队列尾部的缓存将会被垃圾回收。
If your cached values hold resources that need to be explicitly released, override
entryRemoved(boolean, K, V, V)
.如果你的缓存持有资源明确需要被释放,重写entryRemoved(boolean, K, V, V)方法
If a cache miss should be computed on demand for the corresponding keys, override
create(K)
. This simplifies the calling code, allowing it to assume a value will always be returned, even when there’s a cache miss.如果缓存未命中需要计算相关的key(key对应的item丢失),重写create。这简化了调用的代码,认为总是有value返回的,甚至在缓存未命中的时候。
By default, the cache size is measured in the number of entries. Override
sizeOf(K, V)
to size the cache in different units. For example, this cache is limited to 4MiB of bitmaps:默认情况下,缓存的大小是由item数量决定,重写sizeOf来计算不同的缓存对象的大小
1234567 > int cacheSize = 4 * 1024 * 1024; // 4MiB> LruCache<String, Bitmap> bitmapCache = new LruCache<String, Bitmap>(cacheSize) {> protected int sizeOf(String key, Bitmap value) {> return value.getByteCount();> }> }>This class is thread-safe. Perform multiple cache operations atomically by synchronizing on the cache:
LruCache是线程安全的
123456 > synchronized (cache) {> if (cache.get(key) == null) {> cache.put(key, value);> }> }>This class does not allow null to be used as a key or value. A return value of null from
get(K)
,put(K, V)
orremove(K)
is unambiguous: the key was not in the cache.LruCache不允许key或者value为空
大致就是这些意思。
接下来看它的变量:
|
|
再看构造方法
|
|
做的事情就是给maxSize赋值,以及初始化LinkedHaspMap,这里看LinkedHashMap的三个参数:第一个参数initialCapacity,初始大小,第二个参数loadFactor,负载因子=0.75f,第三个参数accessOrder=true,基于访问顺序;accessOrder=false,基于插入顺序。
第一个参数 initialCapacity
用于初始化该 LinkedHashMap 的大小。
先简单介绍一下 第二个参数 loadFactor
,这个其实的 HashMap 里的构造参数,涉及到扩容问题,比如 HashMap 的最大容量是100,那么这里设置0.75f的话,到75容量的时候就会扩容。
主要是第三个参数 accessOrder=true
,这样的话 LinkedHashMap 数据排序就会基于数据的访问顺序,从而实现了 LruCache 核心工作原理。
以上就是构造函数,接下来再看get方法:
LruCache.get(K key)
|
|
其实上述最主要的还是
|
|
调用了LinkedHashMap的get方法加上构造方法中默认设置 LinkedHashMap 的 accessOrder=true来实现的LRU算法。
那么接下来就来看LinkedHashMap 的get方法:
LinkedHashMap.get(Object key)
|
|
看recordAccess方法:
|
|
看到首先执行remove方法然后执行addBefore
remove方法如下:
|
|
addBefore如下:
|
|
LinkedHashMap是双向循环链表,因此上述两步将entry放到了表尾。
看完了get方法再来看put方法:
LruCache.put(K key, V value)
|
|
一共有几点:
- 首先put开始的时候讲值放进了LinkedHashMap中,不管有没有超过设定的缓存量
- 通过safeSizeOf方法计算出此次需要添加的数据等容量,并添加到size中
- safeSizeOf其实就是调用了sizeOf来计算此次添加到数据大小
- 最后执行trimToSize来判断size是否大于maxSize,然后进行数据的移除
那么来看一下trimToSize方法:
|
|
可以看出这是一个死循环,只有当size<=maxSize才能跳出循环
也就是说该方法会判断之前的size是否大于maxSize,如果是的话,证明容量已经溢出了,然后接下来就会获取到Map的最前面的值,如果获取到的话就把它移除,同时减去他的容量,并添加一次回收次数,一直执行以上操作直到没有益处。跳出循环之后,会调用一次entryRemoved将最后一次删除的数据回调出去。
总结
以上就是LruCache的大致流程了,总结一下关键的几点:
- LruCache 是通过 LinkedHashMap 构造方法的第三个参数的 accessOrder=true 实现了 LinkedHashMap 的数据排序基于访问顺序 (最近访问的数据会在链表尾部),在容量溢出的时候,将链表头部的数据移除。从而,实现了 LRU 数据缓存机制
- LruCache 在内部的get、put、remove包括 trimToSize 都是安全的(因为都上锁了)。
- LruCache自身没有释放内存,将LinkedHashMap的数据移除了,如果数据还在别的地方被引用了,需要手动释放内存。
- 覆写entryRemoved方法可以知道Lrucache数据移除是否发生了冲突,也可以去手动释放资源。
- maxSize和sizeOf方法的覆写必须相同单位。