转载

无意中发现 Android 5.0 LruCache 的 bug

码哒，今天无意中发现Android 5.0(api level 21)之前的LruCache实现居然存在一个bug.

由于在电脑上（Java SE环境）测试code比较方便，我便将最近写在Android项目中的框架代码copy到Java项目中进行测试，然后缺少一个LruCache, 我也直接将其源码copy过来，但是报了一个错误，正是下面第一段代码中

map.eldest();

这句，但是这个方法由于不是Java标准API而被

@hide

了，我便想都不想，直接改成了遍历map并取出最后一个元素（思维定式，以为LinkedHashMap的最后一个元素就是那个eldest()的，即LRU（Least Recently Used）的），但是测试中很快发现了问题，然后在LinkedHashMap源码中找到其定义及注释，修改为取出链表的第一个元素了。

然而凑巧的是，今天下班我把代码copy到自己的本上带回家测试，再次copy这个LruCache源码的时候，发现居然没有报错，纳闷中，我去翻看那行怎么不报错，便发现了该问题。那段代码正好跟我昨天刚开始犯的错误一样，遍历最后一个元素当做LRU的，并将去驱逐。并且加了注释，大意是说：由于

map.eldest();

为非标准API, 所以将其修改了。

OK，看代码吧。

首先来看看正确的实现 Android 6.0(API Level 23)：

```Java /* * 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<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);
    }
}

其中有个

下面来看看错误的实现 Android 5.0(API Level 21)：

```Java /* * @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);
    }
}

注意其中这段以及其注释说明：

Java
Map.Entry<K, V> toEvict = null;
for (Map.Entry<K, V> entry : map.entrySet()) {
toEvict = entry;
}
``

/** * 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 * ...(略) ``

是说，这个版本不能使用非标准API

然而这段代码经过测试，在Cache Size填满后，确实总是驱逐最后添加进去的元素。显然不符合Lru的意图。

需要注意的是，LruCache的map是这么构造的：

this.map = new LinkedHashMap<K, V>(0, 0.75f, true);

，重点在这个

true

, 表示任何一个操作(get, put等)都将触发重排序，将这个被操作的元素排到链表的末尾，因此末尾的是最近“频繁”使用的，而不是LRU的，那么这个

取出末尾的那个元素并将其驱逐

的逻辑，显然是错误的！

那么我们还是回过头来看看

eldest()

到底做了什么吧！

Java
/**
* Returns the eldest entry in the map, or {@code null} if the map is empty.
* @hide
*/
public Entry<K, V> eldest() {
LinkedEntry<K, V> eldest = header.nxt;
return eldest != header ? eldest : null;
}

eldest()

直接返回了

header.nxt

.
``

Java 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; ``