1. 概述
比較常用的一種緩存算法是LRU（Least Recently Used），LRU是近期最少使用算法，它的核心思想是當(dāng)緩存滿時(shí)，會(huì)優(yōu)先淘汰那些近期最少使用的緩存對(duì)象。采用LRU算法的緩存有兩種：內(nèi)存緩存和磁盤緩存，LruCache用于實(shí)現(xiàn)內(nèi)存緩存。
2. 使用
int cacheSize = (int) (Runtime.getRuntime().maxMemory() / 1024 / 8);//計(jì)算最大緩存大小（內(nèi)存的1/8）
LruCache<String, Bitmap> lruCache = new LruCache<String, Bitmap>(cacheSize) {
@Override
protected int sizeOf(String key, Bitmap value) {//自定義每個(gè) entry 大小的計(jì)算方法
return value.getByteCount() / 1024;
}
};
注：maxMemory 返回的單位是 字節(jié)。
3. 構(gòu)造方法與成員變量
size 當(dāng)前占用的內(nèi)存大小
maxSize 允許的最大容量
這兩個(gè)值指的是內(nèi)存的大小，跟Entry的數(shù)量沒有直接關(guān)系。
private final LinkedHashMap<K, V> map;//使用 LinkedHashMap 方便實(shí)現(xiàn)移除「最近最少使用的元素」
//每一個(gè)緩存實(shí)體的大小。不一定是元素的數(shù)量。
private int size;
private int maxSize;
private int putCount;//添加的數(shù)量
private int createCount;//創(chuàng)建的數(shù)量
private int evictionCount;//「趕出」的數(shù)量
private int hitCount;//命中次數(shù)
private int missCount;//不命中的次數(shù)
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);//初始化LinkedHashMap
}
4. put 操作
android.support.v4.util.LruCache#put
/**
* 緩存{@code key}的{code}值。該值被移動(dòng)到隊(duì)列的頭部。
*
* @return 原先 key 對(duì)應(yīng)的值.
*/
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++;//put 數(shù)量+1
size += safeSizeOf(key, value);//當(dāng)前占用的內(nèi)存大小增加相應(yīng)的單位
previous = map.put(key, value);//存儲(chǔ)
if (previous != null) {//
size -= safeSizeOf(key, previous);//本來(lái)已經(jīng)有這樣的 Entry，需要減去舊 Entry
}
}
if (previous != null) {//移除舊值
entryRemoved(false, key, previous, value);
}
trimToSize(maxSize);//
return previous;
}
LruCache#safeSizeOf
private int safeSizeOf(K key, V value) {
int result = sizeOf(key, value);//調(diào)用 sizeOf 方法，獲取對(duì)應(yīng) Entry 的大小
if (result < 0) {
throw new IllegalStateException("Negative size: " + key + "=" + value);
}
return result;
}
/**
* Returns the size of the entry for {@code key} and {@code value} in
* user-defined units. The default implementation returns 1 so that size
* is the number of entries and max size is the maximum number of entries.
*
以用戶定義的單位返回{@code key}和{code code}的 entry 大小。默認(rèn)實(shí)現(xiàn)返回1，以便size是 entry 數(shù)量，max size是 entry 的最大數(shù)量。
* <p>An entry's size must not change while it is in the cache.
*/
protected int sizeOf(K key, V value) {
return 1;
}
LruCache#trimToSize
移除緩存中最不常使用的元素，直到低于指定的值。
/**
* 刪除「最老的」 entries ，直到剩余 entries 的總數(shù)達(dá)到或小于參數(shù) maxSize 的值。
* @param maxSize返回之前緩存的最大大小?？赡苁?1
* 驅(qū)逐即使是0大小的元素。
* @param maxSize the maximum size of the cache before returning. May be -1
* to evict even 0-sized elements.
*/
public void trimToSize(int maxSize) {
while (true) {//無(wú)條件循環(huán)
K key;
V value;
synchronized (this) {//進(jìn)入同步塊
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName()
+ ".sizeOf() is reporting inconsistent results!");
}
if (size <= maxSize || map.isEmpty()) {//當(dāng)前容量 符合要求
break;
}
Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
key = toEvict.getKey();//
value = toEvict.getValue();//
map.remove(key);//移除 key 對(duì)應(yīng)的 value
size -= safeSizeOf(key, value);//更新占用內(nèi)存大小
evictionCount++;//「清除的數(shù)量」+ 1
}
entryRemoved(true, key, value, null);//通知元素已經(jīng)被移除了
}
}
LruCache#maxSize
獲取最大的緩存值
public synchronized final int maxSize() {
return maxSize;
}
5. get 操作
/**
* 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) {//key 不能為空
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {//進(jìn)入同步塊
mapValue = map.get(key);//
if (mapValue != null) {
hitCount++;//命中次數(shù)+1
return mapValue;//返回
}
missCount++;//未命中的次數(shù)+1
}
/*嘗試創(chuàng)建一個(gè)值。這可能需要很長(zhǎng)時(shí)間，并且 create() 方法返回時(shí)map 可能已經(jīng)出現(xiàn)了修改。如果 create（）方法正在工作時(shí)將沖突值添加到 map 中，則我們將該值保留在 map 中并釋放創(chuàng)建的值。
*/
V createdValue = create(key);//默認(rèn)實(shí)現(xiàn)中 create 返回null
if (createdValue == null) {
return null;
}
synchronized (this) {//進(jìn)入同步塊
createCount++;//創(chuàng)建次數(shù)+1
mapValue = map.put(key, createdValue);//將生成的值存儲(chǔ)進(jìn)去
if (mapValue != null) {
// There was a conflict so undo that last put
map.put(key, mapValue);//創(chuàng)建值期間，key 有對(duì)應(yīng)的值 put 進(jìn)來(lái)了，那么應(yīng)該將它置為對(duì)應(yīng)的值
} else {
size += safeSizeOf(key, createdValue);//
}
}
if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);//通知 entry 被移除掉了
return mapValue;
} else {
trimToSize(maxSize);//保證內(nèi)存占用小于最大的內(nèi)存
return createdValue;
}
}
/**
* entry被移除之后會(huì)回調(diào)該方法。默認(rèn)為空實(shí)現(xiàn)。
* 對(duì)參數(shù) evicted 的說(shuō)明：
* 如果刪除條目以騰出空間，則 evicted 為 true;
* 如果刪除是由 put或 remove 引起的，則為false。
*/
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}
/**
* 在緩存未命中后調(diào)用，用于計(jì)算相應(yīng)key的值。返回計(jì)算值，如果不能計(jì)算值的話，則返回null。默認(rèn)實(shí)現(xiàn)直接返回null。
*
* 該方法可以在沒有同步的情況下被調(diào)用：這意味著 其他線程可以在該方法執(zhí)行時(shí)訪問緩存。
*/
protected V create(K key) {
return null;
}
6. 清空緩存
/**
* 清空緩存
*/
public final void evictAll() {
trimToSize(-1); // -1 will evict 0-sized elements
}
7. 獲取緩存的快照
/**
* 返回緩存中當(dāng)前內(nèi)容的副本，按照最近最少訪問到最近訪問的順序排列。
*/
public synchronized final Map<K, V> snapshot() {
return new LinkedHashMap<K, V>(map);
}
8.總結(jié)
緩存的關(guān)鍵在于存儲(chǔ)與淘汰。淘汰有一定的策略，LRUCache 中的淘汰策略是刪除最近最少使用的元素。LRUCache 使用 LinkedHashMap 作為存儲(chǔ)的容器，初始化 LinkedHashMap 的時(shí)候指定排序模式為按照訪問順序排序。每次 put 的完成的時(shí)候進(jìn)行檢查，如果緩存占用是否超出了指定的最大值，如果是，會(huì)淘汰掉最近最不常使用有的元素。
由于本人水平有限，可能出于誤解或者筆誤難免出錯(cuò)，如果發(fā)現(xiàn)有問題或者對(duì)文中內(nèi)容存在疑問歡迎在下面評(píng)論區(qū)告訴我。謝謝！
