LruCache源码分析

简介

Lru(Least recently used),中文为最近最少使用。Lru算法的基本原则是,如果一个数据在最近的一段时间内没有被访问,那么这个数据将被访问的可能性也会比较低。在一定的空间中,如果空间被占用满,那么这个一段时间内没有被访问的数据讲会被弃用、抛弃。LruCache就是基于此思想的缓存管理类。Lrucache位于android.util包中,本文基于android platform 27源码进行分析。

LinkedHashMap

在分析LruCache源代码之前,先来了解一下LinkedHashMapLinkedHashMap中使用双向列表来维护元素的顺序,这个顺序可以是插入顺序也可以是访问顺序LinkedHashMap有这样一个构造方法

1
2
3
4
5
6
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder; // the ordering mode - <tt>true</tt> for access-order, <tt>false</tt> for insertion-order
}

accessOrder的参数意义为,为true时,顺序为访问顺序,fasle时为插入顺序,所谓访问顺序就是最近访问的元素会被放到列表的尾部,源代码如下

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 V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}

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

accessOrder为true时候的访问顺序就非常符合Lru的原则。

LruCache

  1. LruCache的源代码不多,非常好理解。先看唯一的构造方法
    1
    2
    3
    4
    5
    6
    7
    8
    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); // initialCapacity = 0, loadFactory = 0.75, accessOrder = true
    // initialCapacity为0时,会分配初始大小为1的hashmap
    }

构造方法中传入缓存的大小,然后初始化一个LinkedHashMap实例,第三个参数为true

  1. put方法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    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); // 获取一个value暂用的空间的大小,计算目前的缓存大小
    previous = map.put(key, value); // 如果key的hashcode相同,则会覆盖原先的,并且返回原先的value
    if (previous != null) {
    size -= safeSizeOf(key, previous); // 缓存大小减去原先的 protected int sizeOf(K key, V value) { return 1; }
    }
    }

    if (previous != null) {
    entryRemoved(false, key, previous, value); // 通知方法,在是用LruCache是可以重写。通知原先的value被替换
    }

    trimToSize(maxSize); // 调整大小,如果现在的大小大于了设定的maxSize,就要根据lru原则剔除数据
    return previous;
    }

其中调用safeSizeOf 来获取一个value暂用的空间大小。最终会调用 sizeOf方法,默认返回1,一般在使用LruCache时,都会重写这个方法,返回一个数据正确的占用空间。

  1. 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
    25
    26
    27
    28
    29
    public 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) { // 如果当前大小小于等于了最大值,则跳出循环
    break;
    }

    Map.Entry<K, V> toEvict = map.eldest(); // 获取LinkedHashMap链表头的元素, public Map.Entry<K, V> eldest() { return head;}
    if (toEvict == null) {
    break;
    }

    key = toEvict.getKey();
    value = toEvict.getValue();
    map.remove(key);
    size -= safeSizeOf(key, value);
    evictionCount++;
    }

    entryRemoved(true, key, value, null); // 通知数据被剔除
    }
    }

如果当前的缓存大小大于了最大值,则需要调用eldest方法获取最近最少的使用的元素,也就是链表头的数据,并且删除,直到当前大小小于等于最大值或者没有元素

LruCache的基本使用

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 class LruCacheActivity extends BaseActivity {
private static final String TAG = "LruCacheActivity";

private LruCache<String, String> mLruCache = new LruCache<String, String>(10) { // 10个字节

@Override
protected int sizeOf(String key, String value) {
return value.getBytes().length;
}

@Override
protected void entryRemoved(boolean evicted, String key, String oldValue, String newValue) {
Logger.d("剔除或者替换,key = %s, oldValue = %s, newValue = %s", key, oldValue, newValue);
}
};

@Override
protected void onCreate(@Nullable Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
initializeActivity(R.layout.module_function_layout_lru_activity);
getSupportActionBar().setDisplayHomeAsUpEnabled(true);
}

public void addItem(View v) {
mLruCache.put(Math.random() + "", "test");
}
}

示例代码

https://github.com/jiahuanyu/android-example-code