简介
我们在做图片三级缓存时，内存缓存为了防止内存溢出，导致APP崩溃，使用LruCache<K, V>来管理内存数据，内部由最近最少使用算法实现，将内存控制在一定的大小内，超出最大值时会自动回收。
原理
初始化时指定最大内存大小，google原生OS的默认值是16M，但是各个厂家的OS会对这个值进行修改，有的128 有的256等等。可使用val maxMemory = Runtime.getRuntime().maxMemory()来动态获取手机的内存大小，一般控制在总内存的1/8。
初始化
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);
}
new LruCache<String,Bitmap>((int) maxMemory/8)
添加数据
当有新数据添加时，往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) {
putCount++;
size += safeSizeOf(key, value);
previous = map.put(key, value);
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, value);
}
trimToSize(maxSize);
return previous;
}
判断内存集合是否超过最大限制；如果超过，将链表头部的对象也就是近期最少用到的数据移除，直到内存大小满足最大初始值。
private 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;
}
Map.Entry<K, V> toEvict = null;
for (Map.Entry<K, V> entry : map.entrySet()) {
toEvict = entry;
}
if (toEvict == null) {
break;
}
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
获取数据
获取数据时，有数据时，直接返回数据，没有数据就调用create返回自定义的或者null
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
V createdValue = create(key);
if (createdValue == null) {
return null;
}
synchronized (this) {
createCount++;
mapValue = map.put(key, createdValue);
if (mapValue != null) {
map.put(key, mapValue);
} else {
size += safeSizeOf(key, createdValue);
}
}
if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
trimToSize(maxSize);
return createdValue;
}
}
初始化LinkedHashMap accessOrder传值为true，调用afterNodeAccess；
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
当accessOrder的值为true，且e不是尾节点，将e移到链表的尾端；
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
LruCache 局部同步锁
在 get, put, trimToSize, remove 四个方法里的 entryRemoved 方法都不在同步块里，因为 entryRemoved 回调的参数都属于方法域参数，不会线程不安全。
总结
通过以上源码的分析，可以知道新增数据和获取缓存时，数据都会移动到链表尾端，而当前内存大于设置最大内存的大小时，会移除链表头端的数据，与hitCount++的数量毫无关系。
面试题：最近最少使用算法是使用次数多的还是最近的数据先被移除？
