LRU 全称为 Least Recently Used 即最近最少使用，是一种缓存置换算法。淘汰最长时间未使用的对象。下面是 LruCache 的结构。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18private final LinkedHashMap<K, V> map;
private int size; //当前缓存内容的大小。它不一定是元素的个数，比如如果缓存的是图片，一般用的是图片占用的内存大小
private int maxSize; // 最大可缓存的大小
private int putCount; // put 方法被调用的次数
private int createCount; // create(Object) 被调用的次数
private int evictionCount; // 被置换出来的元素的个数
private int hitCount; // get 方法命中缓存中的元素的次数
private int missCount; // get 方法未命中缓存中元素的次数
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
可以看出，LruCache 是使用 LinkedHashMap 来存储内容的。LinkedHashMap 继承自 HashMap ，不同的是，它是一个双向循环链表，它的每一个数据结点都有两个指针，分别指向直接前驱和直接后继。LinkedHashMap 的 put（key ，value） 方法，我觉得是当 map 中已经插入过 key 的话，把newValue插入到map中，返回之前存储的 oldValue ，否则返回null。
新建一个节点时的插入过程1
2
3
4
5
6
7
8
9
10
11
12
13
14
15@Override void addNewEntry(K key, V value, int hash, int index) {
LinkedEntry<K, V> header = this.header;
// Remove eldest entry if instructed to do so.
LinkedEntry<K, V> eldest = header.nxt;
if (eldest != header && removeEldestEntry(eldest)) {
remove(eldest.key);
}
// Create new entry, link it on to list, and put it into table
LinkedEntry<K, V> oldTail = header.prv;
LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
key, value, hash, table[index], header, oldTail);
table[index] = oldTail.nxt = header.prv = newTail;
}
可以看到，当加入一个新结点时，结构如下：
当accessOrder为true时，更新或者访问一个结点时，它会把这个结点移到尾部，对应代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13private void makeTail(LinkedEntry<K, V> e) {
// Unlink e
e.prv.nxt = e.nxt;
e.nxt.prv = e.prv;
// Relink e as tail
LinkedEntry<K, V> header = this.header;
LinkedEntry<K, V> oldTail = header.prv;
e.nxt = header;
e.prv = oldTail;
oldTail.nxt = header.prv = e;
modCount++;
}
以上代码分为两步，第一步是先把该节点取出来（Unlink e），如下图：
第二步是把这个这个结点移到尾部（Relink e as tail），也就是把旧的尾部的nxt以及头部的prv指向它，并让它的nxt指向头部，把它的prv指向旧的尾部。如下图：
LruCache
safeSizeOf(K key, V value) 是返回 value 对应的 size 大小
通过重写 sizeOf( ) 方法来确定每个 size 的大小
来读一下它的get方法：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
42
43
44
45
46
47
48
49
50
51
52
53public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) { //获取到值时，就返回该值
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
/*
* Attempt to create a value. This may take a long time, and the map
* may be different when create() returns. If a conflicting value was
* added to the map while create() was working, we leave that value in
* the map and release the created value.
*/
//尝试创建一个值，这个方法的默认实现是直接返回null。但是在它的设计中，这个方法可能执行完成之后map已经有了变化。
V createdValue = create(key);
if (createdValue == null) {
return null; // 如果不为没有命名的key创建新值，则直接返回 null
}
synchronized (this) {
createCount++;
//将创建的值放入map中，如果map在前面的过程中正好放入了这对key-value，那么会返回放入的value
mapValue = map.put(key, createdValue);
if (mapValue != null) {
//如果不为空，说明不需要我们所创建的值，所以又把返回的值放进去
// There was a conflict so undo that last put
map.put(key, mapValue);
} else {
//为空，说明我们更新了这个key的值，需要重新计算大小
size += safeSizeOf(key, createdValue);
}
}
//上面放入的值有冲突
if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);// 通知之前创建的值已经被移除，而改为mapValue
return mapValue;
} else {
trimToSize(maxSize);//没有冲突时，因为放入了新创建的值，大小已经有变化，所以需要修整大小
return createdValue;
}
}
LruCache 是可能被多个线程同时访问的，所以在读写 map 时进行加锁。当获取不到对应的 key 的值时，它会调用其 create(K key) 方法，这个方法用于当缓存没有命名时计算一个 key 所对应的值，它的默认实现是直接返回 null。这个方法并没有加上同步锁，也就是在它进行创建时，map 可能已经有了变化。
所以在 get 方法中，如果 create(key) 返回的 V 不为 null，会再把它给放到 map 中，并检查是否在它创建的期间已经有其他对象也进行创建并放到 map 中了，如果有，则会放弃这个创建的对象，而把之前的对象留下，否则因为我们放入了新创建的值，所以要计算现在的大小并进行 trimToSize。
trimToSize 方法是根据传进来的 maxSize，如果当前大小超过了这个 maxSize，则会移除最老的结点，直到不超过。代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25public 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 || map.isEmpty()) {
break;
}
Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
再来看put方法，它的代码也很简单：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22public 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;
}
主要逻辑是，计算新增加的大小，加入 size ，然后把 key-value 放入 map 中，如果是更新旧的数据（map.put(key, value) 会返回之前的 value），则减去旧数据的大小，并调用 entryRemoved(false, key, previous, value) 方法通知旧数据被更新为新的值，最后也是调用 trimToSize(maxSize) 修整缓存的大小。
本文参考: Android源码解析——LruCache
