LruCache 是什么东西？
LRU 咋一看这么熟悉，操作系统里面内存管理，页面置换时替换算法之一，英文全拼为Least Recently Used 以为最近最少使用，简单来说，就是替换掉最老的数据。其核心思想为如果数据最近被访问过，那么将来被访问的几率也更高。另外一个比较简单的算法是 FIFO，First In First Out 先进先出，就是淘汰最先使用的，也就是说留下最近使用的，看似这两个很像，实际上区别还是很大的，当缓存命中时，LRU会将元素移到队首，而FIFO不会变 我觉得这是对于 LRU 和 FIFO 比较正确的定义，就实现方式来说，FIFO 相对简单些
前世今生
// 很干净，没有父类（Object 除外）
public class LruCache<K, V> {}
使用场景
主要是用于缓存数据的场景，节约内存，比如图片的缓存
实现原理大白话
他的实现还是很简单，很清晰的，使用一个 LinkedHashMap 作为数据存储结构，你使用这个东西的时候可以当一个 Key-Value 内存数据库使用。只不过，它主要是为了缓存，当数据量达到阈值值，会根据LRU删除数据，那有的同学可能会问，为什么要删啊？其实这就是使用它原因，删掉一部分可能不使用的数据，节约出宝贵的内存，要是你不管内存的话，那就另当别论了
存储数据格式
head -> node -> node -> node -> node -> node -> tail
node = <Key, Value>
源码分析
属性
// 数据存储
private final LinkedHashMap<K, V> map;
/** Size of this cache in units. Not necessarily the number of elements. */
private int size;
// 阈值设置，超过阈值就会抛弃
private int maxSize;
/**
* 下面的统计数据主要是用来评估的
*/
// 调用 put 的次数
private int putCount;
// 创建 key 的次数
private int createCount;
// 淘汰数据 的次数
private int evictionCount;
// 命中的次数
private int hitCount;
// 未命中的次数
private int missCount;
方法
构造函数
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
// 在这里初始化 cache ，默认大小为 0
// true 这个很关键，代表 access-order，
// true 则链表的顺序是为访问顺序，刚好符合LRU的特性
// false 则 插入顺序
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
put 存数据
/**
* 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) {
// 注意不允许为空，HashMap 是可以允许你 Key Value 为空的
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
// 锁住自身的对象，线程安全
synchronized (this) {
putCount++;
// 计算存入数据的大小
size += safeSizeOf(key, value);
// 存入数据，如果 key 重复，则返回旧数据
// 具体实现可查看 HashMap 的putVal函数
previous = map.put(key, value);
// 如果有旧数据，自然要更新大小
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
// entryRemoved 空方法，可重写
if (previous != null) {
entryRemoved(false, key, previous, value);
}
// 调整大小
trimToSize(maxSize);
return previous;
}
调整大小函数
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;
}
// remove the head
// head -> next -> next -> tail
// 获取队首数据
Map.Entry<K, V> toEvict = map.eldest();
if (toEvict == null) {
break;
}
key = toEvict.getKey();
value = toEvict.getValue();
// 删除
map.remove(key);
// 减小
size -= safeSizeOf(key, value);
// 擦除加1
evictionCount++;
}
// 可重写，监听清除
entryRemoved(true, key, value, null);
}
}
get 刚开始的时候你可能会困惑，说好的 lru 怎么没看到
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
// 拿到数据直接返回了
// 更换节点的工作，LinkedHashMap 帮我们做了
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
/*
* Attempt to create a value. This may take a long time, and the map
* may be different when create() returns. If a conflicting value was
* added to the map while create() was working, we leave that value in
* the map and release the created value.
*/
// 缓存失效
// 或者不存在key，同样 create 也是空方法，使用者根据自己需求去实现
V createdValue = create(key);
if (createdValue == null) {
return null;
}
// 就是一个 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;
}
}
看完这几个函数，大概知道了原理
再来看一个非常重要的函数，内存大小的计算，通常也是需要使用者自己重写
private int safeSizeOf(K key, V value) {
int result = sizeOf(key, value);
if (result < 0) {
throw new IllegalStateException("Negative size: " + key + "=" + value);
}
return result;
}
/**
* Returns the size of the entry for {@code key} and {@code value} in
* user-defined units. The default implementation returns 1 so that size
* is the number of entries and max size is the maximum number of entries.
*
* <p>An entry's size must not change while it is in the cache.
*/
// 子类可重写，默认返回1，根据使用情况自己计算
// 扯一句，关于 Java 对象在内存的大小如何计算，请自行去查找
protected int sizeOf(K key, V value) {
return 1;
}
总结
HashMap 是个很重要的东西，下一次我们在慢慢分析
今天跟大家分享了一个很简单的数据结构，也是你可以效仿的对象，还是那句，Read the fucking source code
纯属个人观点，如果有错，欢迎指正。
网友评论