0. 前言
学过操作系统这门课的朋友都还记得 LRU
这个算法吧,中文名叫”最近最久未使用”,它是用在页面置换策略中的一种很巧妙的淘汰算法,而在 Android
中,也有一个缓存淘汰机制用到了它,叫做 LruCache
,它也可以说是一个精妙的设计吧,这篇博文中,笔者将带领大家剖析它源码中的精妙之处…
1. 初始化
LruCache
类源码位于 android.util.LruCache
包下,大家也可以同步阅读。第一件事,便是看其实例化过程,只有一个带参数的构造函数,参数的意思是缓存最大支持的内存容量,注意哦,不是数量,是占用空间的容量:
1 2 3 4 5 6 7 8 9 10
| 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
,它是一个循环链表,前面两个参数不要紧,关键在最后一个参数,最后一个参数含义是”是否以最近访问的顺序排序”,也就是说,如果为 true
,那么 HashMap
的链表将会以最近访问的元素在尾部,很久没访问的元素在头部的顺序来排序,在 LinkedHashMap
的源码中可以证实这一说法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| public V get(Object key) { ... for (...; e != null; e = e.next) { K eKey = e.key; if (eKey == key || ...) { if (accessOrder) makeTail((LinkedEntry<K, V>) e); return e.value; } } return null; }
private void makeTail(LinkedEntry<K, V> e) { e.prv.nxt = e.nxt; e.nxt.prv = e.prv; LinkedEntry<K, V> header = this.header; LinkedEntry<K, V> oldTail = header.prv; e.nxt = header; e.prv = oldTail; oldTail.nxt = header.prv = e; modCount++; }
|
并且,通过 LinkedHashMap#eldest()
方法可以返回最老的结点:
1 2 3 4 5 6 7
| public Entry<K, V> eldest() { LinkedEntry<K, V> eldest = header.nxt; return eldest != header ? eldest : null; }
|
2. 添加
初始化步骤为我们提供了一个可供存储缓存的循环链表,还提供好了 LRU
排序。接下来看看如何添加一个缓存记录的:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| public final V put(K key, V value) { if (key == null || value == null) { throw new NullPointerException("key == null || value == null"); } V previous; synchronized (this) { putCount++; size += safeSizeOf(key, value); previous = map.put(key, value); if (previous != null) { size -= safeSizeOf(key, previous); } } if (previous != null) { entryRemoved(false, key, previous, value); } trimToSize(maxSize); return previous; }
|
不少的代码,其实就是两步,先将缓存结点添加进 LinkedHashMap
,然后调用 trimToSize(maxSize)
检查大小并淘汰。接下来看看是如何淘汰就节点的:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| public void trimToSize(int maxSize) { while (true) { K key; V value; synchronized (this) { ... 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); } }
|
上面两段代码都提到了 entryRemoved()
方法,这其实是一个供子类扩展功能的方法,它可以被子类覆写,比如可以再增加一级磁盘缓存,那么磁盘上的添加和移除缓存方法就需要子类来重写了:
1 2 3 4 5 6 7 8 9 10
|
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}
protected V create(K key) { return null; }
|
3. 取出
添加好了缓存就可以取出来用了,接下来看是如何取出来的:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| public final V get(K key) { ... V mapValue; synchronized (this) { mapValue = map.get(key); if (mapValue != null) { hitCount++; return mapValue; } missCount++; } V createdValue = create(key); if (createdValue == null) { return null; } synchronized (this) { createCount++; mapValue = map.put(key, createdValue); if (mapValue != null) { map.put(key, mapValue); } else { size += safeSizeOf(key, createdValue); } } if (mapValue != null) { entryRemoved(false, key, createdValue, mapValue); return mapValue; } else { trimToSize(maxSize); return createdValue; } }
|
其实完成的内容也很简单,就是从 LinkedHashMap
中取出,如果有就返回,如果没有就调用子类的 create(key)
方法,最后要记得验证是否需要淘汰最近最久未使用的元素。
总结
LruCache
的源码还是很简单的,但它很巧妙地结合 LinkedHashMap
实现了 LRU
算法,可以说非常值得一读!