本文介绍的内容有
- LruCache算法思想介绍
- v4包中LruCache中源码解析
LruCache算法思想介绍
- LruCache（Least Recently Used）算法的核心思想就是最近最少使用算法
- 最近最少使用算法
规则：
1.限定存储表大小
2.添加或者使用某个元素式 ，这个元素排序到表头
3.添加新元素的时候，如果表已满，直接去除表尾元素
image.png
v4包中LruCache中源码解析
- 建议要先简单了解一下LinkedHashMap 数据结构,了解其特点和优势。
下面是v4包中LruCache这个类的所有代码
public class LruCache<K, V> {
// 存放数据的集合 - LinkedHashMap -> 内部结构是封装的双向链表
private final LinkedHashMap<K, V> map;
// 当前缓存大小
private int size;
// 最大缓存大小
private int maxSize;
// 插入元素的次数
private int putCount;
// 元素丢失后(根据key没找到value),如果我们重写了oncreate方法并创建成功的次数
private int createCount;
// 元素回收的次数
private int evictionCount;
// 调用元素的次数 -> 根据key找到value
private int hitCount;
// 元素丢失的次数 -> 根据key没找到value
private int missCount;
// 初始化 传入最大size
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
} else {
this.maxSize = maxSize;
//创建LinkedHashMap，后面的增删改查操作实际就是对这个map的操作
// true 按照访问做排序 -> 插入和访问都做排序
this.map = new LinkedHashMap(0, 0.75F, true);
}
}
// 重置最大size
public void resize(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
} else {
synchronized(this) {
this.maxSize = maxSize;
}
// 到方法中再介绍
this.trimToSize(maxSize);
}
}
// 根据key查找元素
@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;
return mapValue;
}
// 表示根据key没有找到元素
++this.missCount;
}
// 没有找到元素 就去创建元素 ，我们可以重写这个方法
V createdValue = this.create(key);
if (createdValue == null) {
// 创建失败（没有重写create方法并返回值） -> 返回null
return null;
} else {
// 表示创建成功
synchronized(this) {
// 成功 +1
++this.createCount;
// 因为是刚创建出来的，所以要放入map中
// 加入后，如果key之前就存在，就返回上次key的value，如果不存在就返回null
mapValue = this.map.put(key, createdValue);
if (mapValue != null) {
//加入旧的value
this.map.put(key, mapValue);
} else {
// 计算大小
this.size += this.safeSizeOf(key, createdValue);
}
}
if (mapValue != null) {
// 如果旧的值存在 ，维持旧的值不变，那么新创建的createdValue就没有用，调用这个方法处理掉
this.entryRemoved(false, key, createdValue, mapValue);
// 返回旧值
return mapValue;
} else {
// 到方法中再介绍
this.trimToSize(this.maxSize);
// 返回新创建的值
return createdValue;
}
}
}
}
// 添加值
@Nullable
public final V put(@NonNull K key, @NonNull V value) {
if (key != null && value != null) {
Object previous;
synchronized(this) {
//做了一次添加操作
++this.putCount;
// 当前size累加
this.size += this.safeSizeOf(key, value);
// 查找 返回旧值或者null
previous = this.map.put(key, value);
if (previous != null) {
// 如果旧值存在 ，当前size减去旧值大小
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");
}
}
// 这个方法就是通过对当前size和maxSize的循环比较，一直删除元素，直到符合条件
public void trimToSize(int maxSize) {
while(true) {
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()) {
return;
}
// 缓存超出最大值，执行删除元素的操作
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;
}
this.entryRemoved(true, key, value, (Object)null);
}
}
// 删除操作
@Nullable
public final V remove(@NonNull K key) {
if (key == null) {
throw new NullPointerException("key == null");
} else {
Object previous;
synchronized(this) {
// 根据key移除元素 返回value
previous = this.map.remove(key);
if (previous != null) {
// value不等于null ，重新计算大小
this.size -= this.safeSizeOf(key, previous);
}
}
if (previous != null) {
// 需要重写的自定义操作
this.entryRemoved(false, key, previous, (Object)null);
}
return previous;
}
}
// 需要重写的自定义操作 比如对旧值的资源回收
protected void entryRemoved(boolean evicted, @NonNull K key, @NonNull V oldValue, @Nullable V newValue) {
}
// 重写方法 查找不到值的时候 可以按照这个来创建
@Nullable
protected V create(@NonNull K key) {
return null;
}
// 返回元素大小
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;
}
}
// 可重写 返回元素实际大小
protected int sizeOf(@NonNull K key, @NonNull V value) {
return 1;
}
public final void evictAll() {
this.trimToSize(-1);
}
public final synchronized int size() {
return this.size;
}
public final synchronized int maxSize() {
return this.maxSize;
}
public final synchronized int hitCount() {
return this.hitCount;
}
public final synchronized int missCount() {
return this.missCount;
}
public final synchronized int createCount() {
return this.createCount;
}
public final synchronized int putCount() {
return this.putCount;
}
public final synchronized int evictionCount() {
return this.evictionCount;
}
public final synchronized Map<K, V> snapshot() {
return new LinkedHashMap(this.map);
}
public final synchronized String 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);
}
}
网友评论