前言
LRU及Least Recently Used, 最近最少使用算法, 也就是當(dāng)內(nèi)存緩存達(dá)到設(shè)定的最大值時(shí)將內(nèi)存緩存中近期最少使用的對象移除，有效的避免了OOM的出現(xiàn).
上篇文章我們看了LinkedHashMap的源碼, 通過LinkedHashMap可以很方便的獲取最少使用的元素, 而LRUCache也就是通過LinkedHashMap來實(shí)現(xiàn)的, 下面來看下LRUCache的代碼.
源碼
- 注釋
/**
* A cache that holds strong references to a limited number of values. Each time
* a value is accessed, it is moved to the head of a queue. When a value is
* added to a full cache, the value at the end of that queue is evicted and may
* become eligible for garbage collection.
*
* <p>If your cached values hold resources that need to be explicitly released,
* override {@link #entryRemoved}.
*
* <p>If a cache miss should be computed on demand for the corresponding keys,
* override {@link #create}. This simplifies the calling code, allowing it to
* assume a value will always be returned, even when there's a cache miss.
*
* <p>By default, the cache size is measured in the number of entries. Override
* {@link #sizeOf} to size the cache in different units. For example, this cache
* is limited to 4MiB of bitmaps:
* <pre> {@code
* int cacheSize = 4 * 1024 * 1024; // 4MiB
* LruCache<String, Bitmap> bitmapCache = new LruCache<String, Bitmap>(cacheSize) {
* protected int sizeOf(String key, Bitmap value) {
* return value.getByteCount();
* }
* }}</pre>
*
* <p>This class is thread-safe. Perform multiple cache operations atomically by
* synchronizing on the cache: <pre> {@code
* synchronized (cache) {
* if (cache.get(key) == null) {
* cache.put(key, value);
* }
* }}</pre>
*
* <p>This class does not allow null to be used as a key or value. A return
* value of null from {@link #get}, {@link #put} or {@link #remove} is
* unambiguous: the key was not in the cache.
*
* <p>This class appeared in Android 3.1 (Honeycomb MR1); it's available as part
* of <a s
* Support Package</a> for earlier releases.
*/
總結(jié)一下注釋中提到的幾點(diǎn)信息:
- LRUCache是一個(gè)持有有限數(shù)據(jù)的強(qiáng)引用. 每次訪問元素, 該元素就會被移到隊(duì)列頭部. 隊(duì)列滿了之后再次添加元素, 就會回收隊(duì)列尾部的元素.
- 如果緩存的值持有的資源需要被徹底釋放, 需要重寫entryRemoved進(jìn)行釋放操作.
- 重寫create方法, 這樣緩存即使丟失也總能被返回.
- 默認(rèn)的緩存占用大小是緩存對象的個(gè)數(shù), 需要重寫sizeOf計(jì)算不同緩存對象所占的大小.
- LRUCache是線程安全的.
- 不允許使用空的key和value.
- 出現(xiàn)在Android3.1, 也在Android Support包中兼容早期版本.
- 變量及構(gòu)造方法
public class LruCache<K, V> {
private final LinkedHashMap<K, V> map;
private int size;//內(nèi)存占用大小
private int maxSize;//緩存最大容量
private int putCount;//put的次數(shù)
private int createCount;//create的次數(shù)
private int evictionCount;//回收的次數(shù)
private int hitCount;//get到的次數(shù)
private int missCount;//未get到的次數(shù)
//構(gòu)造函數(shù)中傳入最大緩存容量
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
//初始化LinkedHashMap, 擴(kuò)充因子為0.75, accessOrder為true, 按訪問順序排列, 方便獲取最老的元素
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
}
- put
public final V put(K key, V value) {
//key和value都不能為空
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {
putCount++;
size += safeSizeOf(key, value);//size累加該對象緩存大小
previous = map.put(key, value);//獲取key對應(yīng)的之前的值
//不為空, size要減去之前的值所占的緩存大小
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
//key之前對應(yīng)的有值, 通知舊值被替換
if (previous != null) {
entryRemoved(false, key, previous, value);
}
//重新計(jì)算是否超過最大容量
trimToSize(maxSize);
return previous;
}
private int safeSizeOf(K key, V value) {
//獲取該對象緩存大小
int result = sizeOf(key, value);
if (result < 0) {
throw new IllegalStateException("Negative size: " + key + "=" + value);
}
return result;
}
//需要重寫該方法, 設(shè)置每個(gè)緩存對象的大小, 默認(rèn)為1
protected int sizeOf(K key, V value) {
return 1;
}
//當(dāng)entry對象被回收或刪除或替換時(shí), 通過此方法回調(diào)出去
//evicted: 是否被回收 oldValue: key對應(yīng)的舊值 newValue:key對應(yīng)的新值
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {
}
LRUCache的put操作就是在LinkedHashMap的put操作上增加了緩存大小的計(jì)算和是否超出最大容量的計(jì)算, 如果超出就刪除最舊的緩存對象.
- trimToSize
計(jì)算緩存是否超出最大值.
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;
}
//緩存容量超出最大值之后, 通過LinkedHashMap獲取最舊的元素
Map.Entry<K, V> toEvict = map.eldest();
if (toEvict == null) {
break;
}
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);// 刪除最舊的元素
size -= safeSizeOf(key, value);//重新計(jì)算緩存大小
evictionCount++;//增加回收次數(shù)
}
//回調(diào)通知回收了最舊的元素
entryRemoved(true, key, value, null);
}
}
- get
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
//map獲取到key對應(yīng)的值之后直接返回
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
//如果map中沒有獲取到, 判斷用戶是否重寫create來創(chuàng)建對象
V createdValue = create(key);
if (createdValue == null) {
return null;
}
//如果用戶重寫了create創(chuàng)建對象
synchronized (this) {
createCount++;
//把key和新創(chuàng)建的對象存入map, 并獲取key對應(yīng)的之前的對象
mapValue = map.put(key, createdValue);
//如果key對應(yīng)的之前的對象不為空, 再重新把之前的值存入map
//因?yàn)閏reate可能需要一段時(shí)間, 多線程訪問時(shí)可能會有key對應(yīng)舊值不為空的情況, 所以保存舊值, 放棄新值
if (mapValue != null) {
// There was a conflict so undo that last put
map.put(key, mapValue);
} else {//key對應(yīng)舊值為空, 累加緩存大小
size += safeSizeOf(key, createdValue);
}
}
//key對應(yīng)舊值不為空, 緩存大小不不變, 通知刪除新值, 返回舊值
if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {//key沒有對應(yīng)舊值, 重新計(jì)算是否超出最大值, 返回新值
trimToSize(maxSize);
return createdValue;
}
}
get就是通過LinkedHashMap獲取key對應(yīng)的value, 有則直接返回, 沒有則創(chuàng)建, 如果創(chuàng)建了新value就加入LinkedHashMap, 重新計(jì)算緩存大小, 重新計(jì)算是否超出最大緩存.
- remove
public final V remove(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V previous;
synchronized (this) {
//刪除key對應(yīng)的value
previous = map.remove(key);
//key對應(yīng)value不為空, 刪除之后要重新計(jì)算緩存大小
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
//key對應(yīng)value不為空, 刪除之后, 通知刪除了該value
if (previous != null) {
entryRemoved(false, key, previous, null);
}
return previous;
}
remove操作也很簡單, 通過LinkedHashMap刪除key對應(yīng)value之后重新計(jì)算緩存大小.
- resize
public void resize(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
synchronized (this) {
this.maxSize = maxSize;
}
trimToSize(maxSize);
}
很簡單, 就是重新設(shè)置緩存最大值, 重新計(jì)算當(dāng)前緩存是否超出最大值.
基本操作就這些, 是不是很簡單, 存取都是通過LinkedHashMap來操作的, 只不過多了緩存大小的計(jì)算, 以及是否超出最大緩存的計(jì)算, 如果超出最大緩存, 就把最少使用的對象刪除.
原理清楚了, 具體使用可以參考大神的照片墻
