LruCache是Android3.1所提供的一个缓存类。主要的算法原理是把最近使用的对象用强引用存储在LinkedHashmap中，并且把最少使用的对象在缓存值达到预设定值之前移除，并提供了get和put方法来完成缓存的获取和添加操作。
LruCache的具体实现
public class MemoryCache implements ICache {
private LruCache<String, String> mMemoryCache;
private EvictedListener mEvictedListener;
public MemoryCache() {
init();
}
public void setEvictedListener(EvictedListener listener) {
this.mEvictedListener = listener;
}
private void init() {
int maxMemory = (int) (Runtime.getRuntime().maxMemory() / 1024);
int cacheSize = maxMemory / 4;
mMemoryCache = new LruCache<String, String>(cacheSize) {
@Override
protected int sizeOf(@NonNull String key, @NonNull String value) {
return value.getBytes().length;
}
@Override
protected void entryRemoved(boolean evicted, @NonNull String key, @NonNull String oldValue, @Nullable String newValue) {
if (evicted) {
if (mEvictedListener != null) {
mEvictedListener.handleEvictEntry(key, oldValue);
}
}
}
};
}
@Override
public String get(String key) {
return mMemoryCache.get(key);
}
@Override
public void put(String key, String value) {
mMemoryCache.put(key, value);
}
@Override
public boolean remove(String key) {
return Boolean.parseBoolean(mMemoryCache.remove(key));
}
public interface EvictedListener {
void handleEvictEntry(String evictKey, String evictValue);
}
}
- 设置LruCache缓存大小，一般为当前进程可用容量的1/8。
- 重写sizeOf方法，计算出每个key下的数据大小。
LruCache的实现原理
LruCache的核心思想很好理解，就是要维护一个缓存对象列表，其中对象列表的排列方式是按照访问顺序实现的，即一直没访问的对象，将放在队尾，即将被淘汰。而最近访问的对象将放在队头，最后被淘汰。
LruCache算法的核心 = LRU算法 + LinkedHashMap数据结构
LRU算法
全称：Least Recently Used，即近期最少使用算法
算法原理：当缓存满时，优先淘汰近期最少使用的缓存对象
采用LRU算法缓存类型：内存缓存(LruCache)，硬盘缓存(DiskLruCache)
LinkedHashMap
简称：数据结构 = 数组+单链表+双向链表，双向链表实现了存储顺序=访问顺序/插入顺序
/**
* LinkedHashMap 构造函数
* 参数accessOrder = true时，存储顺序（遍历顺序） = 外部访问顺序；为false时，存储顺序（遍历顺序） = 插入顺序
**/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
具体例子解释：
当设置为true时
public static final void main(String[] args) {
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(0, 0.75f, true);
map.put(0, 0);
map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
map.put(4, 4);
map.put(5, 5);
map.put(6, 6);
map.get(1);
map.get(2);
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ":" + entry.getValue());
}
}
输出结果：
0:0
3:3
4:4
5:5
6:6
1:1
2:2
即最近访问的最后输出，那就刚好符合LRU缓存算法的思想。
从LruCache源码中可以看出，如何使用LinkedHashMap来实现缓存的添加、删除和获取。
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); //用了LinkedHashMap的访问顺序
}
public final V put(K key, V value) {
//不可为空，否则抛出异常
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {
//插入的缓存对象值加1
putCount++;
//增加已有缓存的大小
size += safeSizeOf(key, value);
//向map中加入缓存对象
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;
}
put方法就是添加缓存对象后，调用trimToSize方法来判断缓存是否已满，如果满了就要删除近期最少使用对象
public void trimToSize(int maxSize) {
//死循环
while (true) {
K key;
V value;
synchronized (this) {
//如果map为空并且缓存size不等于0或者缓存size小于0，抛出异常
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName()
+ ".sizeOf() is reporting inconsistent results!");
}
//如果缓存大小size小于最大缓存，或者map为空，不需要再删除缓存对象，跳出循环
if (size <= maxSize || map.isEmpty()) {
break;
}
//迭代器获取第一个对象，即队尾的元素，近期最少访问的元素
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);
}
}
trimToSize()方法不断地删除LinkedHashMap中队尾的元素，即近期最少访问的，直到缓存大小小于最大值。
public final V get(K key) {
//key为空抛出异常
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
//获取对应的缓存对象
//get()方法会实现将访问的元素更新到队列头部的功能
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
其中LinkedHashMap的get（）方法如下：
public V get(Object key) {
LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
if (e == null)
return null;
//实现排序的关键方法
e.recordAccess(this);
return e.value;
}
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//判断是否是访问排序
if (lm.accessOrder) {
lm.modCount++;
//删除此元素
remove();
//将此元素移动到队列的头部
addBefore(lm.header);
}
}
总结
由此可见LruCache维护了一个LinkedHashMap，该LinkedHashMap是以访问顺序排序的。当调用put()方法是，就会在LinkedHashMap中添加元素，并调用trimToSize（）判断缓存是否已满，如果满了，就调用LinkedHashMap的迭代器删除队尾元素，直到满足内存设定要求。当调用get()方法时，就会调用LinkedHashMap的get（）方法，获取对应集合的元素，同时会更新该元素到对头。
每天多努力那么一点点，积少成多
网友评论