一. LruCache基本原理
LRU全稱為Least Recently Used，即最近最少使用阱高。
由于緩存容量是有限的竞端，當(dāng)有新的數(shù)據(jù)需要加入緩存，但緩存的空閑空間不足的時候贡翘，如何移除原有的部分?jǐn)?shù)據(jù)從而釋放空間用來放新的數(shù)據(jù)？
LRU算法就是當(dāng)緩存空間滿了的時候砰逻，將最近最少使用的數(shù)據(jù)從緩存空間中刪除以增加可用的緩存空間來緩存新數(shù)據(jù)鸣驱。
這個算分的內(nèi)部有一個緩存列表，每當(dāng)一個緩存數(shù)據(jù)被訪問的時候诱渤，這個數(shù)據(jù)就會被提到列表尾部丐巫，每次都這樣的話，列表的頭部數(shù)據(jù)就是最近最不常使用的了勺美，當(dāng)緩存空間不足時递胧，就會刪除列表頭部的緩存數(shù)據(jù)。
二. LruCache的使用
//獲取系統(tǒng)分配給每個應(yīng)用程序的最大內(nèi)存
int maxMemory=(int)(Runtime.getRuntime().maxMemory()/1024);
int cacheSize=maxMemory/8;
private LruCache<String, Bitmap> mMemoryCache;
//給LruCache分配1/8
mMemoryCache = new LruCache<String, Bitmap>(mCacheSize){
//重寫該方法赡茸，來測量Bitmap的大小
@Override
protected int sizeOf(String key, Bitmap value) {
return value.getRowBytes() * value.getHeight()/1024;
}
};
三. LruCache部分源碼解析
LruCache 利用 LinkedHashMap 的一個特性（accessOrder＝true 基于訪問順序）再加上對 LinkedHashMap 的數(shù)據(jù)操作上鎖實現(xiàn)的緩存策略缎脾。
LruCache 的數(shù)據(jù)緩存是內(nèi)存中的。
- 首先設(shè)置了內(nèi)部 LinkedHashMap 構(gòu)造參數(shù) accessOrder=true占卧， 實現(xiàn)了數(shù)據(jù)排序按照訪問順序遗菠。
- LruCache類在調(diào)用get(K key) 方法時联喘，都會調(diào)用LinkedHashMap.get(Object key) 。
- 如上述設(shè)置了 accessOrder=true 后辙纬，調(diào)用LinkedHashMap.get(Object key) 都會通過LinkedHashMap的afterNodeAccess()方法將數(shù)據(jù)移到隊尾豁遭。
- 由于最新訪問的數(shù)據(jù)在尾部，在 put 和 trimToSize 的方法執(zhí)行下贺拣，如果發(fā)生數(shù)據(jù)移除蓖谢，會優(yōu)先移除掉頭部數(shù)據(jù)
1.構(gòu)造方法
/**
* @param maxSize for caches that do not override {@link #sizeOf}, this is
* the maximum number of entries in the cache. For all other caches,
* this is the maximum sum of the sizes of the entries in this cache.
*/
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參數(shù)介紹：
initialCapacity 用于初始化該 LinkedHashMap 的大小。
loadFactor（負(fù)載因子）這個LinkedHashMap的父類 HashMap 里的構(gòu)造參數(shù)譬涡，涉及到擴(kuò)容問題闪幽，比如 HashMap 的最大容量是100，那么這里設(shè)置0.75f的話涡匀，到75的時候就會擴(kuò)容盯腌。
accessOrder,這個參數(shù)是排序模式，true表示在訪問的時候進(jìn)行排序( LruCache 核心工作原理就在此)陨瘩，false表示在插入的時才排序腕够。
2.添加數(shù)據(jù) LruCache.put(K key, V value)
/**
* Caches {@code value} for {@code key}. The value is moved to the head of
* the queue.
*
* @return the previous value mapped by {@code key}.
*/
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++;
//safeSizeOf(key, value)。
//這個方法返回的是1舌劳，也就是將緩存的個數(shù)加1.
// 當(dāng)緩存的是圖片的時候燕少，這個size應(yīng)該表示圖片占用的內(nèi)存的大小，所以應(yīng)該重寫里面調(diào)用的sizeOf(key, value)方法
size += safeSizeOf(key, value);
//向map中加入緩存對象,若緩存中已存在蒿囤，返回已有的值，否則執(zhí)行插入新的數(shù)據(jù)崇决，并返回null
previous = map.put(key, value);
//如果已有緩存對象材诽，則緩存大小恢復(fù)到之前
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
//entryRemoved()是個空方法，可以自行實現(xiàn)
if (previous != null) {
entryRemoved(false, key, previous, value);
}
trimToSize(maxSize);
return previous;
}
- 開始的時候確實是把值放入LinkedHashMap恒傻，不管超不超過你設(shè)定的緩存容量脸侥。
- 根據(jù) safeSizeOf方法計算 此次添加數(shù)據(jù)的容量是多少，并且加到size 里 盈厘。
- 方法執(zhí)行到最后時睁枕，通過trimToSize()方法 來判斷size 是否大于maxSize。
可以看到put()方法并沒有太多的邏輯沸手，重要的就是在添加過緩存對象后外遇，調(diào)用 trimToSize()方法，來判斷緩存是否已滿契吉，如果滿了就要刪除近期最少使用的數(shù)據(jù)跳仿。
2.trimToSize(int maxSize)
/**
* Remove the eldest entries until the total of remaining entries is at or
* below the requested size.
*
* @param maxSize the maximum size of the cache before returning. May be -1
* to evict even 0-sized elements.
*/
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小于最大緩存捐晶，不需要再刪除緩存對象菲语，跳出循環(huán)
if (size <= maxSize) {
break;
}
//在緩存隊列中查找最近最少使用的元素妄辩，若不存在，直接退出循環(huán)山上，若存在則直接在map中刪除眼耀。
Map.Entry<K, V> toEvict = map.eldest();
if (toEvict == null) {
break;
}
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
size -= safeSizeOf(key, value);
//回收次數(shù)+1
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
/**
* Returns the eldest entry in the map, or {@code null} if the map is empty.
*
* Android-added.
*
* @hide
*/
public Map.Entry<K, V> eldest() {
Entry<K, V> eldest = header.after;
return eldest != header ? eldest : null;
}
trimToSize()方法不斷地刪除LinkedHashMap中隊首的元素，即近期最少訪問的佩憾，直到緩存大小小于最大值哮伟。
3.LruCache.get(K key)
/**
* Returns the value for {@code key} if it exists in the cache or can be
* created by {@code #create}. If a value was returned, it is moved to the
* head of the queue. This returns null if a value is not cached and cannot
* be created.
* 通過key獲取緩存的數(shù)據(jù)，如果通過這個方法得到的需要的元素鸯屿，那么這個元素會被放在緩存隊列的尾部澈吨，
*
*/
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
//從LinkedHashMap中獲取數(shù)據(jù)。
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
/*
* 正常情況走不到下面
* 因為默認(rèn)的 create(K key) 邏輯為null
* 走到這里的話說明實現(xiàn)了自定義的create(K key) 邏輯寄摆，比如返回了一個不為空的默認(rèn)值
*/
/*
* Attempt to create a value. This may take a long time, and the map
* may be different when create() returns. If a conflicting value was
* added to the map while create() was working, we leave that value in
* the map and release the created value.
* 譯：如果通過key從緩存集合中獲取不到緩存數(shù)據(jù)谅辣，就嘗試使用creat(key)方法創(chuàng)造一個新數(shù)據(jù)。
* create(key)默認(rèn)返回的也是null婶恼，需要的時候可以重寫這個方法桑阶。
*/
V createdValue = create(key);
if (createdValue == null) {
return null;
}
//如果重寫了create(key)方法，創(chuàng)建了新的數(shù)據(jù)勾邦，就講新數(shù)據(jù)放入緩存中蚣录。
synchronized (this) {
createCount++;
mapValue = map.put(key, createdValue);
if (mapValue != null) {
// There was a conflict so undo that last put
map.put(key, mapValue);
} else {
size += safeSizeOf(key, createdValue);
}
}
if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
trimToSize(maxSize);
return createdValue;
}
}
當(dāng)調(diào)用LruCache的get()方法獲取集合中的緩存對象時，就代表訪問了一次該元素眷篇，將會更新隊列萎河，保持整個隊列是按照訪問順序排序,這個更新過程就是在LinkedHashMap中的get()方法中完成的。
總結(jié)
- LruCache中維護(hù)了一個集合LinkedHashMap蕉饼，該LinkedHashMap是以訪問順序排序的虐杯。
- 當(dāng)調(diào)用put()方法時，就會在結(jié)合中添加元素昧港，并調(diào)用trimToSize()判斷緩存是否已滿擎椰，如果滿了就用LinkedHashMap的迭代器刪除隊首元素，即近期最少訪問的元素创肥。
- 當(dāng)調(diào)用get()方法訪問緩存對象時达舒，就會調(diào)用LinkedHashMap的get()方法獲得對應(yīng)集合元素，同時會更新該元素到隊尾叹侄。
