Android 缓存机制 LRUCache
程序员文章站
2022-06-19 10:56:58
...
LRUCache
- 1.Android 的缓存中不管是内存缓存和磁盘缓存都用到了LruCache,LruCache的核心思想就是LRU(Least Recently Used)算法
LRU 算法
- LRU(Least Recently Used)直面翻译过来:最近最少使用,就是淘汰旧数据的策略,保留最近访问过的数据。如果需要加载新数据但空间不足的情况下,会按照最近访问时间排序,将最老的数据淘汰掉。
辅助知识
-
LinkedHashMap
- HashMap我们很熟悉了,LinkedHashMap 是HashMap的子类,可以理解为是:HashMap+LinkedList,一个有序的HashMap。
- 通过维护所有item的双向链表,保证了元素的顺序。该迭代顺序可以是插入顺序或者是访问顺序。迭代顺序在构造时可以指定。
LinkedHashMap 排序模式
/**
* initialCapacity 初始容量
* loadFactor 达到该百分比就扩容Map
* 排序模式:true为访问顺序 false为插入顺序
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
- 访问顺序,当插入10个数据后(0,1,2,3,4,5,6,7,8,9),这时候如果对第3个数据进行访问/操作,该数据会被排在队列尾部(0,1,3,4,5,6,7,8,9,2)
- 插入顺序,当插入10个数据后(0,1,2,3,4,5,6,7,8,9),这时候如果对第3个数据进行访问/操作,该数据位置不会产生变动(0,1,2,3,4,5,6,7,8,9)
LRUCache源码
- 1、 从构造看起,构造并没有多余的东西,初始化了一个LinkedHashMap,和 maxSize。这里我们看到LinkedHashMap中传的第三个参数为true,那么其排序模式为访问模式。
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);
}
// 返回最旧的数据
public Map.Entry<K, V> eldest() {
Entry<K, V> eldest = header.after;
return eldest != header ? eldest : null;
}
- 2、put() 增
- a.有则覆盖,无则put进map
- b.size 计数
- c.trimToSize() 刷新数据,移除超过maxSize数据
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 ++ 增大缓存大小
size += safeSizeOf(key, value);
previous = map.put(key, value);
if (previous != null) {
// size-- 如果已有了,恢复增加的
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
// 无逻辑,自行实现
entryRemoved(false, key, previous, value);
}
// LRU 核心方法
trimToSize(maxSize);
return previous;
}
//移除超过maxSize数据
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) {
// while 结束
break;
}
//获取最旧的数据
Map.Entry<K, V> toEvict = map.eldest();
if (toEvict == null) {
// while 结束
break;
}
key = toEvict.getKey();
value = toEvict.getValue();
// 移除该最旧的数据
map.remove(key);
// size-- 更新size
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
- 3、get() 获取
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
// 查找,并根据访问排序的规则,该key的数据将被放置到map队列末尾
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
// 尝试新建一个(不明觉厉)
V createdValue = create(key);
if (createdValue == null) {
return null;
}
synchronized (this) {
createCount++;
// 并加到map中
mapValue = map.put(key, createdValue);
if (mapValue != null) {
//如果冲突了,把映射的mapValue,put进去
map.put(key, mapValue);
} else {
// size++
size += safeSizeOf(key, createdValue);
}
}
if (mapValue != null) {
// 又释放掉了
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
// 刷新map,移除超size的数据
trimToSize(maxSize);
return createdValue;
}
}
- 3、remove 移除
public final V remove(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V previous;
synchronized (this) {
// 移除
previous = map.remove(key);
if (previous != null) {
// size --
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, null);
}
return previous;
}
总结
- 1.LRUCache 利用LinkedHashMap对数据进行访问排序
- 2.对size进行计数,在trimToSize()中从队列首部依次删除超过size的数据
- 3.获取数据时,将该数据置于队列末尾并返回。