Lru算法（Least recently used，最近最少使用），其思想核心是最新操作（添加、读取）的数据，使用频率最高。
算法原理
算法原理图
通常实现是通过链表结构实现
- 链表头部写入数据
- 如果当前缓存数量大于最大缓存书，则删除链表尾部数据
- 读取缓存数据时将该数据移动到链表顶部
LruCache实现
内部数据结构
LruCache 内部创建一个LinkedHashMap永存存数缓存数据，为什么要使用这个类呢？
- LinkedHashMap构造函数
public LinkedHashMap(int initialCapacity, float loadFactor,boolean accessOrder)- initialCapacity 容量
- loadFactor 容量不足时，扩容倍数
- accessOrder false还是基于插入 顺寻排序ture基于访问顺序
LruCache显然是基于访问顺序排序
内部数据结构
内部实现采用LinkedHashMapEntry实现双链表结构，可以记录添加顺序，新增数据添加到双链表的尾部添加和读取数据
执行get和put方法的，条件满足是都会会调用this.recordAccess方法（LinkedHashMap重写了recordAccess方法），以保证访问顺序排序，会将数据插入或者移动到链表的尾部
- 遍历顺序
LinkedHashMap遍历顺序是从头到尾，这样可以保证删除最老的数据
好像与上面的原理图并不一样，不过是添加数据的时候添加到链表尾部，遍历的时候从尾到头遍历实际上效果还是一样的
核心代码
trimToSize是核心代码，详见注解
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 || map.isEmpty()) {
break;
}
//当前缓存已缓存数量大于最大缓存数，遍历获取map中第一个
Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
key = toEvict.getKey();
value = toEvict.getValue();
//删除缓存
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
