android lrucache清空,Android LruCache 的 Bug
码哒，今天无意中发现Android 5.0(api level 21)之前的LruCache实现居然存在一个bug。
由于在电脑上(Java SE环境，非手机上)测试code比较方便，我便将最近写在Android项目中的框架代码copy到Java项目中进行测试，然后缺少一个LruCache, 我也直接将其源码复制过来，但是报了一个错误，正是下面第一段代码中map.eldest();这句，但是这个方法由于不是Java标准API而被@hide了，我便想也没想，直接改成了遍历map并取出最后一个元素(思维定式，以为LinkedHashMap的最后一个元素就是那个eldest()的，即LRU的)，但是测试中很快发现了问题，然后在LinkedHashMap源码中找到其定义及注释，修改为取出链表的第一个元素了。
然而凑巧的是，今天下班我把代码copy到自己的本儿上准备带回家测试，再次copy这个LruCache源码的时候，发现居然不报错了，纳闷中，我便再次翻到那一行，就发现了题述的问题：那段代码正好跟我昨天刚开始犯的错误一样，遍历最后一个元素当做LRU的，并将去驱逐。并且加了注释，大意是说：由于map.eldest();为非标准API, 所以将其修改了。
OK，看代码吧。
首先来看看正确的实现 Android 6.0(API Level 23)：
/**
* Remove the eldest entries until the total of remaining entries is at or
* below the requested size.
*
* @param maxSize the maximum size of the cache before returning. May be -1
* to evict even 0-sized elements.
*/
public 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;
}
Map.Entry 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);
}
}
其中有个map.eldest();方法，表示取出LinkedHashMap中最年长的元素，并将其驱逐。
下面来看看错误的实现 Android 5.0(API Level 21)：
/**
* @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 toEvict = null;
for (Map.Entry 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);
}
}
注意其中这段以及其注释说明：
Map.Entry toEvict = null;
for (Map.Entry entry : map.entrySet()) {
toEvict = entry;
}
遍历取出最后一个元素，这个正是将被驱逐的元素。同时在类说明中给了一段注释：
import java.util.LinkedHashMap;
import java.util.Map;
/**
* BEGIN LAYOUTLIB CHANGE
* This is a custom version that doesn't use the non standard LinkedHashMap#eldest.
* END LAYOUTLIB CHANGE
*
* 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
* ...(略)
是说，这个版本不能使用非标准APILinkedHashMap#eldest。然而紧接着的一句话：
Each time a value is accessed, it is moved to the head of a queue.
每次访问一个值时，它都会被移动到队列的head(意思是说head是 most-recently，不是 least-recently)。
就说错了，有LinkedHashMap的文档为证：
* A special {@link #LinkedHashMap(int,float,boolean) constructor} is
* provided to create a linked hash map whose order of iteration is the order
* in which its entries were last accessed, from least-recently accessed to
* most-recently (access-order). This kind of map is well-suited to
* building LRU caches.
从“较远的近”(最近最少访问)到“极为最近”排序，说明head是“较远的近”，是 least-recently，是eldest。
这段代码经过测试，在Cache Size填满后，确实总是驱逐最后添加进去的元素。显然不符合Lru的意图。
需要注意的是，LruCache的map是这么构造的：this.map = new LinkedHashMap(0, 0.75f, true);，重点在这个true, 表示任何一个操作(get, put等)都将触发重排序，将这个被操作的元素排到链表的末尾，因此末尾的是最近“频繁”使用的，而不是 LRU(Least Recently Used)最近“最少”使用的，那么这个取出末尾的那个元素并将其驱逐的逻辑，显然是错误的！
那么我们还是回过头来看看eldest()到底做了什么吧！
/**
* Returns the eldest entry in the map, or {@code null} if the map is empty.
* @hide
*/
public Entry eldest() {
LinkedEntry eldest = header.nxt;
return eldest != header ? eldest : null;
}
eldest()直接返回了header.nxt.
public class LinkedHashMap extends HashMap {
/**
* A dummy entry in the circular linked list of entries in the map.
* The first real entry is header.nxt, and the last is header.prv.
* If the map is empty, header.nxt == header && header.prv == header.
*/
transient LinkedEntry header;
而header.nxt又是The first real entry. 意思很明确了，就是返回链表的第一个元素。
那么可以肯定Android 5.0(API Level 21)及以前对LruCache的实现就是一个bug了。