LruCache源码思考

LruCache是内存缓存数据存储的经典方案,该存储结构通过删除最近最少使用的数据,以使最常用数据发挥更有效的作用。

LruCache的特点:

  1. 最大数据存储容量的限制;
  2. 按照数据的访问顺序排序;
  3. 最近最少使用的数据的管理;
  4. 良好的灵活性。

源码来源:Android API 25 Platform

最大数据存储的限制

最大数据存储的限制是Lru算法开始发挥作用的起点,当数据容量超过设置的最大数据容量时,Lru算法开始发挥作用,删除最近最少使用的数据,直到低于设置的最大容量。

最大数据设置的灵活性:

  • 在创建LruCache对象时,设置默认的最大值;

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    	/**
    * @param maxSize for caches that do not override {@link #sizeOf}, this is
    * the maximum number of entries in the cache. For all other caches,
    * this is the maximum sum of the sizes of the entries in this cache.
    */
    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);
    }
  • 向外暴露接口设置最大值

    一旦最大值变化,重新对已存储的数据大小进行检验,若当前存储的数据大小超过新设置的最大值,则精简缓存.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
        /**
    * Sets the size of the cache.
    *
    * @param maxSize The new maximum size.
    */
    public void resize(int maxSize) {
    if (maxSize <= 0) {
    throw new IllegalArgumentException("maxSize <= 0");
    }
    // 支持线程安全
    synchronized (this) {
    this.maxSize = maxSize;
    }
    // 真正的缓存精简由该方法实现,以上做安全校验。
    trimToSize(maxSize);
    }

数据的存储顺序

在创建LruCache对象时,直接初始化了LinkedHashMap的数据结构来存储数据,并按照访问顺序来进行排序。

1
2
3
...
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
...

关于LinkedHashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
	/**
* Constructs an empty <tt>LinkedHashMap</tt> instance with the
* specified initial capacity, load factor and ordering mode.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @param accessOrder the ordering mode - <tt>true</tt> for
* access-order, <tt>false</tt> for insertion-order
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
  1. 通过链表实现数据的有序存储;

  2. accessOrder确定了链表中数据的排序方式:

    false:按照数据的插入顺序存储;

    true:按照数据的访问顺序存储,最近访问的数据放到链表的末端;若在遍历链表前,没有数据的访问,则按照插入时的顺序遍历。

    访问排序的实现

    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
    // 该方法的最终目的是:把最近访问的元素放到链表最后;
    // e:最近访问的元素
    void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMapEntry<K,V> last;
    // 排序前条件判断:1.是访问排序;2.最后一个元素不是我们要插入的元素
    if (accessOrder && (last = tail) != e) {
    LinkedHashMapEntry<K,V> p =
    (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
    // 1. 重置p节点的尾节点;
    p.after = null;
    // 2. 判断p的头节点是否是链表头节点;
    if (b == null)
    head = a;
    else
    b.after = a;
    // 3. 判断p的尾节点是否是链表的尾节点;
    if (a != null)
    a.before = b;
    else
    last = b;
    // 4. 将p节点连接到链表的尾节点;
    if (last == null)
    head = p;
    else {
    p.before = last;
    last.after = p;
    }
    // 5. 将p节点赋予到尾节点;
    tail = p;
    ++modCount;
    }
    }

最近最少使用的数据的删除

Q:哪个元素是最近最少使用的元素?

A:按照访问排序的实现,访问排序会将最近访问的元素放在链表的底部,那头部的节点就是最近最少使用的元素。

Q:删除最近最少使用的元素的时机?

A: 1. 当插入新元素,链表的大小超过了设置的最大容量时;

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
	/**
* Caches {@code value} for {@code key}. The value is moved to the head of
* the queue.
*
* @return the previous value mapped by {@code key}.
*/
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);
previous = map.put(key, value);
if (previous != null) {
// 减小被替换元素的大小。
size -= safeSizeOf(key, previous);
}
}
// 通知链表中的元素被删除(得到删除的通知后,我们可以针对被删除的元素做很多事情:释放资源等)
if (previous != null) {
entryRemoved(false, key, previous, value);
}
// 插入元素后,检测是否超过了最大存储空间。
trimToSize(maxSize);
return previous;
}
  1. 手动调用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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
	/**
* Remove the eldest entries until the total of remaining entries is at or
* below the requested size.
*
* @param maxSize the maximum size of the cache before returning. May be -1
* to evict even 0-sized elements.
*/
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!");
}
// size最小是0,maxSize可能 < 0(清空列表),因此有必要再对toEvict是否为空进行判断;
if (size <= maxSize) {
// 直到当前空间大小小于设置的最大值,则退出循环;
break;
}
// 获取最近最少使用的元素(核心)
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);
}
}

良好的灵活性

  • 数据结构采用范型,实现多类型的数据存储;
  • 通过复写sizeOf实现元素大小的计算可自定义;
  • 通过复写create实现空value时的可自定义;
  • 通过复写entryRemoved实现被删除元素的可监听性;
  • 通过resize接口实现最大存储空间的可定制性;
  • 通过snapshot获取当前链表的快照;
  • 通过toString可简单查看获取缓存元素时的击中率。

从单个元素进入链表的之后的整个周期内,元素的清除和替换我们都可以观察到变化;甚至在获取元素为空时,我们都可以创建新的元素返回;从单个元素到整个链表,再到击中率/失败率的统计,都具有完善的体系。LruCache虽然代码量很小,但具有优秀的灵活性。

0%