一琳钉、Android中的緩存策略
一般來說菠剩，緩存策略主要包含緩存的添加、獲取和刪除這三類操作鄙煤。如何添加和獲取緩存這個比較好理解晾匠，那么為什么還要刪除緩存呢？這是因為不管是內(nèi)存緩存還是硬盤緩存梯刚，它們的緩存大小都是有限的凉馆。當(dāng)緩存滿了之后，再想其添加緩存，這個時候就需要刪除一些舊的緩存并添加新的緩存澜共。
因此LRU(Least Recently Used)緩存算法便應(yīng)運(yùn)而生向叉，LRU是近期最少使用的算法，它的核心思想是當(dāng)緩存滿時嗦董，會優(yōu)先淘汰那些近期最少使用的緩存對象母谎，有效的避免了OOM的出現(xiàn)。在Android中采用LRU算法的常用緩存有兩種：LruCache和DisLruCache京革，分別用于實現(xiàn)內(nèi)存緩存和硬盤緩存奇唤，其核心思想都是LRU緩存算法。
其實LRU緩存的實現(xiàn)類似于一個特殊的棧匹摇，把訪問過的元素放置到棧頂（若棧中存在咬扇，則更新至棧頂；若棧中不存在則直接入棧）来惧，然后如果棧中元素數(shù)量超過限定值冗栗，則刪除棧底元素（即最近最少使用的元素）。詳細(xì)算法實現(xiàn)如下圖：
1.新數(shù)據(jù)壓入到棧頂供搀；
2.每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪問）隅居，則將數(shù)據(jù)移到棧頂；
3.當(dāng)棧滿的時候葛虐，將棧底的數(shù)據(jù)丟棄胎源。
舉個例子演示一下：
二、LruCache的使用
LruCache是Android 3.1所提供的一個緩存類屿脐，所以在Android中可以直接使用LruCache實現(xiàn)內(nèi)存緩存涕蚤。而DisLruCache目前在Android 還不是Android SDK的一部分，但Android官方文檔推薦使用該算法來實現(xiàn)硬盤緩存的诵。
講到LruCache不得不提一下LinkedHashMap万栅，因為LruCache中Lru算法的實現(xiàn)就是通過LinkedHashMap來實現(xiàn)的。LinkedHashMap繼承于HashMap西疤，它使用了一個雙向鏈表來存儲Map中的Entry順序關(guān)系烦粒，這種順序有兩種，一種是LRU順序代赁，一種是插入順序扰她，這可以由其構(gòu)造函數(shù)public LinkedHashMap(int initialCapacity,float loadFactor, boolean accessOrder)的最后一個參數(shù)accessOrder來指定。所以芭碍，對于get徒役、put、remove等操作窖壕，LinkedHashMap除了要做HashMap做的事情忧勿，還做些調(diào)整Entry順序鏈表的工作杉女。LruCache中將LinkedHashMap的順序設(shè)置為LRU順序來實現(xiàn)LRU緩存，每次調(diào)用get(也就是從內(nèi)存緩存中取圖片)鸳吸，則將該對象移到鏈表的尾端宠纯。調(diào)用put插入新的對象也是存儲在鏈表尾端，這樣當(dāng)內(nèi)存緩存達(dá)到設(shè)定的最大值時层释，將鏈表頭部的對象（近期最少用到的）移除。關(guān)于LinkedHashMap詳解請前往：理解LinkedHashMap
LruCache使用示例
LruCache的使用非常簡單快集，我們就以圖片緩存為例：
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)前進(jìn)程可用容量的1/8。
② 重寫sizeOf方法个初，計算出要緩存的每張圖片的大小乖寒。
注意：緩存的總?cè)萘亢兔總€緩存對象的大小所用單位要一致。
LruCache的實現(xiàn)原理
LruCache的核心思想很好理解院溺，就是要維護(hù)一個緩存對象列表楣嘁，其中對象列表的排列方式是按照訪問順序?qū)崿F(xiàn)的，即一直沒訪問的對象珍逸，將放在隊尾逐虚，即將被淘汰。而最近訪問的對象將放在隊頭谆膳，最后被淘汰叭爱。如下圖所示：
那么這個隊列到底是由誰來維護(hù)的，前面已經(jīng)介紹了是由LinkedHashMap來維護(hù)漱病。
而LinkedHashMap是由數(shù)組+雙向鏈表的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)的买雾。其中雙向鏈表的結(jié)構(gòu)可以實現(xiàn)訪問順序和插入順序，使得LinkedHashMap中的
/**
* Constructs a new {@code LinkedHashMap} instance with the specified
* capacity, load factor and a flag specifying the ordering behavior.
*
* @param initialCapacity
*? ? ? ? ? ? the initial capacity of this hash map.
* @param loadFactor
*? ? ? ? ? ? the initial load factor.
* @param accessOrder
*? ? ? ? ? ? {@code true} if the ordering should be done based on the last
*? ? ? ? ? ? access (from least-recently accessed to most-recently
*? ? ? ? ? ? accessed), and {@code false} if the ordering should be the
*? ? ? ? ? ? order in which the entries were inserted.
*/
public LinkedHashMap(
? ? ? ? int initialCapacity, float loadFactor, boolean accessOrder) {
? ? super(initialCapacity, loadFactor);
? ? init();
? ? this.accessOrder = accessOrder;
}
其中accessOrder設(shè)置為true則為訪問順序杨帽，為false漓穿，則為插入順序。
以具體例子解釋注盈，當(dāng)設(shè)置為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);? ? //訪問1
? ? map.get(2);? ? //訪問2
? ? for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
? ? ? ? System.out.println(entry.getKey() + ":" + entry.getValue());
? ? }
}
輸出結(jié)果如下：
0:0
3:3
4:4
5:5
6:6
1:1
2:2
即最近訪問的對象會被放到隊尾晃危，然后最后輸出，那么這就正好滿足的LRU緩存算法的思想当凡∩胶Γ可見LruCache巧妙實現(xiàn)，就是利用了LinkedHashMap的這種數(shù)據(jù)結(jié)構(gòu)沿量。
下面我們在LruCache源碼中具體看看浪慌，怎么應(yīng)用LinkedHashMap來實現(xiàn)緩存的添加，獲得和刪除的朴则。
LruCache源碼分析
我們先看看成員變量有哪些：
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ù)
? ? //...省略...
}
構(gòu)造函數(shù)如下权纤，可以看到LruCache正是用了LinkedHashMap的accessOrder=true構(gòu)造參數(shù)實現(xiàn)LRU訪問順序：
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);
}
put方法
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++;? ? //插入次數(shù)加1
? ? ? ? size += safeSizeOf(key, value);? ? //更新緩存的大小
? ? ? ? previous = map.put(key, value);
? ? ? ? //如果已有緩存對象，則緩存大小的值需要剔除這個舊的大小
? ? ? ? if (previous != null) {
? ? ? ? ? ? size -= safeSizeOf(key, previous);
? ? ? ? }
? ? }
? ? //entryRemoved()是個空方法汹想，可以自行實現(xiàn)
? ? if (previous != null) {
? ? ? ? entryRemoved(false, key, previous, value);
? ? }
? ? //調(diào)整緩存大小(關(guān)鍵方法)
? ? trimToSize(maxSize);
? ? return previous;
}
可以看到put()方法并沒有什么難點(diǎn)外邓，重要的就是在添加過緩存對象后，調(diào)用trimToSize()方法古掏，來判斷緩存是否已滿损话，如果滿了就要刪除近期最少使用的算法。
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為空，則不需要再刪除緩存對象庞萍，跳出循環(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);
? ? }
}
trimToSize()方法不斷地刪除LinkedHashMap中隊頭的元素恋博，即近期最少訪問的，直到緩存大小小于最大值私恬。
當(dāng)調(diào)用LruCache的get()方法獲取集合中的緩存對象時债沮，就代表訪問了一次該元素，將會更新隊列本鸣，保持整個隊列是按照訪問順序排序秦士。這個更新過程就是在LinkedHashMap中的get()方法中完成的。
我們先看LruCache的get()方法永高。
get方法
//LruCache的get()方法
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++;? ? //未命中
? ? }
? ? /*
? ? * 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.
? ? * 如果未命中，則試圖創(chuàng)建一個對象命爬，這里create方法默認(rèn)返回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;
? ? }
}
其中LinkedHashMap的get()方法如下：
//LinkedHashMap中的get方法
public V get(Object key) {
? ? Node<K,V> e;
? ? if ((e = getNode(hash(key), key)) == null)
? ? ? ? return null;
? ? //實現(xiàn)排序的關(guān)鍵方法
? ? if (accessOrder)
? ? ? ? afterNodeAccess(e);
? ? return e.value;
}
調(diào)用的afterNodeAccess()方法將該元素移到隊尾异剥，保證最后才刪除，如下：
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;
? ? ? ? }
? ? ? ? //當(dāng)前節(jié)點(diǎn)p移動到尾部之后絮重，尾部指針指向當(dāng)前節(jié)點(diǎn)
? ? ? ? tail = p;
? ? ? ? ++modCount;
? ? }
}
由此可見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)集合元素，同時會更新該元素到隊尾姨蟋。
以上便是LruCache實現(xiàn)的原理辣吃，理解了LinkedHashMap的數(shù)據(jù)結(jié)構(gòu)就能理解整個原理。如果不懂芬探，可以先看看LinkedHashMap的具體實現(xiàn)。
參考資料
