一、引言
关于 LruCache 的总结，因为工作推迟了好长一段时间，因此趁现在有点空赶紧记录下来。
相信很多童鞋也跟我一样，最初都是使用 LruCache 作为 ImageLoader 图片缓存中的一环，但是使用的过程中，我们并不关心它这个“最近使用原则”到底源码怎么实现的，而仅仅在意它具备这样的特性。因此，本文要做的工作如下：
- 从基本使用解释”最近使用“这一特性；
- 结合源码分析”最近使用“的实现；
二、从使用到源码
首先来说说“最近使用”的特点：假设头部为最近的地方，而尾部是最远的地方，那么最先插入的元素会放到尾部，而最后插入的元素会被放到头部，并且如果我们使用了其中的某个元素，那么这个元素会被放到头部；如果容量到达了限定值，那么再次插入元素的时候就会删除掉尾部使用频率最低的元素以插入新元素。 这一特性可解释如下图：
LRU使用特性
通常我们会这样使用 LruCache，假定限制内存大小为 5M，那么可以这么做：
// 限定大小
final int maxSize = 1024 * 1024 * 5;
LruCache<String, Bitmap> lruCache = new LruCache<String, Bitmap>(maxSize){
@Override
protected int sizeOf(String key, Bitmap value) {
return value.getRowBytes() * value.getHeight() / 1024 ;
}
@Override
protected void entryRemoved(boolean evicted, String key, Bitmap oldValue,Bitmap newValue) {
// 如果在列表请求时这样实现，那么快速滑动时肯定会造成内存抖动，因此实际使用中
// 可以先将这些需要清理掉的图片缓存一下，然后在某个时间节点上集中清理掉
if (!oldValue.isRecycled()){
oldValue.recycle();
}
}
};
跟进到它的构造方法，可以看到它创建了一个 LinkedHashMap ，并且仅仅是基于这一数据结构来实现：
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<Integer, Integer> linkedHashMap= new LinkedHashMap<>(0, 0.75f, true);
linkedHashMap.put(1, 1);
linkedHashMap.put(2, 2);
linkedHashMap.put(3, 3);
linkedHashMap.put(4, 4);
linkedHashMap.put(5, 5);
for (Map.Entry<Integer, Integer> e : linkedHashMap.entrySet()){
Log.i(TAG, e.getKey() + " <->" + e.getValue());
}
// 这里模拟先后使用 4 和 3 这两个元素
linkedHashMap.get(4);
linkedHashMap.get(3);
Log.i(TAG, "-----------------");
for (Map.Entry<Integer, Integer> e : linkedHashMap.entrySet()){
Log.i(TAG, e.getKey() + " <->" + e.getValue());
}
// 这里模拟到达内存限定值，删除最不常用的那个元素
Log.i(TAG, "delete: " + linkedHashMap.keySet().iterator().next());
输出如下：
1 <->1
2 <->2
3 <->3
4 <->4
5 <->5
-------------
1 <->1
2 <->2
5 <->5
4 <->4
3 <->3
delete: 1 // 要删除的元素
根据结果可见，这确实跟我们跟我们前面所理解的一样，只不过上面是模拟操作，我们接下来看看 LruCache 对这部分的实现。首先定位到 put 方法，可见每次添加新元素时都会统计数量和空间大小、进行新旧元素的替换，然后检查是否超出空间限定值，如果超出，移除尾部最不常用的元素：
public final V put(K key, V value) {
// 不允许 key、value 为 null
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);
// 如果 key 位置上已经存在元素，那么用新元素替换旧元素，并重新统计空间大小
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
// 将 key 上的旧元素删除掉
if (previous != null) {
entryRemoved(false, key, previous, value);
}
// 超出容量时删除尾部最不常用的元素
trimToSize(maxSize);
return previous;
}
上面的 trimToSize 源码如下，跟集合自身的 trimToSize 功能不一样之处在于，集合自身的 trimToSize 用于去除多余的没有存放元素的空间，而这里是移除尾部最不常用的元素，些许类似：
private void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
// 1. 统计错误的情况
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName()
+ ".sizeOf() is reporting inconsistent results!");
}
// 2. 还有足够空间容量的情况
if (size <= maxSize) {
break;
}
// 3. 超出限定容量的情况
Map.Entry<K, V> toEvict = null;
// 定位到尾部最不常用的元素，标记为删除
for (Map.Entry<K, V> entry : map.entrySet()) {
toEvict = entry;
}
// 如如果容器没有元素，直接退出
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、HashMap版本基于JDK8；在Android中则基于Android N
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
LinkedHashMap 继承自 HashMap，因此我们先来回顾一下 HashMap 和祖先 Hashtable 的特性：
内部构造：
- 当发生冲突（
key的哈希值相同，但是他们并不equals）的量数据量较少（< 8）时，HashMap和Hashtable都采用 数组 + 单向链表 这种结构作为解决方案； - 当发生冲突的数据量较大（
> 8）时，不同于Hashtable，HashMap采用了数组 + 红黑树的解决方案； -
HashMap是一种非线程安全的数据结构，而Hashtable是
上面描述了 HashMap 和 Hashtable 的主要区别，这种差异导致 HashMap 在操作性能和使用场景上都比 Hashtable 更胜一筹，并且你完全可以放弃使用 Hashtable ，而在并发场景下使用 ConcurrentHashMap；
回到 HashMap， 为什么 采用 数组 + 单向链表 和 数组 + 红黑树 两种切换方案呢？原因很简单，因为数据量很小时，使用单向链表的操作效率已经够高了，并且单向链表内部构造简单，能减少额外的空间分配；相应的，数据量大时采用红黑树，因为红黑树能够保证各操作的做坏时间复杂度为 log(n)，因此适用于数据量大且操作频繁的场景；
OK， 有了上面的回顾内容，我们可以对 LinkedHashMap 有个初步的了解，接下来我们主要看看 LinkedHashMap中新增的排序规则。
首先来看看它的构造器，初始容量（initialCapacity）、加载因子（loadFactor）就不解释了，看到 参数 accessOrder，它用于控制是否开启 就近使用原则：
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
这里我们假设开启了就近使用原则，获取元素时是这样的：
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
这里的节点是双向链表的节点,继承自 HashMap.Node，如下：
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
LinkedHashMapEntry<K,V> before, after;
LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
注意到上面的 afterNodeAccess，源码如下，在这里会将节点移动到尾部，而这里的尾部代表最常使用的节点，也是最近节点。
void afterNodeAccess(Node<K,V> e) {
LinkedHashMapEntry<K,V> last;
if (accessOrder && (last = tail) != e) { // 节点不在尾部
LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, // 当前节点
b = p.before, // 前一个节点
a = p.after; // 后一个节点
p.after = null; // 剪断 当自己与后一个节点的连接
// 1. 将自己从链表中分离出来
if (b == null) // 前面没节点了，说明它自己是头部，那么直接让位给下一个节点
head = a;
else // 前面还有节点，那么将前一个节点连接到下一个节点，让位
b.after = a;
if (a != null) // 因为是双向链表，所以这里 a 节点存在的时候需要重置一下前一个连接，
a.before = b;
else
last = b; // 不存在则直接把 befor 当成尾部
if (last == null) // 说明当前链表无节点， 那么直接把当前节点作为头部
head = p;
else { // 已经存在节点的话，那么将当前节点连接到尾部
p.before = last;
last.after = p;
}
tail = p; // 尾部重新赋值一下
++modCount;
}
}
相对于 HashMap 而言， LinkedHashMap 使用双向链表而不是单向链表，并且有排序规则，能够对元素进行排序。
三、总结
嗯~，写到最后发现没啥话可说的了...嘿嘿
文中主要分析总结了一下 LruCache 的最近使用原则，接着回顾了一下 LinkedHashMap 相关的一些知识，如 HashMap 和 Hashtable，并具体分析了一下它在get元素时进行的操作规则;
总的来说，LruCache相当于LinkedHashMap的一层代理，自身控制内存大小，而将存储操作委托给了LinkedHashMap；
网友评论