【原文位址 LRUcache源碼分析】
LruCache 源碼解析
1. 簡介
LRU 是 Least Recently Used 最近最少使用算法。
曾經，在各大緩存圖檔的架構沒流行的時候。有一種很常用的記憶體緩存技術：SoftReference 和 WeakReference（軟引用和弱引用）。但是走到了 Android 2.3（Level 9）時代，垃圾回收機制更傾向于回收 SoftReference 或 WeakReference 的對象。後來，又來到了 Android3.0，圖檔緩存在内容中，因為不知道要在是什麼時候釋放記憶體，沒有政策，沒用一種可以預見的場合去将其釋放。這就造成了記憶體溢出。
2. 使用方法
當成一個 Map 用就可以了，隻不過實作了 LRU 緩存政策。
使用的時候記住幾點即可：
- 1.（必填）你需要提供一個緩存容量作為構造參數。
- 2.（必填） 覆寫
sizeOf
- 3.（選填） 覆寫
entryRemoved
- 4.（記住）LruCache是線程安全的，在内部的 get、put、remove 包括 trimToSize 都是安全的（因為都上鎖了）。
- 5.（選填） 還有就是覆寫
create
一般做到 1、2、3、4就足夠了，5可以無視 。
以下是 一個 LruCache 實作 Bitmap 小緩存的案例,
entryRemoved
裡的自定義邏輯可以無視，想看的可以去到我的我的展示demo 裡的看自定義
entryRemoved
邏輯。
private static final float ONE_MIB = 1024 * 1024;
// 7MB
private static final int CACHE_SIZE = (int) (7 * ONE_MIB);
private LruCache<String, Bitmap> bitmapCache;
this.bitmapCache = new LruCache<String, Bitmap>(CACHE_SIZE) {
protected int sizeOf(String key, Bitmap value) {
return value.getByteCount();
}
@Override
protected void entryRemoved(boolean evicted, String key, Bitmap oldValue, Bitmap newValue) {
...
}
}; 3. 效果展示
LruCache 效果展示
4. 源碼分析
4.1 LruCache 原理概要解析
LruCache 就是 利用 LinkedHashMap 的一個特性（ accessOrder＝true 基于通路順序 ）再加上對 LinkedHashMap 的資料操作上鎖實作的緩存政策。
LruCache 的資料緩存是記憶體中的。
- 1.首先設定了内部
LinkedHashMap
accessOrder=true
- 2.然後在每次
LruCache.get(K key)
LinkedHashMap.get(Object key)
- 3.如上述設定了
accessOrder=true
LinkedHashMap.get(Object key)
LinkedHashMap.makeTail(LinkedEntry<K, V> e)
- 4.
LinkedHashMap
LruCache.get
LinkedHashMap.get
- 5.在
put
trimToSize
具體解析在： 4.2、4.3、4.4、4.5 。
4.2 LruCache 的唯一構造方法
/**
* LruCache的構造方法：需要傳入最大緩存個數
*/
public LruCache(int maxSize) {
...
this.maxSize = maxSize;
/*
* 初始化LinkedHashMap
* 第一個參數：initialCapacity，初始大小
* 第二個參數：loadFactor，負載因子=0.75f
* 第三個參數：accessOrder=true，基于通路順序；accessOrder=false，基于插入順序
*/
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
} 第一個參數
initialCapacity
用于初始化該 LinkedHashMap 的大小。
先簡單介紹一下 第二個參數
loadFactor
，這個其實的 HashMap 裡的構造參數，涉及到擴容問題，比如 HashMap 的最大容量是100，那麼這裡設定0.75f的話，到75容量的時候就會擴容。
主要是第三個參數
accessOrder=true
，這樣的話 LinkedHashMap 資料排序就會基于資料的通路順序，進而實作了 LruCache 核心工作原理。
4.3 LruCache.get(K key)
/**
* 根據 key 查詢緩存，如果存在于緩存或者被 create 方法建立了。
* 如果值傳回了，那麼它将被移動到雙向循環連結清單的的尾部。
* 如果如果沒有緩存的值，則傳回 null。
*/
public final V get(K key) {
...
V mapValue;
synchronized (this) {
// 關鍵點：LinkedHashMap每次get都會基于通路順序來重整資料順序
mapValue = map.get(key);
// 計算 命中次數
if (mapValue != null) {
hitCount++;
return mapValue;
}
// 計算 丢失次數
missCount++;
}
/*
* 官方解釋：
* 嘗試建立一個值，這可能需要很長時間，并且Map可能在create()傳回的值時有所不同。如果在create()執行的時
* 候，一個沖突的值被添加到Map，我們在Map中删除這個值，釋放被創造的值。
*/
V createdValue = create(key);
if (createdValue == null) {
return null;
}
/***************************
* 不覆寫create方法走不到下面 *
***************************/
/*
* 正常情況走不到這裡
* 走到這裡的話 說明 實作了自定義的 create(K key) 邏輯
* 因為預設的 create(K key) 邏輯為null
*/
synchronized (this) {
// 記錄 create 的次數
createCount++;
// 将自定義create建立的值，放入LinkedHashMap中，如果key已經存在，會傳回 之前相同key 的值
mapValue = map.put(key, createdValue);
// 如果之前存在相同key的value，即有沖突。
if (mapValue != null) {
/*
* 有沖突
* 是以 撤銷 剛才的 操作
* 将 之前相同key 的值 重新放回去
*/
map.put(key, mapValue);
} else {
// 拿到鍵值對，計算出在容量中的相對長度，然後加上
size += safeSizeOf(key, createdValue);
}
}
// 如果上面 判斷出了 将要放入的值發生沖突
if (mapValue != null) {
/*
* 剛才create的值被删除了，原來的 之前相同key 的值被重新添加回去了
* 告訴 自定義 的 entryRemoved 方法
*/
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
// 上面 進行了 size += 操作 是以這裡要重整長度
trimToSize(maxSize);
return createdValue;
}
} 上述的
get
方法表面并沒有看出哪裡有實作了 LRU 的緩存政策。主要在
mapValue = map.get(key)
;裡，調用了 LinkedHashMap 的 get 方法，再加上 LruCache 構造裡預設設定 LinkedHashMap 的 accessOrder=true。
4.4 LinkedHashMap.get(Object key)
/**
* Returns the value of the mapping with the specified key.
*
* @param key
* the key.
* @return the value of the mapping with the specified key, or {@code null}
* if no mapping for the specified key is found.
*/
@Override public V get(Object key) {
/*
* This method is overridden to eliminate the need for a polymorphic
* invocation in superclass at the expense of code duplication.
*/
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
if (e == null)
return null;
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
}
return null;
} 其實仔細看
if (accessOrder)
的邏輯即可，如果
accessOrder=true
那麼每次
get
都會執行 N 次
makeTail(LinkedEntry<K, V> e)
。
接下來看看：
4.5 LinkedHashMap.makeTail(LinkedEntry e)
/**
* Relinks the given entry to the tail of the list. Under access ordering,
* this method is invoked whenever the value of a pre-existing entry is
* read by Map.get or modified by Map.put.
*/
private void makeTail(LinkedEntry<K, V> e) {
// Unlink e
e.prv.nxt = e.nxt;
e.nxt.prv = e.prv;
// Relink e as tail
LinkedEntry<K, V> header = this.header;
LinkedEntry<K, V> oldTail = header.prv;
e.nxt = header;
e.prv = oldTail;
oldTail.nxt = header.prv = e;
modCount++;
} // Unlink e
// Relink e as tail
LinkedHashMap 是雙向循環連結清單，然後此次 LruCache.get -> LinkedHashMap.get 的資料就被放到最末尾了。
以上就是 LruCache 核心工作原理。
接下來介紹 LruCache 的容量溢出政策。
4.6 LruCache.put(K key, V value)
public final V put(K key, V value) {
...
synchronized (this) {
...
// 拿到鍵值對，計算出在容量中的相對長度，然後加上
size += safeSizeOf(key, value);
...
}
...
trimToSize(maxSize);
return previous;
} 記住幾點：
- 1.put 開始的時候确實是把值放入 LinkedHashMap 了，不管超不超過你設定的緩存容量。
- 2.然後根據
safeSizeOf
size
- 3.說到
safeSizeOf
sizeOf(K key, V value)
- 4.直到 put 要結束時，進行了
trimToSize
size
maxSize
4.7 LruCache.trimToSize(int maxSize)
public void trimToSize(int maxSize) {
/*
* 這是一個死循環，
* 1.隻有 擴容 的情況下能立即跳出
* 2.非擴容的情況下，map的資料會一個一個删除，直到map裡沒有值了，就會跳出
*/
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!");
}
// 如果是 擴容 或者 map為空了，就會中斷，因為擴容不會涉及到丢棄資料的情況
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);
}
} 簡單描述：會判斷之前
size
是否大于
maxSize
。是的話，直接跳出後什麼也不做。不是的話，證明已經溢出容量了。由
makeTail
圖已知，最近經常通路的資料在最末尾。拿到一個存放 key 的 Set，然後一直一直從頭開始删除，删一個判斷是否溢出，直到沒有溢出。
最後看看：
4.8 覆寫 entryRemoved 的作用
entryRemoved被LruCache調用的場景：
- 1.（put） put 發生 key 沖突時被調用，evicted=false，key=此次 put 的 key，oldValue=被覆寫的沖突 value，newValue=此次 put 的 value。
- 2.（trimToSize） trimToSize 的時候，隻會被調用一次，就是最後一次被删除的最少通路資料帶回來。evicted=true，key=最後一次被删除的 key，oldValue=最後一次被删除的 value，newValue=null（此次沒有沖突，隻是 remove）。
- 3.（remove） remove的時候，存在對應 key，并且被成功删除後被調用。evicted=false，key=此次 put的 key，oldValue=此次删除的 value，newValue=null（此次沒有沖突，隻是 remove）。
- 4.（get後半段，查詢丢失後處理情景，不過建議忽略） get 的時候，正常的話不實作自定義
create
create(K key)
解釋一下第四點吧：<1>.第四點是這樣的，先 get(key)，然後沒拿到，丢失。<2>.如果你提供了 自定義的
create(key)
方法，那麼 LruCache 會根據你的邏輯自造一個 value，但是當放入的時候發現沖突了，但是已經放入了。<3>.此時，會将那個沖突的值再讓回去覆寫，此時調用上述4.的 entryRemoved。
因為 HashMap 在資料量大情況下，拿資料可能造成丢失，導緻前半段查不到，你自定義的
create(key)
放入的時候發現又查到了（有沖突）。然後又急忙把原來的值放回去，此時你就白白create一趟，無所作為，還要走一遍entryRemoved。
綜上就如同注釋寫的一樣：
/**
* 1.當被回收或者删掉時調用。該方法當value被回收釋放存儲空間時被remove調用
* 或者替換條目值時put調用，預設實作什麼都沒做。
* 2.該方法沒用同步調用，如果其他線程通路緩存時，該方法也會執行。
* 3.evicted=true：如果該條目被删除空間 （表示 進行了trimToSize or remove） evicted=false：put沖突後 或 get裡成功create後
* 導緻
* 4.newValue!=null，那麼則被put()或get()調用。
*/
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {
} 可以參考我的 demo 裡的
entryRemoved
。
4.9 LruCache 局部同步鎖
在
get
,
put
,
trimToSize
,
remove
四個方法裡的
entryRemoved
方法都不在同步塊裡。因為
entryRemoved
回調的參數都屬于方法域參數，不會線程不安全。
本地方法棧和程式計數器是線程隔離的資料區
5. 開源項目中的使用
square/picasso
6. 總結
LruCache重要的幾點：
- 1.LruCache 是通過 LinkedHashMap 構造方法的第三個參數的
accessOrder=true
LinkedHashMap
- 2.LruCache 在内部的get、put、remove包括 trimToSize 都是安全的（因為都上鎖了）。
- 3.LruCache 自身并沒有釋放記憶體，将 LinkedHashMap 的資料移除了，如果資料還在别的地方被引用了，還是有洩漏問題，還需要手動釋放記憶體。
- 4.覆寫
entryRemoved
- 5.
maxSize
sizeOf(K key, V value)
7. 資源
LruCacheActivity
LruCache 注釋源碼