主目錄見：Android高級進(jìn)階知識（這是總目錄索引）
?今天我們來聊聊緩存策略相關(guān)的內(nèi)容迟郎，LruCache應(yīng)該說是三級緩存策略會使用到的內(nèi)存緩存策略痢掠。今天我們就來扒一扒這里面的原理，同時(shí)也溫故溫故我們的數(shù)據(jù)結(jié)構(gòu)方面的知識。
一.目標(biāo)
我們今天講的這個(gè)緩存策略，主要有幾個(gè)目的：
1.了解緩存的策略车海；
2.鞏固數(shù)據(jù)結(jié)構(gòu)相關(guān)的知識；
3.自己能實(shí)現(xiàn)一個(gè)緩存策略隘击。
二.源碼解析
1.緩存策略
要來分析源碼，我們首先要先明白有哪幾種緩存淘汰算法研铆，我們先來復(fù)習(xí)一下：
1.FIFO(First In First Out)：先進(jìn)先出埋同；
2.LRU(Least Recently Used):最近最少使用;
3.LFU(Least Frequently Used):最不經(jīng)常使用。
這些都是什么呢棵红？我們舉個(gè)例子凶赁，比如我們的緩存對象順序?yàn)椋?隊(duì)尾)EDDCBABAEA(隊(duì)頭)，那么如果這時(shí)候來了個(gè)A逆甜，這時(shí)候要淘汰一個(gè)對象虱肄，如果是FIFO，這時(shí)候就會淘汰的E交煞；如果是LRU的話咏窿，這時(shí)候就會淘汰的D，因?yàn)镈被使用過之后接下來再也沒有被使用過了素征；如果是LFU的話集嵌，那么淘汰的就是C了,因?yàn)镃就被使用過一次虑绵。這些就是我們?nèi)齻€(gè)緩存淘汰算法瓷式，我們知道我們的緩存是有限的，所以我們必須在新的對象進(jìn)來的時(shí)候選擇一個(gè)優(yōu)秀的替換策略來替換緩存中的對象渡紫，這樣可以提高緩存的命中率端蛆，進(jìn)而提高我們程序的效率凤粗。
2.LinkedHashMap
我們知道，我們的LRU算法可以用很多方法實(shí)現(xiàn)今豆，最常見的是用鏈表的形式嫌拣，這里的LinkedHashMap就是雙向鏈表實(shí)現(xiàn)的，所以我們的LruCache是用的LinkedHashMap來實(shí)現(xiàn)晚凿，我們首先看下LruCache的成員變量和構(gòu)造函數(shù)：
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;//緩存內(nèi)容大小
private int maxSize;//最大的緩存大小
private int putCount;//put()方法被調(diào)用的次數(shù)
private int createCount;//create()方法被調(diào)用的次數(shù)
private int evictionCount;// 被置換出來的元素的個(gè)數(shù)
private int hitCount;//命中緩存中對象的次數(shù)
private int missCount;//未命中緩存中對象的次數(shù)
/**
* @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;//我們看到這個(gè)最大值自己可以控制
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);//第一個(gè)參數(shù)是初始化容量亭罪，第二個(gè)參數(shù)是加載因子默認(rèn)是0.75，第三個(gè)為訪問順序
}
......
}
我們先來說說初始化容量和加載因子的關(guān)系歼秽，我們這里下來看下HashMap中的構(gòu)造函數(shù)：
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
} else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
initialCapacity = DEFAULT_INITIAL_CAPACITY;
}
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Android-Note: We always use the default load factor of 0.75f.
// This might appear wrong but it's just awkward design. We always call
// inflateTable() when table == EMPTY_TABLE. That method will take "threshold"
// to mean "capacity" and then replace it with the real threshold (i.e, multiplied with
// the load factor).
threshold = initialCapacity;
init();
}
我們看到我們的初始容量為0的話应役，這里會使用默認(rèn)的初始容量，然后如果我們進(jìn)行擴(kuò)容的時(shí)候會用到 float thresholdFloat = capacity * loadFactor即容量*加載因子來進(jìn)行決定擴(kuò)展后的容量，默認(rèn)的加載因子0.75是實(shí)驗(yàn)后的最佳數(shù)據(jù)箩祥。接著我們來看看LinkedHashMap是怎么實(shí)現(xiàn)的LRU算法的院崇，我們先來LinkedHashMap的變量和構(gòu)造函數(shù)：
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
private static final long serialVersionUID = 3801124242820219131L;
private transient LinkedHashMapEntry<K,V> header;
private final boolean accessOrder;
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
......
}
我們看到LinkedHashMap里面主要有LinkedHashMapEntry，這個(gè)是雙向鏈表的一個(gè)節(jié)點(diǎn)有前驅(qū)和后繼袍祖，我們可以來看看這個(gè)LinkedHashMapEntry節(jié)點(diǎn)：
private static class LinkedHashMapEntry<K,V> extends HashMapEntry<K,V> {
// These fields comprise the doubly linked list used for iteration.
LinkedHashMapEntry<K,V> before, after;
LinkedHashMapEntry(int hash, K key, V value, HashMapEntry<K,V> next) {
super(hash, key, value, next);
}
.....
}
我們看到這里的LinkedHashMapEntry繼承的HashMapEntry底瓣，同時(shí)里面有before和after節(jié)點(diǎn)，這是為了擴(kuò)展成雙向鏈表做的準(zhǔn)備蕉陋。我們來看下添加新的節(jié)點(diǎn)的方法最終會調(diào)用到createEntry方法：
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> old = table[bucketIndex];
LinkedHashMapEntry<K,V> e = new LinkedHashMapEntry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
}
看懂這個(gè)方法之前捐凭，我們必須明確一下hashmap的數(shù)據(jù)結(jié)構(gòu)，我們看下下面這個(gè)圖：
我們看到前面會有一個(gè)table數(shù)組用于存放各個(gè)entry鏈表的凳鬓，然后LinkedHashMap又在此基礎(chǔ)上面增加了當(dāng)前節(jié)點(diǎn)上面增加before和after的前驅(qū)和后繼節(jié)點(diǎn)的引用信息茁肠。為了大家更加清楚地知道這個(gè)雙鏈表結(jié)構(gòu)，我們把雙鏈表抽取出來如下：
所以添加一個(gè)新的節(jié)點(diǎn)的時(shí)候會調(diào)用addbefore來添加缩举，這個(gè)方法做的東西就是在頭部增加新的節(jié)點(diǎn)：
具體的代碼在addBefore()方法里面：
private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
這里的existingEntry就是我們的header垦梆。所以我們可以看到新增的節(jié)點(diǎn)被插入到了首節(jié)點(diǎn)前面變成了首節(jié)點(diǎn)。我們剛才看到LruCache構(gòu)造函數(shù)里面LinkedHashMap的初始化的第三個(gè)參數(shù)accessOrder被賦值為true是什么意思呢仅孩？這個(gè)是為了記錄訪問的順序的托猩，如果被訪問過了之后，這里true說明我們要把被訪問過的節(jié)點(diǎn)掉到首節(jié)點(diǎn)去辽慕。具體代碼可以看recordAccess()方法：
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
這個(gè)方法是在get方法中調(diào)用的京腥，我們這里如果accessOrder為true的話，那么我們會先移除訪問節(jié)點(diǎn)鼻百，然后把它添加到首節(jié)點(diǎn)绞旅，說明我這個(gè)節(jié)點(diǎn)剛訪問過。到這里我們已經(jīng)明白了LinkedHashMap的工作原理了温艇，那么我們接下來就來看看LruCache的源碼了因悲。
3.LruCache源碼
熟悉了LinkedHashMap的數(shù)據(jù)結(jié)構(gòu)，我們就很容易知道怎么用這個(gè)來實(shí)現(xiàn)LRU算法了勺爱，我們先來看看LruCache的get()方法的源碼：
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
//現(xiàn)在hashMap中查找有沒有這個(gè)key對應(yīng)的節(jié)點(diǎn)(這個(gè)地方只要是get一次就會把命中的節(jié)點(diǎn)往首節(jié)點(diǎn)排)
mapValue = map.get(key);
if (mapValue != null) {
//如果命中的話那么命中+1晃琳，返回該值
hitCount++;
return mapValue;
}
//如果沒有命中的話那么沒命中+1
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è)值，默認(rèn)是空
V createdValue = create(key);
if (createdValue == null) {//如果不為沒有命名的key創(chuàng)建新值琐鲁，則直接返回
return null;
}
// 接下來是如果用戶重寫了create方法后卫旱，可能會執(zhí)行到
synchronized (this) {
createCount++;//創(chuàng)建的數(shù)量增加
mapValue = map.put(key, createdValue););// 將剛剛創(chuàng)建的值放入map中，返回的值是在map中與key相對應(yīng)的舊值（就是在放入new value前的old value）
if (mapValue != null) {
// There was a conflict so undo that last put
map.put(key, mapValue);//如果不為空围段，說明不需要我們所創(chuàng)建的值顾翼，所以又把返回的值放進(jìn)去
} else {
size += safeSizeOf(key, createdValue);//為空，說明我們更新了這個(gè)key的值奈泪，需要重新計(jì)算大小
}
}
if (mapValue != null) {//上面放入的值有沖突
entryRemoved(false, key, createdValue, mapValue);// 通知之前創(chuàng)建的值已經(jīng)被移除适贸，而改為mapValue
return mapValue;
} else {
trimToSize(maxSize);//沒有沖突時(shí)灸芳，因?yàn)榉湃肓诵聞?chuàng)建的值，大小已經(jīng)有變化拜姿，所以需要修整大小
return createdValue;
}
}
我們看到LruCahe是可能被多個(gè)線程訪問的烙样，所以讀取時(shí)候要適當(dāng)加上鎖機(jī)制，當(dāng)獲取不到key對應(yīng)的value時(shí)候蕊肥，他會調(diào)用create方法谒获，這個(gè)方法默認(rèn)是返回null的，除非我們重寫了create方法壁却，這個(gè)方法并沒有加鎖批狱，所以在創(chuàng)建的過程中有可能其他線程已經(jīng)添加進(jìn)去了這個(gè)值，所以在后面的時(shí)候會進(jìn)行判斷是否已經(jīng)不為空了展东，如果不為空即刪除放入原來的值精耐，沒有沖突就放入新值調(diào)整大小變化。我們來看下最后調(diào)整大小的代碼trimToSize方法：
public void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName()
+ ".sizeOf() is reporting inconsistent results!");
}
if (size <= maxSize) {
break;
}
Map.Entry<K, V> toEvict = map.eldest();
if (toEvict == null) {
break;
}
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
這個(gè)方法我們看到會判斷size<=maxSize不琅锻，如果小于則不用調(diào)整，如果大于了那么我們就會取出最老的Entry向胡，進(jìn)行刪除恼蓬，然后置換的個(gè)數(shù)增加1。然后我們看下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++;
size += safeSizeOf(key, value);
previous = map.put(key, value);
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, value);
}
trimToSize(maxSize);
return previous;
}
我們看到這個(gè)方法不難僵芹，主要的邏輯就是計(jì)算一下放入進(jìn)去值的大小处硬，然后加起來。同樣地拇派，放進(jìn)去map中荷辕，然后看是不是更新舊的值，如果是則把剛才加上的大小再減去件豌，然后刪除舊的值跟maxSize調(diào)整一下總的大小疮方。到這里我們大概已經(jīng)講完LruCache的源碼了，我們也大概了解了整體的設(shè)計(jì)茧彤，其實(shí)我們自己也是可以寫出這樣一套代碼的骡显，主要的還是數(shù)據(jù)結(jié)構(gòu)方面的知識。
總結(jié)：其實(shí)整體的LruCache的實(shí)現(xiàn)并不會非常難曾掂，主要就是數(shù)據(jù)結(jié)構(gòu)的知識惫谤，我們可以根據(jù)這一套思想，我們也可以實(shí)現(xiàn)各種緩存策略珠洗，今天講的這個(gè)主要是內(nèi)存的緩存策略溜歪，到時(shí)我們可以來講講DiskLruCache是磁盤的緩存策略，希望能有所收獲哈许蓖。
