Android 源码之LruCache
“三级缓存”这个词我想搞Android 都知道，与其相关的就是LruCache，今天我们就来说说LruCache。
LruCache（Least Recently Used），即最近最少使用算法。
在android源码包名为android.util下就有这么一个类：LruCache，已经帮我们实现好了LruCache算法。
在说LruCache之前，总少不要说LinkedHashMap，而LinkedHashMap是继承于HashMap的，而HashMap相关东西可参考笔者之前写的：HashMap、ArrayMap、SparseArray
我们还是直接上demo：
System.out.println("————————LinkedList——————————");
LinkedList<String> linkedList=new LinkedList<>();
linkedList.add("1");
linkedList.add("2");
linkedList.add("3");
linkedList.add("4");
System.out.println("获取第二个数据："+linkedList.get(1));
for(String string:linkedList){
System.out.println("数据："+string);
}
System.out.println("—————————HashMap—————————");
HashMap<Integer,String> hashMap=new HashMap<>();
hashMap.put(10,"1");
hashMap.put(2,"2");
hashMap.put(3,"3");
hashMap.put(4,"4");
System.out.println("获取key为2的数据："+hashMap.get(2));
for (Map.Entry<Integer,String> entry:hashMap.entrySet()){
System.out.println("数据："+entry.getValue());
}
打印出来的结果如下：
————————LinkedList——————————
获取第二个数据：2
数据：1
数据：2
数据：3
数据：4
—————————HashMap—————————
获取key为2的数据：2
数据：2
数据：3
数据：4
数据：1
很显然LinkedList是有序的，而HashMap是无序的，所以，我们今天要说的LinkedHashMap就应运而生了，我们继续看demo：
System.out.println("—————LinkedHashMap（无参）——————");
LinkedHashMap<Integer,String> linkedHashMap0=new LinkedHashMap<>();
linkedHashMap0.put(10,"1");
linkedHashMap0.put(2,"2");
linkedHashMap0.put(3,"3");
linkedHashMap0.put(4,"4");
System.out.println("获取key为2的数据："+linkedHashMap0.get(2));
for (Map.Entry<Integer,String> entry:linkedHashMap0.entrySet()){
System.out.println("数据："+entry.getValue());
}
System.out.println("—————LinkedHashMap（有参）——————");
LinkedHashMap<Integer,String> linkedHashMap=new LinkedHashMap<>(0, 0.75f, true);
linkedHashMap.put(10,"1");
linkedHashMap.put(2,"2");
linkedHashMap.put(3,"3");
linkedHashMap.put(4,"4");
System.out.println("获取key为2的数据："+linkedHashMap.get(2));
for (Map.Entry<Integer,String> entry:linkedHashMap.entrySet()){
System.out.println("数据："+entry.getValue());
}
打印出来的结果如下：
—————LinkedHashMap（无参）——————
获取key为2的数据：2
数据：1
数据：2
数据：3
数据：4
—————LinkedHashMap（有参）——————
获取key为2的数据：2
数据：1
数据：3
数据：4
数据：2
第一个LinkedHashMap无参实现了有序的Map
第二个LinkedHashMap有参（第三个参数accessOrder为true时）不止实现了有序的Map，而且将最近一次调用get获取的数据置于队尾。
好啦，LinkedHashMap基本的东西也就这样子了，接下来我们来看看LruCache的源码，首先在这个类最开始部分的注释已经给了使用示例，如下图：
LruCache使用示例
用法非常简单，接下来我们看看其构造函数：
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
原来在初始化的时候就创建了LinkedHashMap，而且就是上面LinkedHashMap有参的形式，就是利用其来实现最近最少使用算法的。
LruCache的源码非常简单，没什么好说的，但是里面有一个方法却让人有点摸不着头脑：
/**
* @param maxSize the maximum size of the cache before returning. May be -1
* to evict even 0-sized elements.
*/
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!");
}
if (size <= maxSize) {
break;
}
// BEGIN LAYOUTLIB CHANGE
// get the last item in the linked list.
// This is not efficient, the goal here is to minimize the changes
// compared to the platform version.
Map.Entry<K, V> toEvict = null;
for (Map.Entry<K, V> entry : map.entrySet()) {
toEvict = entry;
}
// END LAYOUTLIB CHANGE
if (toEvict == null) {
break;
}
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
这个方法是用来当存于LinkedHashMap中数据大小超过最大限制数时，将最近最少使用的数据进行移除的，按照LinkedHashMap特性，最近使用到会至于队尾，然而我们摘取上面关键的代码：
Map.Entry<K, V> toEvict = null;
for (Map.Entry<K, V> entry : map.entrySet()) {
toEvict = entry;
}
这样找到的不就是最后一个元素吗？如果按照这代码执行的话，被移除的就是最后一个元素，也就是最近使用过的元素，这根本就违背了“最近最少使用”原则嘛！
这到底是怎么回事？
我越看越不对劲，这代码这么简单我没理由会理解错的啊！难不成我对“最近最少使用算法”本来就存在误解？吓得我赶紧百度一番，没错啊！
于是，我写了个demo来验证一下：
LruCache<String,Integer> lruCache=new LruCache<>(4);
lruCache.put("1",1);
lruCache.put("2",2);
lruCache.put("3",3);
lruCache.put("4",4);
lruCache.get("2");
Map<String, Integer> snapshot = lruCache.snapshot();
for(Map.Entry<String,Integer> entry:snapshot.entrySet()){
LogUtil.loge("数据："+entry.getValue());
}
LogUtil.loge("------------------超出后------------------");
lruCache.put("5",5);
snapshot = lruCache.snapshot();
for(Map.Entry<String,Integer> entry:snapshot.entrySet()){
LogUtil.loge("数据："+entry.getValue());
}
打印出来的结果如下：
数据：1
数据：3
数据：4
数据：2
------------------超出后------------------
数据：3
数据：4
数据：2
数据：5
幸好结果正常，还有没颠覆我对LruCache算法的理解O(∩_∩)O
那到底是为什么呢？干脆点，打断点进去看看啊，然而我惊奇地发现，上面我有疑问的代码变成了这样子的：
Map.Entry<K, V> toEvict = map.eldest();
if (toEvict == null) {
break;
}
如果是这样子的话倒是没错，因为在LinkedHashMap中有这么一个方法，返回的就是对头元素，这样确实符合LruCache算法，当超出时最开始加入的会被移除。
// Android-added: eldest(), for internal use in LRU caches
/**
* Returns the eldest entry in the map, or {@code null} if the map is empty.
* @hide
*/
public Map.Entry<K, V> eldest() {
return head;
}
其实，你用断点进去发现代码不一样时，你会发现原来是android版本的问题，比如笔者用的夜神模拟器版本为19，其源码就是上面那样子的。而一开始我查看源码时用的是项目里配的目标版本为28的源码，这就是区别！
于是，我又打开了AndroidStudio自带的API为28的模拟器，我想继续进断点看看，结果呢？诡异的事又发生了，怎么感觉错行了呢？感觉执行的和我看到的不是同一行呢？而且也没有运行上面那个诡异代码的循环，好像到附近也是一行跳过，倒跟API 19的那个有点像了····
最后，我终于注意到那诡异源码上的那些英文注释：
// BEGIN LAYOUTLIB CHANGE
// get the last item in the linked list.
// This is not efficient, the goal here is to minimize the changes
// compared to the platform version.
然后我一口气查看最近几个版本的源码，发现原来在API 22的时候LruCache类中就出现了这样子的注释和诡异代码，而API 23-27又恢复正常，现在API 28又变成这样子诡异了，简直了······
其实嘛，从上面的英文注释我们大概也能猜到是为了兼容性吧，算了，这里就不作深究了，毕竟注释也说清楚了，那代码是无效的，我想这也是断点进去会诡异的原因吧。
我们来说另外一个吧，LinkedHashMap如何获取头部元素和尾部元素呢？
最简单的做法：
Map.Entry<Integer,String> first=null;
Map.Entry<Integer,String> last=null;
for (Map.Entry<Integer,String> entry:linkedHashMap.entrySet()){
if(first==null){
first=entry;
//break;
}
last=entry;
}
这样写当然没毛病，就是在获取尾部元素时效率有点低。
我们注意到上面LruCache中正常代码有用到LinkedHashMap的一个方法：eldest()，根据注释，我们知道这个方法是android为LruCache加的，而且使用了@hide注解，所以，我们是无法直接访问到的，嘿嘿，这话的意思是，我们可以间接访问到，必须滴，反射大法上！
try {
Field headField = linkedHashMap.getClass().getDeclaredField("head");
Field tailField = linkedHashMap.getClass().getDeclaredField("tail");
headField.setAccessible(true);
tailField.setAccessible(true);
Map.Entry<Integer,String> head = (Map.Entry<Integer, String>) headField.get(linkedHashMap);
Map.Entry<Integer,String> tail = (Map.Entry<Integer, String>) tailField.get(linkedHashMap);
if(head!=null){
System.out.println("头部元素："+head.getValue());
}
if(tail!=null){
System.out.println("尾部元素："+tail.getValue());
}
} catch (IllegalAccessException e) {
e.printStackTrace();
} catch (NoSuchFieldException e) {
e.printStackTrace();
}
代码也非常简单，就不多说了！
