關(guān)于Android的三級(jí)緩存，其中主要的就是內(nèi)存緩存和硬盤緩存。這兩種緩存機(jī)制的實(shí)現(xiàn)都應(yīng)用到了LruCache算法，今天我們就從使用到源碼解析，來徹底理解Android中的緩存機(jī)制。
一、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í)，會(huì)優(yōu)先淘汰那些近期最少使用的緩存對(duì)象。采用LRU算法的緩存有兩種：LrhCache和DisLruCache，分別用于實(shí)現(xiàn)內(nèi)存緩存和硬盤緩存，其核心思想都是LRU緩存算法。
二、LruCache的使用
LruCache是Android 3.1所提供的一個(gè)緩存類，所以在Android中可以直接使用LruCache實(shí)現(xiàn)內(nèi)存緩存。而DisLruCache目前在Android 還不是Android SDK的一部分，但Android官方文檔推薦使用該算法來實(shí)現(xiàn)硬盤緩存。
1.LruCache的介紹
LruCache是個(gè)泛型類，主要算法原理是把最近使用的對(duì)象用強(qiáng)引用（即我們平常使用的對(duì)象引用方式）存儲(chǔ)在 LinkedHashMap 中。當(dāng)緩存滿時(shí)，把最近最少使用的對(duì)象從內(nèi)存中移除，并提供了get和put方法來完成緩存的獲取和添加操作。
2.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è)緩存對(duì)象的大小所用單位要一致。
三、LruCache的實(shí)現(xiàn)原理
LruCache的核心思想很好理解，就是要維護(hù)一個(gè)緩存對(duì)象列表，其中對(duì)象列表的排列方式是按照訪問順序?qū)崿F(xiàn)的，即一直沒訪問的對(duì)象，將放在隊(duì)尾，即將被淘汰。而最近訪問的對(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中的<key,value>對(duì)按照一定順序排列起來。
通過下面構(gòu)造函數(shù)來指定LinkedHashMap中雙向鏈表的結(jié)構(gòu)是訪問順序還是插入順序。
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
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);
map.get(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巧妙實(shí)現(xiàn)，就是利用了LinkedHashMap的這種數(shù)據(jù)結(jié)構(gòu)。
下面我們?cè)贚ruCache源碼中具體看看，怎么應(yīng)用LinkedHashMap來實(shí)現(xiàn)緩存的添加，獲得和刪除的。
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);
}
從LruCache的構(gòu)造函數(shù)中可以看到正是用了LinkedHashMap的訪問順序。
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) {
//插入的緩存對(duì)象值加1
putCount++;
//增加已有緩存的大小
size += safeSizeOf(key, value);
//向map中加入緩存對(duì)象
previous = map.put(key, value);
//如果已有緩存對(duì)象，則緩存大小恢復(fù)到之前
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)，重要的就是在添加過緩存對(duì)象后，調(diào)用 trimToSize()方法，來判斷緩存是否已滿，如果滿了就要?jiǎng)h除近期最少使用的算法。
trimToSize()方法
public void trimToSize(int maxSize) {
//死循環(huán)
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為空，不需要再刪除緩存對(duì)象，跳出循環(huán)
if (size <= maxSize || map.isEmpty()) {
break;
}
//迭代器獲取第一個(gè)對(duì)象，即隊(duì)尾的元素，近期最少訪問的元素
Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
key = toEvict.getKey();
value = toEvict.getValue();
//刪除該對(duì)象，并更新緩存大小
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
trimToSize()方法不斷地刪除LinkedHashMap中隊(duì)尾的元素，即近期最少訪問的，直到緩存大小小于最大值。
當(dāng)調(diào)用LruCache的get()方法獲取集合中的緩存對(duì)象時(shí)，就代表訪問了一次該元素，將會(huì)更新隊(duì)列，保持整個(gè)隊(duì)列是按照訪問順序排序。這個(gè)更新過程就是在LinkedHashMap中的get()方法中完成的。
先看LruCache的get()方法
get()方法
public final V get(K key) {
//key為空拋出異常
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
//獲取對(duì)應(yīng)的緩存對(duì)象
//get()方法會(huì)實(shí)現(xiàn)將訪問的元素更新到隊(duì)列頭部的功能
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
其中LinkedHashMap的get()方法如下：
public V get(Object key) {
LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
if (e == null)
return null;
//實(shí)現(xiàn)排序的關(guān)鍵方法
e.recordAccess(this);
return e.value;
}
調(diào)用recordAccess()方法如下：
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//判斷是否是訪問排序
if (lm.accessOrder) {
lm.modCount++;
//刪除此元素
remove();
//將此元素移動(dòng)到隊(duì)列的頭部
addBefore(lm.header);
}
}
由此可見LruCache中維護(hù)了一個(gè)集合LinkedHashMap，該LinkedHashMap是以訪問順序排序的。當(dāng)調(diào)用put()方法時(shí)，就會(huì)在結(jié)合中添加元素，并調(diào)用trimToSize()判斷緩存是否已滿，如果滿了就用LinkedHashMap的迭代器刪除隊(duì)尾元素，即近期最少訪問的元素。當(dāng)調(diào)用get()方法訪問緩存對(duì)象時(shí)，就會(huì)調(diào)用LinkedHashMap的get()方法獲得對(duì)應(yīng)集合元素，同時(shí)會(huì)更新該元素到隊(duì)頭。
以上便是LruCache實(shí)現(xiàn)的原理，理解了LinkedHashMap的數(shù)據(jù)結(jié)構(gòu)就能理解整個(gè)原理。如果不懂，可以先看看LinkedHashMap的具體實(shí)現(xiàn)。
