谈谈LruCache源码

谈谈LruCache源码


LruCache,首先从名字就可以看出它的功能。作为较为常用的缓存策略,它在日常开发中起到了重要的作用。例如Glide中,它与SoftReference 在Engine类中缓存图片,可以减少流量开销,提升加载图片的效率。在API12时引入android.util.LruCache,然而在API22时对它进行了修改,引入了android.support.v4.util.LruCache。我们在这里分析的是support包里的LruCache


什么是LruCache算法?

Lru(Least Recently Used),也就是最近最少使用算法。它在内部维护了一个LinkedHashMap,在put数据的时候会判断指定的内存大小是否已满。若已满,则会使用最近最少使用算法进行清理。至于为什么要使用LinkedHashMap存储,因为LinkedHashMap内部是一个数组加双向链表的形式来存储数据,也就是说当我们通过get方法获取数据的时候,数据会从队列跑到队头来。反反复复,队尾的数据自然是最少使用到的数据。



image


LruCache如何使用?


初始化

一般来说,我们都是取运行时最大内存的八分之一来作为内存空间,同时还要覆写一个sizeOf的方法。特别需要强调的是,sizeOf的单位必须和内存空间的单位一致。

1
2
3
4
5
6
7
int maxMemory = (int) (Runtime.getRuntime().maxMemory() / 1024);
LruCache<String, Bitmap> cache = new LruCache<String, Bitmap>(maxMemory / 8) {
@Override
protected int sizeOf(@NonNull String key, @NonNull Bitmap value) {
return bitmap.getRowBytes() * bitmap.getHeight() / 1024;
}
};


API

公共方法
final int createCount()返回返回值的次数create(Object)
final void evictAll()清除缓存,调用entryRemoved(boolean, K, V, V)每个删除的条目。
final int evictionCount()返回已被驱逐的值的数量。
final V get(K key)返回key缓存中是否存在的值,还是可以创建的值#create
final int hitCount()返回返回get(K)已存在于缓存中的值的次数。
final int maxSize()对于不覆盖的高速缓存sizeOf(K, V),这将返回高速缓存中的最大条目数。
final int missCount()返回get(K)返回null或需要创建新值的次数。
final V put(K key, V value)缓存valuekey
final int putCount()返回put(K, V)调用的次数。
final V remove(K key)删除条目(key如果存在)。
void resize(int maxSize)设置缓存的大小。
final int size()对于不覆盖的高速缓存sizeOf(K, V),这将返回高速缓存中的条目数。
final Map<K, V> snapshot()返回缓存的当前内容的副本,从最近最少访问到最近访问的顺序排序。
final String toString()
void trimToSize(int maxSize)删除最旧的条目,直到剩余条目的总数等于或低于请求的大小。


LruCache源码分析

我们接下里从构造方法开始为大家进行讲解:

构造函数

1
2
3
4
5
6
7
8
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
} else {
this.maxSize = maxSize;
this.map = new LinkedHashMap(0, 0.75F, true);
}
}

构造函数一共做了两件事。第一节:判断maxSize是否小于等于0。第二件,初始化maxSize和LinkedHashMap。没什么可说的,我们接着往下走。

safeSizeOf(测量元素大小)

1
2
3
4
5
6
7
8
private int safeSizeOf(K key, V value) {
int result = this.sizeOf(key, value);
if (result < 0) {//判空
throw new IllegalStateException("Negative size: " + key + "=" + value);
} else {
return result;
}
}

sizeOf (测量元素大小)

这个方法一定要覆写,否则存不进数据。

1
2
3
protected int sizeOf(@NonNull K key, @NonNull V value) {
return 1;
}

put方法 (增加元素)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
@Nullable
public final V put(@NonNull K key, @NonNull V value) {
if (key != null && value != null) {
Object previous;
synchronized(this) {
++this.putCount;//count为LruCahe的缓存个数,这里加一
this.size += this.safeSizeOf(key, value);//加上这个value的大小
previous = this.map.put(key, value);//存进LinkedHashMap中
if (previous != null) {//如果之前存过这个key,则减掉之前value的大小
this.size -= this.safeSizeOf(key, previous);
}
}

if (previous != null) {
this.entryRemoved(false, key, previous, value);
}

this.trimToSize(this.maxSize);//进行内存判断
return previous;
} else {
throw new NullPointerException("key == null || value == null");
}
}

在synchronized代码块里,进入的就是一次插入操作。我们往下,俺老孙定眼一看,似乎trimToSize这个方法有什么不寻常的地方?

