综合开发

Android内存缓存LruCache源码解析

微信扫一扫,分享到朋友圈

Android内存缓存LruCache源码解析

LruCache

LruCache是Android提供的基于最近最少使用算法的缓存策略,该策略根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

LruCache的原理是在内部由LinkedHashMap维护了一个队列,队列按照访问时间排序,head访问时间最早,tail访问时间最晚。当队列长度超过设置的最大长度时,则从head开始挨个删除,直到长度符合要求。

LruCache源码解析

从LruCache常用的几个方法入手分析。

  • 构造函数
private final LinkedHashMap<K, V> map;
/** Size of this cache in units. Not necessarily the number of elements. */
private int size;
private int maxSize;
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);
}

LruCache的数据结构就是一个LinkedHashMap,在构造函数中初始化,并指定maxSize,maxSize指的是LinkedHashMap中可以保存的最大条数。

  • put
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); //safeSizeOf用来计算新增的条目的size,默认是1
previous = map.put(key, value);
if (previous != null) { //如果存在旧的数据,减去旧的数据的size
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, value);  //缓存被移除时调用,默认为空实现
}
trimToSize(maxSize);    //将超出maxSize的数据移除
return previous;
}

put方法只是将数据put到LinkedHashMap中,然后计算新的size值,并检查是否超过maxSize,如果超过的话,将队头(最后访问时间最早)的数据依次删除。

  • get
public 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++;
}
//map找不到的话,尝试创建一个,create默认返回null,所以一般情况下只执行到这里就结束了。
V createdValue = create(key);
if (createdValue == null) {
return null;
}
//如果createdValue不为空的话,就put到LinkedHashMap中,如果map中已经有值,就撤销put操作
synchronized (this) {
createCount++;
mapValue = map.put(key, createdValue);
if (mapValue != null) {
// There was a conflict so undo that last put
map.put(key, mapValue);
} else {
size += safeSizeOf(key, createdValue);
}
}
if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
trimToSize(maxSize);
return createdValue;
}
}

get方法先从LinkedHashMap中获取数据,如果存在值则返回。如果不存在值,则调用create方法,如果create方法没有被重写则返回null。如果被重写了,会创建一个createdValue,并put到LinkedHashMap中,如果与原有的值冲突了,就撤销put操作,如果没有冲突,就put到map中,并更新size。

  • 排序

看完LruCache的代码,可以知道,缓存数量超出限制之后,从队头挨个删除。看起来平平无奇,那么LruCache在哪里排序以实现LRU的效果呢。这就需要看一下LinkedHashMap了。

/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMapEntry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMapEntry<K,V> tail;
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);
}
}

LinkedHashMap是双向链表,head保存的是最老的数据,而tail保存的是最年轻的数据。

public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

从上面的代码可以看出来,在put的时候,如果之前不存在当前key,则添加在队尾。如果之前已经存在当前key,替换成新的Value。然后会调用afterNodeAccess。

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, 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;
}
}

在afterNodeAccess中一顿链表的操作,最后把p挪到了队尾。因此,可以确定执行完put方法之后,新的value一定在队尾。再回头看get方法。

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;
}

在get方法中同样通过afterNodeAccess方法将该Node挪到队尾。因此可以实现LinkedHashMap按访问时间进行排序。

美图公司:2019年营收9.779亿元 高级订阅收入同比增长518.1%

上一篇

Java程序员应该知道的20个有用的lib开源库

下一篇

你也可能喜欢

评论已经被关闭。

插入图片

热门栏目

Android内存缓存LruCache源码解析

长按储存图像,分享给朋友