簡介
我們在做圖片三級緩存時(shí)羹呵，內(nèi)存緩存為了防止內(nèi)存溢出，導(dǎo)致APP崩潰瓷们，使用LruCache<K, V>來管理內(nèi)存數(shù)據(jù)业栅，內(nèi)部由最近最少使用算法實(shí)現(xiàn)，將內(nèi)存控制在一定的大小內(nèi)谬晕，超出最大值時(shí)會(huì)自動(dòng)回收碘裕。
原理
初始化時(shí)指定最大內(nèi)存大小，google原生OS的默認(rèn)值是16M攒钳，但是各個(gè)廠家的OS會(huì)對這個(gè)值進(jìn)行修改帮孔，有的128 有的256等等〔怀牛可使用val maxMemory = Runtime.getRuntime().maxMemory()來動(dòng)態(tài)獲取手機(jī)的內(nèi)存大小文兢，一般控制在總內(nèi)存的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)
添加數(shù)據(jù)
當(dāng)有新數(shù)據(jù)添加時(shí)焕檬，往LinkedHashMap里面添加數(shù)據(jù)存儲(chǔ)到鏈表尾端姆坚，如果之前存在則移除之前的數(shù)據(jù)，添加完成之后計(jì)算是否超過最大內(nèi)存实愚。
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;
}
判斷內(nèi)存集合是否超過最大限制兼呵；如果超過，將鏈表頭部的對象也就是近期最少用到的數(shù)據(jù)移除腊敲，直到內(nèi)存大小滿足最大初始值击喂。
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);
}
獲取數(shù)據(jù)
獲取數(shù)據(jù)時(shí)，有數(shù)據(jù)時(shí)碰辅，直接返回?cái)?shù)據(jù)懂昂，沒有數(shù)據(jù)就調(diào)用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，調(diào)用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;
}
當(dāng)accessOrder的值為true忍法，且e不是尾節(jié)點(diǎn)，將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 四個(gè)方法里的 entryRemoved 方法都不在同步塊里，因?yàn)?entryRemoved 回調(diào)的參數(shù)都屬于方法域參數(shù)勉失，不會(huì)線程不安全羹蚣。
總結(jié)
通過以上源碼的分析，可以知道新增數(shù)據(jù)和獲取緩存時(shí)乱凿，數(shù)據(jù)都會(huì)移動(dòng)到鏈表尾端顽素，而當(dāng)前內(nèi)存大于設(shè)置最大內(nèi)存的大小時(shí)咽弦，會(huì)移除鏈表頭端的數(shù)據(jù)，與hitCount++的數(shù)量毫無關(guān)系胁出。
面試題：最近最少使用算法是使用次數(shù)多的還是最近的數(shù)據(jù)先被移除型型？