trimToSize (判断是否内存溢出)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void trimToSize(int maxSize) {
while(true) {//这是一个无限循环,目的是为了移除value直到内存空间不溢出
Object key;
Object value;
synchronized(this) {
if (this.size < 0 || this.map.isEmpty() && this.size != 0) {//如果没有分配内存空间,抛出异常
throw new IllegalStateException(this.getClass().getName() + ".sizeOf() is reporting inconsistent results!");
}

if (this.size <= maxSize || this.map.isEmpty()) {//如果小于内存空间,just so so~
return;
}
//否则将使用Lru算法进行移除
Entry<K, V> toEvict = (Entry)this.map.entrySet().iterator().next();
key = toEvict.getKey();
value = toEvict.getValue();
this.map.remove(key);
this.size -= this.safeSizeOf(key, value);
++this.evictionCount;//回收次数+1
}

this.entryRemoved(true, key, value, (Object)null);
}
}

这个TrimToSize方法的作用在于判断内存空间是否溢出。利用无限循环,将一个一个的最少使用的数据给剔除掉。

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
@Nullable
public final V get(@NonNull K key) {
if (key == null) {
throw new NullPointerException("key == null");
} else {
Object mapValue;
synchronized(this) {
mapValue = this.map.get(key);
if (mapValue != null) {
++this.hitCount;//命中次数+1,并且返回mapValue
return mapValue;
}

++this.missCount;//未命中次数+1
}
/*
如果未命中,会尝试利用create方法创建对象
create需要自己实现,若未实现则返回null
*/
V createdValue = this.create(key);
if (createdValue == null) {
return null;
} else {
synchronized(this) {
//创建了新对象之后,再将其添加进map中,与之前put方法逻辑基本相同
++this.createCount;
mapValue = this.map.put(key, createdValue);
if (mapValue != null) {
this.map.put(key, mapValue);
} else {
this.size += this.safeSizeOf(key, createdValue);
}
}

if (mapValue != null) {
this.entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
this.trimToSize(this.maxSize);//每次加入数据时,都需要判断一下是否溢出
return createdValue;
}
}
}
}

create方法 (尝试创造对象)

1
2
3
4
@Nullable
protected V create(@NonNull K key) {
return null;//这个方法需要自己实现
}

get方法和create方法的注释已经写在了代码上,这里逻辑同样不是很复杂。但是我们需要注意的是map的get方法,既然LinkedHashMap能实现Lru算法,那么它的内部一定不简单!

LinkedHashMap的get方法

1
2
3
4
5
6
7
8
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;
}

LinkedHashMap中,首先进行了判断,是否找到该元素,没找到则返回null。找到则调用afterNodeAccess方法。

LinkedHashMap的afterNodeAccess方法

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
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMapEntry<K,V> last;
//accessOrder为true 且当前节点不是尾节点 则按访问顺序排序
if (accessOrder && (last = tail) != e) {
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
//下面是排序过程
p.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;
}
}

原来如此!LinkedHashMap在这个方法中实现了按访问顺序排序,这也就是为什么我们的LruCache底层是使用的LinkedHashMap作为数据结构。

主要方法已经讲完了 ,接下里我们就看看其他方法吧。

remove (移除元素)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
@Nullable
public final V remove(@NonNull K key) {
if (key == null) {//判空
throw new NullPointerException("key == null");
} else {
Object previous;
synchronized(this) {
previous = this.map.remove(key);//根据key移除value
if (previous != null) {
this.size -= this.safeSizeOf(key, previous);//减掉value的大小
}
}

if (previous != null) {
this.entryRemoved(false, key, previous, (Object)null);
}

return previous;
}
}

evictAll方法(移除所有元素)

1
2
3
public final void evictAll() {
this.trimToSize(-1);//移除掉所有的value
}

其他方法

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
public final synchronized int size() {
return this.size;//当前内存空间的size
}

public final synchronized int maxSize() {
return this.maxSize;//内存空间最大的size
}

public final synchronized int hitCount() {
return this.hitCount;//命中个数
}

public final synchronized int missCount() {
return this.missCount;//未命中个数
}

public final synchronized int createCount() {
return this.createCount;//创建Value的个数
}

public final synchronized int putCount() {
return this.putCount;//put进去的个数
}

public final synchronized int evictionCount() {
return this.evictionCount;//移除个数
}

public final synchronized Map<K, V> snapshot() {
return new LinkedHashMap(this.map);//创建LinkedHashMap
}

public final synchronized String toString() {//toString
int accesses = this.hitCount + this.missCount;
int hitPercent = accesses != 0 ? 100 * this.hitCount / accesses : 0;
return String.format(Locale.US, "LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]", this.maxSize, this.hitCount, this.missCount, hitPercent);
}

最后

有了这篇文章,相信大家对LruCache的工作原理已经很清楚了吧!有什么不对的地方希望大家能够指正。学无止境,大家一起加油吧。

0%