LRU 是 Least Recently Used 最近最少使用算法。
曾经,在各大缓存图片的框架没流行的时候。有一种很常用的内存缓存技术:SoftReference 和 WeakReference(软引用和弱引用)。但是走到了 Android 2.3(Level 9)时代,垃圾回收机制更倾向于回收 SoftReference 或 WeakReference 的对象。后来,又来到了 Android3.0,图片缓存在内容中,因为不知道要在是什么时候释放内存,没有策略,没用一种可以预见的场合去将其释放。这就造成了内存溢出。
当成一个 Map 用就可以了,只不过实现了 LRU 缓存策略。
使用的时候记住几点即可:
你需要提供一个缓存容量作为构造参数。覆写 sizeOf 方法 ,自定义设计一条数据放进来的容量计算,如果不覆写就无法预知数据的容量,不能保证缓存容量限定在最大容量以内。覆写 entryRemoved 方法 ,你可以知道最少使用的缓存被清除时的数据( evicted, key, oldValue, newVaule )。LruCache是线程安全的,在内部的 get、put、remove 包括 trimToSize 都是安全的(因为都上锁了)。还有就是覆写 create 方法 。以下是 一个 LruCache 实现 Bitmap 小缓存的案例, entryRemoved 里的自定义逻辑可以无视。
private static final float ONE_MIB = 1024 * 1024; // 7MB private static final int CACHE_SIZE = (int) (7 * ONE_MIB); private LruCache<String, Bitmap> bitmapCache; this.bitmapCache = new LruCache<String, Bitmap>(CACHE_SIZE) { protected int sizeOf(String key, Bitmap value) { return value.getByteCount(); } @Override protected void entryRemoved(boolean evicted, String key, Bitmap oldValue, Bitmap newValue) { ... } };LruCache 就是 利用 LinkedHashMap 的一个特性( accessOrder=true 基于访问顺序 )再加上对 LinkedHashMap 的数据操作上锁实现的缓存策略。
LruCache 的数据缓存是内存中的。
首先设置了内部 LinkedHashMap 构造参数 accessOrder=true, 实现了数据排序按照访问顺序。
然后在每次 LruCache.get(K key) 方法里都会调用 LinkedHashMap.get(Object key)。
如上述设置了 accessOrder=true 后,每次 LinkedHashMap.get(Object key) 都会进行 LinkedHashMap.makeTail(LinkedEntry<K, V> e)。
LinkedHashMap 是双向循环链表,然后每次 LruCache.get -> LinkedHashMap.get 的数据就被放到最末尾了。
在 put 和 trimToSize 的方法执行下,如果发生数据量移除,会优先移除掉最前面的数据(因为最新访问的数据在尾部)。
第一个参数 initialCapacity 用于初始化该 LinkedHashMap 的大小。
先简单介绍一下 第二个参数 loadFactor,这个其实的 HashMap 里的构造参数,涉及到扩容问题,比如 HashMap 的最大容量是100,那么这里设置0.75f的话,到75容量的时候就会扩容。
主要是第三个参数 accessOrder=true ,这样的话 LinkedHashMap 数据排序就会基于数据的访问顺序,从而实现了 LruCache 核心工作原理。
上述的 get 方法表面并没有看出哪里有实现了 LRU 的缓存策略。主要在 mapValue = map.get(key);里,调用了 LinkedHashMap 的 get 方法,再加上 LruCache 构造里默认设置 LinkedHashMap 的 accessOrder=true。
其实仔细看 if (accessOrder) 的逻辑即可,如果 accessOrder=true 那么每次 get 都会执行 N 次 makeTail(LinkedEntry<K, V> e) 。
接下来看看:
LinkedHashMap 是双向循环链表,然后此次 LruCache.get -> LinkedHashMap.get 的数据就被放到最末尾了。
以上就是 LruCache 核心工作原理。
接下来介绍 LruCache 的容量溢出策略。
记住几点:
put 开始的时候确实是把值放入 LinkedHashMap 了,不管超不超过你设定的缓存容量。然后根据 safeSizeOf 方法计算 此次添加数据的容量是多少,并且加到 size 里 。说到 safeSizeOf 就要讲到 sizeOf(K key, V value) 会计算出此次添加数据的大小 。直到 put 要结束时,进行了 trimToSize 才判断 size 是否 大于 maxSize 然后进行最近很少访问数据的移除。简单描述:会判断之前 size 是否大于 maxSize 。是的话,直接跳出后什么也不做。不是的话,证明已经溢出容量了。由 makeTail 图已知,最近经常访问的数据在最末尾。拿到一个存放 key 的 Set,然后一直一直从头开始删除,删一个判断是否溢出,直到没有溢出。
entryRemoved被LruCache调用的场景:
(put) put 发生 key 冲突时被调用,evicted=false,key=此次 put 的 key,oldValue=被覆盖的冲突 value,newValue=此次 put 的 value。(trimToSize) trimToSize 的时候,只会被调用一次,就是最后一次被删除的最少访问数据带回来。evicted=true,key=最后一次被删除的 key,oldValue=最后一次被删除的 value,newValue=null(此次没有冲突,只是 remove)。(remove) remove的时候,存在对应 key,并且被成功删除后被调用。evicted=false,key=此次 put的 key,oldValue=此次删除的 value,newValue=null(此次没有冲突,只是 remove)。(get后半段,查询丢失后处理情景,不过建议忽略) get 的时候,正常的话不实现自定义 create 的话,代码上看 get 方法只会走一半,如果你实现了自定义的 create(K key) 方法,并且在 你 create 后的值放入 LruCache 中发生 key 冲突时被调用,evicted=false,key=此次 get 的 key,oldValue=被你自定义 create(key)后的 value,newValue=原本存在 map 里的 key-value。解释一下第四点吧:<1>.第四点是这样的,先 get(key),然后没拿到,丢失。<2>.如果你提供了 自定义的 create(key) 方法,那么 LruCache 会根据你的逻辑自造一个 value,但是当放入的时候发现冲突了,但是已经放入了。<3>.此时,会将那个冲突的值再让回去覆盖,此时调用上述4.的 entryRemoved。
因为 HashMap 在数据量大情况下,拿数据可能造成丢失,导致前半段查不到,你自定义的 create(key) 放入的时候发现又查到了(有冲突)。然后又急忙把原来的值放回去,此时你就白白create一趟,无所作为,还要走一遍entryRemoved。
综上就如同注释写的一样:
/** * 1.当被回收或者删掉时调用。该方法当value被回收释放存储空间时被remove调用 * 或者替换条目值时put调用,默认实现什么都没做。 * 2.该方法没用同步调用,如果其他线程访问缓存时,该方法也会执行。 * 3.evicted=true:如果该条目被删除空间 (表示 进行了trimToSize or remove) evicted=false:put冲突后 或 get里成功create后 * 导致 * 4.newValue!=null,那么则被put()或get()调用。 */ protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) { }在 get, put, trimToSize, remove 四个方法里的 entryRemoved 方法都不在同步块里。因为 entryRemoved 回调的参数都属于方法域参数,不会线程不安全。
本地方法栈和程序计数器是线程隔离的数据区
LruCache重要的几点:
LruCache 是通过 LinkedHashMap 构造方法的第三个参数的 accessOrder=true 实现了 LinkedHashMap 的数据排序基于访问顺序 (最近访问的数据会在链表尾部),在容量溢出的时候,将链表头部的数据移除。从而,实现了 LRU 数据缓存机制。
LruCache 在内部的get、put、remove包括 trimToSize 都是安全的(因为都上锁了)。
LruCache 自身并没有释放内存,将 LinkedHashMap 的数据移除了,如果数据还在别的地方被引用了,还是有泄漏问题,还需要手动释放内存。
覆写 entryRemoved 方法能知道 LruCache 数据移除是是否发生了冲突,也可以去手动释放资源。
maxSize 和 sizeOf(K key, V value) 方法的覆写息息相关,必须相同单位。( 比如 maxSize 是7MB,自定义的 sizeOf 计算每个数据大小的时候必须能算出与MB之间有联系的单位 )