1. 概述
由于 Android 為每個(gè)進(jìn)程分配的可用內(nèi)存空間都是有限的，如果進(jìn)程使用的內(nèi)存超過了所分配的限制就會(huì)出現(xiàn)內(nèi)存溢出問題。同時(shí)，如果應(yīng)用每使用一個(gè)資源都需要從本地或網(wǎng)絡(luò)加載，這無疑會(huì)影響應(yīng)用的性能，為了既能保證應(yīng)用性能又能避免內(nèi)存溢出，就出現(xiàn)內(nèi)存緩存技術(shù)。
所謂內(nèi)存緩存技術(shù)指的是把一些資源緩存在內(nèi)存中，如果需要加載資源，首先到內(nèi)存中去尋找，尋找到的話就直接使用，否則去本地或者網(wǎng)絡(luò)去尋找。其中最重要的是內(nèi)存緩存技術(shù)要有一個(gè)合適的緩存策略,即根據(jù)什么策略把緩存中的資源刪除，以保證緩存空間始終在一個(gè)合理的范圍內(nèi)。
LruCache是Android提供的一個(gè)標(biāo)準(zhǔn)的基于LRU，最近最少使用算法的緩存技術(shù)，它的使用方法已經(jīng)在其他博文里簡單介紹過了，這里主要介紹它的實(shí)現(xiàn)機(jī)制。
2. LruChche 實(shí)現(xiàn)原理
LRU的全稱是Least Recently Used，最近最少使用，LruCache的實(shí)現(xiàn)原理就是在其內(nèi)部維護(hù)一個(gè)隊(duì)列，內(nèi)部元素按照最近使用時(shí)間進(jìn)行排序，隊(duì)首是最近最常使用的元素，隊(duì)尾是最近最少使用的元素，當(dāng)緩存中元素達(dá)到最大數(shù)量后，把最近最少使用的元素即隊(duì)尾元素從緩存隊(duì)列中移除，從而保證緩存始終在一個(gè)合理內(nèi)存范圍內(nèi)。
下圖簡單演示LruCache的過程：
從這個(gè)演示圖中可以發(fā)現(xiàn)：
- 每次新入隊(duì)的元素總是位于隊(duì)首；
- 隊(duì)尾元素是最久沒有使用過的元素；
- 當(dāng)隊(duì)列中的元素被再次使用后，就會(huì)把該元素重新插入到隊(duì)首。
LruCache中使用LinkedHashMap來保存元素，而 LinkedHashMap內(nèi)部使用雙向鏈表來實(shí)現(xiàn)這樣的一個(gè) LRU隊(duì)列，其具體實(shí)現(xiàn)在這里就不詳細(xì)描述了，大家只要了解這點(diǎn)就可以了。
3. LruCache 關(guān)鍵實(shí)現(xiàn)
內(nèi)存緩存技術(shù)中最關(guān)鍵的實(shí)現(xiàn)主要包含三部分：
- 如何把元素加入緩存
- 如何從緩存中獲取元素
- 如何在緩存滿時(shí)刪除元素
3.1 LruCache 的初始化
在詳細(xì)講解LruCache的三個(gè)關(guān)鍵實(shí)現(xiàn)部分前，首先要知道LruCache 的初始化。
首先看下是如何在代碼里使用LruCache的：
int maxMemory = (int) Runtime.getRuntime().maxMemory();
LruCache<String, Bitmap> mCache = new LruCache<String, Bitmap>(maxMemory / 4) {
@Override
protected int sizeOf(String key, Bitmap value) {
return value.getByteCount();
}
};
在這段示例代碼里，創(chuàng)建了一個(gè)LruCache示例并重寫了sizeOf方法。重寫sizeOf方法是因?yàn)樗鼤?huì)被用來判斷緩存的當(dāng)前大小是否已經(jīng)達(dá)到了預(yù)定義的緩存大小，如果超過就需要從中移除最久沒有使用的元素。默認(rèn)情況下sizeOf返回的時(shí)候元素個(gè)數(shù)，所以如果在創(chuàng)建LruCache時(shí)指定的緩存中的元素個(gè)數(shù)而非內(nèi)存空間就可以不重新sizeOf方法。
現(xiàn)在來看在創(chuàng)建LruCache的時(shí)候到底發(fā)生了什么，其構(gòu)造函數(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;
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
從構(gòu)造函數(shù)里發(fā)現(xiàn)，除了根據(jù)傳入的參數(shù)確定了緩存的最大內(nèi)存空間(也可能是元素?cái)?shù)量)外，還定義了一個(gè)LinkedHashMap并把其中的第三個(gè)參數(shù)設(shè)置為true，LinkedHashMap的構(gòu)造函數(shù)如下：
/**
* Constructs an empty <tt>LinkedHashMap</tt> instance with the
* specified initial capacity, load factor and ordering mode.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @param accessOrder the ordering mode - <tt>true</tt> for
* access-order, <tt>false</tt> for insertion-order
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
其中，參數(shù)分別是初始容量, 負(fù)載因子和排序方式，如果accessOrder被設(shè)置為true就表示是按照訪順序進(jìn)行排序的，這也就保證了LruCache中的原生是按照訪問順序排序的。
所以在LruCache的初始化過程中，一方面確定了緩存的最大空間，另一方面利用LinkedHashMap實(shí)現(xiàn)了LRU隊(duì)列。
3.2 LruCache 緩存元素
要使用LruCache，首先需要把需要緩存的資源加入到LruCache緩存空間，在LruCache實(shí)現(xiàn)這一功能的是put接口，來看下是如何實(shí)現(xiàn)的：
/**
* 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++;
// 更新當(dāng)前緩存大小并把元素加入緩存隊(duì)列，新元素位于隊(duì)首。
size += safeSizeOf(key, value);
previous = map.put(key, value);
// 如果是更新已存在元素，在增加新元素大小后，需要減去酒元素大小，以保持緩存大小正確。
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
// 如果是更新元素，需要發(fā)出通知，默認(rèn) entryRemoved 沒有實(shí)現(xiàn)。
if (previous != null) {
entryRemoved(false, key, previous, value);
}
// 檢查緩存大小是否達(dá)到限制，如果達(dá)到需要移除最久沒使用的元素。
trimToSize(maxSize);
return previous;
}
put方法整體邏輯比較簡單，就是把新元素放在隊(duì)首，更新當(dāng)前緩存大小，并使用trimToSize 來保證當(dāng)前緩存大小沒有超過限制，其代碼如下：
/**
* @param maxSize the maximum size of the cache before returning. May be -1
* to evict even 0-sized elements.
*/
private 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;
}
// BEGIN LAYOUTLIB CHANGE
// get the last item in the linked list.
// This is not efficient, the goal here is to minimize the changes
// compared to the platform version.
Map.Entry<K, V> toEvict = null;
for (Map.Entry<K, V> entry : map.entrySet()) {
toEvict = entry;
}
// END LAYOUTLIB CHANGE
if (toEvict == null) {
break;
}
// 找到對(duì)穩(wěn)元素，即最久沒有使用的元素，并移除之。
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
// 移除元素后更新當(dāng)前大小
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
trimToSize的邏輯也很簡單明了，在緩存隊(duì)列中找到最近最久沒有使用的元素，把它從隊(duì)列中移除，直到緩存大小滿足限制。由于最近最久沒有使用的元素一直位于隊(duì)尾，所以只要找到隊(duì)尾元素并把它移除即可。
3.3 LruCache 取元素
緩存元素的最終目的是為了方便后續(xù)能從緩存中更快地獲取需要元素，LruCache獲取元素是通過get方法來實(shí)現(xiàn)的，其代碼如下：
/**
* 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.
*/
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
// 從緩存中找到元素后返回，并更新到隊(duì)首。
mapValue = map.get(key);
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.
*/
// 如果找不到元素就調(diào)用 create 去創(chuàng)建一個(gè)元素，默認(rèn) create 返回 null.
V createdValue = create(key);
if (createdValue == null) {
return null;
}
synchronized (this) {
createCount++;
mapValue = map.put(key, createdValue);
// 新創(chuàng)建的元素和隊(duì)列中已存在元素沖突，這個(gè)已存在元素是在 create的過程中新加入隊(duì)列的。
if (mapValue != null) {
// There was a conflict so undo that last put
map.put(key, mapValue);
} else {
// 加入新創(chuàng)建元素后需要更新緩存大小
size += safeSizeOf(key, createdValue);
}
}
if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
// 檢查緩存空間
trimToSize(maxSize);
return createdValue;
}
}
get方法的邏輯也是很簡潔明了的，就是直接從緩存隊(duì)列中獲取元素，如果查找到就返回并更新元素位置到隊(duì)首，如果查不到就自己創(chuàng)建一個(gè)加入隊(duì)列，但考慮到多線程的情況，加入隊(duì)列是需要考慮沖突情況。
3.4 LruCache 移除元素
雖然LruCache可以在緩存空間達(dá)到限制是自動(dòng)把最近最久沒使用的元素從隊(duì)列中移除，但也可以主動(dòng)去移除元素，使用的方法就是remove，其代碼如下：
/**
* Removes the entry for {@code key} if it exists.
*
* @return the previous value mapped by {@code key}.
*/
public final V remove(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V previous;
synchronized (this) {
// 找到元素后移除，并更新緩存大小。
previous = map.remove(key);
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, null);
}
return previous;
}
remove的邏輯更加簡單，到緩存隊(duì)列中找到元素，移除，并更新緩存大小即可。
4. 總結(jié)
本文主要分析了LruCache的內(nèi)部實(shí)現(xiàn)機(jī)制，由于LruCache本身的代碼量比較小，分析起來難度也不大，但養(yǎng)成分析源碼的習(xí)慣所代表的意義更大,讓我們一起 Reading The Fucking Source Code ！
