一、Android中的緩存策略
一般來說，緩存策略主要包含緩存的添加、獲取和刪除這三類操作。如何添加和獲取緩存這個(gè)比較好理解，那么為什么還要?jiǎng)h除緩存呢？這是因?yàn)椴还苁莾?nèi)存緩存還是硬盤緩存，它們的緩存大小都是有限的。當(dāng)緩存滿了之后，再想其添加緩存，這個(gè)時(shí)候就需要?jiǎng)h除一些舊的緩存并添加新的緩存。
因此LRU(Least Recently Used)緩存算法便應(yīng)運(yùn)而生，LRU是近期最少使用的算法，它的核心思想是當(dāng)緩存滿時(shí)，會優(yōu)先淘汰那些近期最少使用的緩存對象，有效的避免了OOM的出現(xiàn)。在Android中采用LRU算法的常用緩存有兩種：LruCache和DisLruCache，分別用于實(shí)現(xiàn)內(nèi)存緩存和硬盤緩存，其核心思想都是LRU緩存算法。
其實(shí)LRU緩存的實(shí)現(xiàn)類似于一個(gè)特殊的棧，把訪問過的元素放置到棧頂（若棧中存在，則更新至棧頂；若棧中不存在則直接入棧），然后如果棧中元素?cái)?shù)量超過限定值，則刪除棧底元素（即最近最少使用的元素）。詳細(xì)算法實(shí)現(xiàn)如下圖：
1.新數(shù)據(jù)壓入到棧頂；
2.每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪問），則將數(shù)據(jù)移到棧頂；
3.當(dāng)棧滿的時(shí)候，將棧底的數(shù)據(jù)丟棄。
舉個(gè)例子演示一下：
二、LruCache的使用
LruCache是Android 3.1所提供的一個(gè)緩存類，所以在Android中可以直接使用LruCache實(shí)現(xiàn)內(nèi)存緩存。而DisLruCache目前在Android 還不是Android SDK的一部分，但Android官方文檔推薦使用該算法來實(shí)現(xiàn)硬盤緩存。
講到LruCache不得不提一下LinkedHashMap，因?yàn)長ruCache中Lru算法的實(shí)現(xiàn)就是通過LinkedHashMap來實(shí)現(xiàn)的。LinkedHashMap繼承于HashMap，它使用了一個(gè)雙向鏈表來存儲Map中的Entry順序關(guān)系，這種順序有兩種，一種是LRU順序，一種是插入順序，這可以由其構(gòu)造函數(shù)public LinkedHashMap(int initialCapacity,float loadFactor, boolean accessOrder)的最后一個(gè)參數(shù)accessOrder來指定。所以，對于get、put、remove等操作，LinkedHashMap除了要做HashMap做的事情，還做些調(diào)整Entry順序鏈表的工作。LruCache中將LinkedHashMap的順序設(shè)置為LRU順序來實(shí)現(xiàn)LRU緩存，每次調(diào)用get(也就是從內(nèi)存緩存中取圖片)，則將該對象移到鏈表的尾端。調(diào)用put插入新的對象也是存儲在鏈表尾端，這樣當(dāng)內(nèi)存緩存達(dá)到設(shè)定的最大值時(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方法，計(jì)算出要緩存的每張圖片的大小。
注意：緩存的總?cè)萘亢兔總€(gè)緩存對象的大小所用單位要一致。
LruCache的實(shí)現(xiàn)原理
LruCache的核心思想很好理解，就是要維護(hù)一個(gè)緩存對象列表，其中對象列表的排列方式是按照訪問順序?qū)崿F(xiàn)的，即一直沒訪問的對象，將放在隊(duì)尾，即將被淘汰。而最近訪問的對象將放在隊(duì)頭，最后被淘汰。如下圖所示：
那么這個(gè)隊(duì)列到底是由誰來維護(hù)的，前面已經(jīng)介紹了是由LinkedHashMap來維護(hù)。
而LinkedHashMap是由數(shù)組+雙向鏈表的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)的。其中雙向鏈表的結(jié)構(gòu)可以實(shí)現(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時(shí)：
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
即最近訪問的對象會被放到隊(duì)尾，然后最后輸出，那么這就正好滿足的LRU緩存算法的思想?？梢奓ruCache巧妙實(shí)現(xiàn)，就是利用了LinkedHashMap的這種數(shù)據(jù)結(jié)構(gòu)。
下面我們在LruCache源碼中具體看看，怎么應(yīng)用LinkedHashMap來實(shí)現(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ù)實(shí)現(xiàn)LRU訪問順序：
public LruCache(int maxSize) {
? ? if (maxSize <= 0) {
? ? ? ? throw new IllegalArgumentException("maxSize <= 0");
? ? }
? ? this.maxSize = maxSize;
? ? //將LinkedHashMap的accessOrder設(shè)置為true來實(shí)現(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);
? ? ? ? //如果已有緩存對象，則緩存大小的值需要剔除這個(gè)舊的大小
? ? ? ? if (previous != null) {
? ? ? ? ? ? size -= safeSizeOf(key, previous);
? ? ? ? }
? ? }
? ? //entryRemoved()是個(gè)空方法，可以自行實(shí)現(xiàn)
? ? if (previous != null) {
? ? ? ? entryRemoved(false, key, previous, value);
? ? }
? ? //調(diào)整緩存大小(關(guān)鍵方法)
? ? trimToSize(maxSize);
? ? return previous;
}
可以看到put()方法并沒有什么難點(diǎn)，重要的就是在添加過緩存對象后，調(diào)用trimToSize()方法，來判斷緩存是否已滿，如果滿了就要?jiǎng)h除近期最少使用的算法。
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;
? ? ? ? ? ? }
? ? ? ? ? ? //迭代器獲取第一個(gè)對象，即隊(duì)頭的元素，近期最少訪問的元素
? ? ? ? ? ? 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中隊(duì)頭的元素，即近期最少訪問的，直到緩存大小小于最大值。
當(dāng)調(diào)用LruCache的get()方法獲取集合中的緩存對象時(shí)，就代表訪問了一次該元素，將會更新隊(duì)列，保持整個(gè)隊(duì)列是按照訪問順序排序。這個(gè)更新過程就是在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()方法會實(shí)現(xiàn)將訪問的元素更新到隊(duì)列尾部的功能
? ? ? ? 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)建一個(gè)對象，這里create方法默認(rèn)返回null,并沒有實(shí)現(xiàn)創(chuàng)建對象的方法。
? ? * 如果需要事項(xiàng)創(chuàng)建對象的方法可以重寫create方法。因?yàn)閳D片緩存時(shí)內(nèi)存緩存沒有命中會去
? ? * 文件緩存中去取或者從網(wǎng)絡(luò)下載，所以并不需要?jiǎng)?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)建的對象之后需要重新計(jì)算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;
? ? //實(shí)現(xiàn)排序的關(guān)鍵方法
? ? if (accessOrder)
? ? ? ? afterNodeAccess(e);
? ? return e.value;
}
調(diào)用的afterNodeAccess()方法將該元素移到隊(duì)尾，保證最后才刪除，如下：
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)到尾部之后，尾部指針指向當(dāng)前節(jié)點(diǎn)
? ? ? ? tail = p;
? ? ? ? ++modCount;
? ? }
}
由此可見LruCache中維護(hù)了一個(gè)集合LinkedHashMap，該LinkedHashMap是以訪問順序排序的。當(dāng)調(diào)用put()方法時(shí)，就會在結(jié)合中添加元素，并調(diào)用trimToSize()判斷緩存是否已滿，如果滿了就用LinkedHashMap的迭代器刪除隊(duì)頭元素，即近期最少訪問的元素。當(dāng)調(diào)用get()方法訪問緩存對象時(shí)，就會調(diào)用LinkedHashMap的get()方法獲得對應(yīng)集合元素，同時(shí)會更新該元素到隊(duì)尾。
以上便是LruCache實(shí)現(xiàn)的原理，理解了LinkedHashMap的數(shù)據(jù)結(jié)構(gòu)就能理解整個(gè)原理。如果不懂，可以先看看LinkedHashMap的具體實(shí)現(xiàn)。
參考資料
