1 LruCache介紹
1.1 常見的緩存算法
- FIFO(First In First Out)：先進先出
- LRU(Least Recently Used)：最近最少使用
- LFU(Least Frequently Used)：最不經(jīng)常使用
舉個例子，比如我們的緩存對象順序為：(隊尾)EDDCBABAEA(隊頭)券盅。如果這時候來了個A断盛，這時候要淘汰一個對象末早，如果是FIFO汁针，這時候就會淘汰的E页屠；如果是LRU的話，這時候就會淘汰的D烁巫，因為D被使用過之后接下來再也沒有被使用過了淳衙；如果是LFU的話蘑秽，那么淘汰的就是C了，因為C就被使用過一次箫攀。
1.2 LruCache是什么肠牲？
LRU (Least Recently Used) 的意思就是近期最少使用算法，它的核心思想就是會優(yōu)先淘汰那些近期最少使用的緩存對象靴跛。當(dāng)訪問一個數(shù)據(jù)時吼具，這個數(shù)據(jù)就會被移動到數(shù)據(jù)隊列的頭部(經(jīng)常用到的數(shù)據(jù))横辆，當(dāng)數(shù)據(jù)添加到緩存滿時讲衫，隊列尾部的數(shù)據(jù)(也就是不常用到的數(shù)據(jù))會被刪除并被回收伴箩。
在Android中采用LRU算法的常用緩存有兩種：LruCache和DisLruCache，分別用于實現(xiàn)內(nèi)存緩存和硬盤緩存绝葡，其核心思想都是LRU緩存算法深碱。
1.3 LruCache使用
Android 提供的 LruCache 基于 LinkedHashMap 實現(xiàn)，利用 LinkedHashMap 會在每次訪問元素之后藏畅，將元素移動到序列末尾的特點敷硅，保證了最近最多使用的元素位于尾部，最近最少使用的元素位于頭部愉阎，當(dāng)緩存占用達到設(shè)置的上限時绞蹦，LruCache 就會移出 LinkedHashMap 中的頭節(jié)點。
LruCache雖然使用了LinkedHashMap榜旦，但是實現(xiàn)的思路并不一樣。Java需要重寫removeEldestEntry來判斷是否刪除節(jié)點；而Android需要重寫LruCache的sizeOf，返回當(dāng)前節(jié)點的大小，Android會根據(jù)這個大小判斷是否超出了限制，進行調(diào)用trimToSize方法清除多余的節(jié)點。
我們就以圖片緩存為例：
int maxMemory = (int) (Runtime.getRuntime().totalMemory()/1024);
int cacheSize = maxMemory/8;
mMemoryCache = new LruCache<String,Bitmap>(cacheSize){
@Override
protected int sizeOf(String key, Bitmap value) {
return value.getRowBytes()*value.getHeight()/1024;
}
};
① 設(shè)置LruCache緩存的大小，一般為當(dāng)前進程可用容量的1/8窍蓝。
② 重寫sizeOf方法，計算出要緩存的每張圖片的大小。
注意：緩存的總?cè)萘亢兔總€緩存對象的大小所用單位要一致。
1.4 DiskLruCache使用
參考鏈接[2]
2 LruCache源碼
2.1 LruCache 的構(gòu)造
LruCache正是用了LinkedHashMap的accessOrder=true構(gòu)造參數(shù)實現(xiàn)LRU訪問順序。
public class LruCache<K, V> {
private final LinkedHashMap<K, V> map;
/** Size of this cache in units. Not necessarily the number of elements. */
private int size; //當(dāng)前cache的大小
private int maxSize; //cache最大大小
private int putCount; //put的次數(shù)
private int createCount; //create的次數(shù)
private int evictionCount; //驅(qū)逐剔除的次數(shù)
private int hitCount; //命中的次數(shù)
private int missCount; //未命中次數(shù)
//...省略...
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
//將LinkedHashMap的accessOrder設(shè)置為true來實現(xiàn)LRU順序
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
}
2.2 LruCache 插入元素
public final V put(K key, V value) {
V previous;
synchronized (this) {
putCount++;
// 內(nèi)存占用記錄增加
size += safeSizeOf(key, value);
// 存入新的值, 并獲取 key 對應(yīng)的舊值
previous = map.put(key, value);
if (previous != null) {
//如果已有緩存對象，則緩存大小的值需要剔除這個舊的大小
size -= safeSizeOf(key, previous);
}
}
//entryRemoved()是個空方法您没，可以自行實現(xiàn)
if (previous != null) {
entryRemoved(false, key, previous, value);
}
// 如果 size > maxSize, 就執(zhí)行丟棄元素, 裁剪內(nèi)存操作
trimToSize(maxSize);
return previous;
}
trimToSize()方法不斷地刪除LinkedHashMap中隊頭的元素压状，即近期最少訪問的镣丑，直到緩存小于最大值慨蛙。
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為空通砍，則不需要再刪除緩存對象，跳出循環(huán)
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);
}
}
2.3 LurCache 獲取緩存
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
//獲取對應(yīng)的緩存對象
//LinkedHashMap的get()方法會實現(xiàn)將訪問的元素更新到隊列尾部的功能
mapValue = map.get(key);
//mapValue不為空表示命中讽营，hitCount+1并返回mapValue對象
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++; //未命中
}
/*
* 如果未命中虎忌，則試圖創(chuàng)建一個對象，這里create方法默認返回null,并沒有實現(xiàn)創(chuàng)建對象的方法橱鹏。
* 如果需要事項創(chuàng)建對象的方法可以重寫create方法膜蠢。因為圖片緩存時內(nèi)存緩存沒有命中會去
* 文件緩存中去取或者從網(wǎng)絡(luò)下載，所以并不需要創(chuàng)建莉兰，下面的就不用看了挑围。
*/
V createdValue = create(key);
if (createdValue == null) {
return null;
}
//假如創(chuàng)建了新的對象，則繼續(xù)往下執(zhí)行
synchronized (this) {
createCount++;
//將createdValue加入到map中糖荒，并且將原來鍵為key的對象保存到mapValue
mapValue = map.put(key, createdValue);
if (mapValue != null) {
// There was a conflict so undo that last put
//如果mapValue不為空杉辙，則撤銷上一步的put操作。
map.put(key, mapValue);
} else {
//加入新創(chuàng)建的對象之后需要重新計算size大小
size += safeSizeOf(key, createdValue);
}
}
if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
//每次新加入對象都需要調(diào)用trimToSize方法看是否需要回收
trimToSize(maxSize);
return createdValue;
}
}
參考資料：
[1] Android LruCache 緩存機制實現(xiàn)原理
[2] Android DiskLruCache完全解析捶朵，硬盤緩存的最佳方案 ★
[3] 源碼分析 - LRUCache緩存實現(xiàn)原理 ★
