LRU 算法描述
当序列达到设置的内存上限时, 丢弃序列中最近最少使用的元素.
LruCache
Android SDK 提供的使用了(Least Recently Used)最近最少使用算法的缓存类.
编写一个 LruCache, 用于缓存 Integer.
1
2
3
4
5
6
7
8
9
10
|
public class IntegerCache extends LruCache<String, Integer> {
public IntegerCache(int maxSize) {
super(maxSize);
}
@Override
protected int sizeOf(String key, Integer value) {
return Integer.SIZE;
}
}
|
1
2
3
4
5
6
7
8
9
10
|
// 最大容量为 4 个 Integer
IntegerCache ca = new IntegerCache(4 * Integer.SIZE)
ca.put("1", 1);
ca.put("2", 2);
ca.put("3", 3);
ca.put("4", 4);
ca.get("4");
ca.put("5", 5);
ca.put("4", 4);
ca.put("6", 6);
|
缓存中内容:
1
2
3
4
5
6
7
8
9
|
{1=1} // put 1
{1=1, 2=2} // put 2
{1=1, 2=2, 3=3} // put 3
{1=1, 2=2, 3=3, 4=4} // put 4
---
{1=1, 2=2, 3=3, 4=4} // get 4
{2=2, 3=3, 4=4, 5=5} // put 5
{2=2, 3=3, 5=5, 4=4} // put 4
{3=3, 5=5, 4=4, 6=6} // put 6
|
可见, 每次的 get 和 put 操作, 都会造成序列中的重排序, 最近使用的元素在末尾, 最近最少使用的元素在头部, 当容量超过限制时会移出最近最少使用的元素.
LruCache 的构造
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public class LruCache<K, V> {
// 构造时就初始化的一个 LinkedHashMap
private final LinkedHashMap<K, V> map;
private int size; /* 记录当前缓存占用的内存大小 */
private int maxSize; /* 最多能缓存的内存大小 */
private int putCount; /* 记录 put 调用的次数 */
private int createCount; /* 记录 create 调用的次数 */
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;
// 初始容量为0, 扩容系数为 0.75, 排序模式: true 表示按访问排序, false 表示按插入排序, SDK 实现里固定为 ture
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
|
LruCache 插入元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public final V put(K key, V value) {
V previous;
synchronized (this) {
putCount++;
// 内存占用记录增加
size += safeSizeOf(key, value);
// 存入新的值, 并获取 key 对应的旧值
previous = map.put(key, value);
if (previous != null) {
// 如果旧值存在, 就减去对应内存
size -= safeSizeOf(key, previous);
}
}
// 如果 size > maxSize, 就执行丢弃元素, 裁剪内存操作
trimToSize(maxSize);
return previous;
}
|
LurCache 获取缓存
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
|
public final V get(K key) {
V mapValue;
synchronized (this) {
// 从缓存中获取 key 对应的 value, 如果存在就直接返回
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
// 如果缓存中没有, 就尝试创建一个对应对象, 该方法由子类实现, 可以返回 null
V createdValue = create(key);
if (createdValue == null) {
return null;
}
// 如果子类 create 返回了非 null 对象, 就把这个对象返回, 并插入到缓存中
synchronized (this) {
createCount++;
mapValue = map.put(key, createdValue);
// 上面 get 时得到了 null 才会走到这, 怎么在插入时旧值又跑出来了 ?
if (mapValue != null) {
// 这里应该是避免多线程访问时, 在 get 获取为 null 之后, 其他线程插入了对应的值, 所以这里把其他线程插入的值还原回去
map.put(key, mapValue);
} else {
// 如果没有其他插入, 就把新创建的内存占用记账
size += safeSizeOf(key, createdValue);
}
}
...
}
|
以上就是 LruCache 里主要的方法了, 看完也没发现与 LRU 算法有关的东西, 那 LRU 的具体实现肯定就在 LinkedHashMap 里了.
LinkedHashMap 的实现
1
2
3
4
5
6
7
|
// LinkedHashMap 的节点数据结构, 继承自 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);
}
}
|
构造
1
2
3
4
5
6
7
|
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
// accessOrder 决定内部的排序顺序
this.accessOrder = accessOrder;
}
|
获取操作
1
2
3
4
5
6
7
8
9
10
11
|
public V get(Object key) {
Node<K,V> e;
// 调用父类 HashMap 的方法
if ((e = getNode(hash(key), key)) == null)
return null;
// 如果按访问顺序排序为 ture, 则进行重排序
if (accessOrder)
// 将 e 移动到最后
afterNodeAccess(e);
return e.value;
}
|
可以看到, 重点就是 afterNodeAccess 这个方法.
访问 node 之后的排序操作
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
|
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMapEntry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, /* p 指向当前节点 e */
b = p.before, /* b 指向前一个节点 */
a = p.after; /* a 指向后一个节点 */
p.after = null; /* 当前节点 after 置 null */
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
|
Case 1: 访问元素的前后存在元素
Case 1.2: 访问元素的前后存在多个元素
Case 2: 访问元素的后面存在元素, 前面不存在
Case 3: 访问元素的前面存在元素, 后面不存在
这种 case 不会做排序操作, 因为元素已经位于链表尾部了.
在访问元素之后, 通过 afterNodeAccess 排序之后, 被访问的元素就移动到了链表的尾部.
插入操作
LinkedHashMap 的 put 操作是直接调用父类 HashMap 的, HashMap 的 put 操作之后, 被插入的元素将会位于链表的尾部, 然后会调用 afterNodeInsertion, 该方法在 LinkedHashMap 中的实现:
1
2
3
4
5
6
7
8
9
|
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMapEntry<K,V> first;
// 如果 removeEldestEntry 为 true, 则移出头部的元素
// LinkedHashMap 中 removeEldestEntry 默认返回 false
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
|
由于 LinkedHashMap 中 removeEldestEntry 默认返回 false, 所以 LinkedHashMap 的插入操作, 默认不会移出元素, 移出元素的操作实际在 LruCache 中的 trimToSize 实现.
在获取和插入之后, LinkedHashMap 中的元素排列就会是: 最近最多使用的位于尾部, 最近最少使用的位于头部.
LruCache 的 trimToSize
trimToSize 目的在于当缓存大于设置的最大内存时, 会移出最近最少使用到的元素(在 LinkedHashMap 中就是头部的元素):
androidxref 上的源码实现:
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
|
public void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
if (size <= maxSize) {
break;
}
// 该方法会返回 LinkedHashMap 的头节点
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 提供的 LruCache 基于 LinkedHashMap 实现, 利用 LinkedHashMap 会在每次访问元素之后, 将元素移动到序列末尾的特点, 保证了最近最多使用的元素位于尾部, 最近最少使用的元素位于头部.
当缓存占用达到设置的上限时, LruCache 就会移出 LinkedHashMap 中的头节点.
-
LinkedHashMap 扩展 HashMap, 实现了一套双向链表机制, 保证了在元素的移动上和元素的查找上的时间复杂度都为 $ O(1) $.
