前言：自從Andorid3.1之后，谷歌引入了LruCache沪曙，官方文檔說(shuō)明如下：
* 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
*
* <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.
*
- 官方文檔指出幾點(diǎn):
--hold strong reference: 該緩存引用的是強(qiáng)引用。
--a value is accessed, it is moved to the head of a queue ：每次一個(gè)數(shù)據(jù)被訪問(wèn)萎羔，就會(huì)被移到對(duì)頭
--要重載sizeof用于測(cè)量當(dāng)前內(nèi)存大小
--不支持空的key液走。
LRU:什么是LRU算法？ LRU是Least Recently Used的縮寫贾陷，即最近最少使用
LruCache里面最重要的是維護(hù)了一個(gè)雙向鏈表（該鏈表支持有序插入）用于存放緩存數(shù)據(jù),LinkedHashMap底層正是實(shí)現(xiàn)了LRU算法.
private final LinkedHashMap<K, V> map;
LinkedHashMap :
- LinkedHashMap is an implementation of {@link Map} that guarantees > iteration order.
- All optional operations are supported.
- <p>All elements are permitted as keys or values, including null.
- <p>Entries are kept in a doubly-linked list. The iteration order is, by > > > default, theorder in which keys were inserted. Reinserting an already-present key > doesn't change theorder. If the three argument constructor is used, and {@code accessOrder} is specified as
{@code true}, the iteration will be in the order that entries were accessed.- The access order is affected by {@code put}, {@code get}, and {@code putAll} operations,
- but not by operations on the collection views.
LinkedHashMap 繼承HashMap,里面維護(hù)一個(gè)內(nèi)部類LinkeEntry雙向鏈表用于存儲(chǔ)數(shù)據(jù)育灸。
具體分析可以看該博客：圖解LinkedHashMap原理
我們先開LruCache的構(gòu)造函數(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);
}
構(gòu)造了一個(gè)LinkedHashMap，而且第三個(gè)參數(shù)為true昵宇，表示訪問(wèn)有序(這個(gè)是實(shí)現(xiàn)該LruCache算法的核心磅崭。)
put函數(shù)：
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è)數(shù)據(jù)，size會(huì)根據(jù)當(dāng)前的數(shù)據(jù)大小增加
private int safeSizeOf(K key, V value) {
int result = sizeOf(key, value);//該方法就是上面說(shuō)的要重寫的方法
if (result < 0) {
throw new IllegalStateException("Negative size: " + key + "=" + value);
}
return result;
}
然后將數(shù)據(jù)放入map瓦哎，返回一個(gè)previous,其中砸喻，map.put(key, value):
HashMap.java
@Override public V put(K key, V value) {
if (key == null) {
return putValueForNullKey(value);
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
// No entry for (non-null) key is present; create one
modCount++;
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index);
return null;
}
當(dāng)當(dāng)前的key在map里面是有的時(shí)候柔逼，返回舊的數(shù)據(jù),并且被回收掉。
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, value);
}
public void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
//如果重載的sizeof方法返回的大小單位跟max傳入的大小單位不同割岛，這里會(huì)報(bào)錯(cuò)
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);
}
對(duì)緩存進(jìn)行內(nèi)存裁剪愉适，不斷第將隊(duì)尾的數(shù)據(jù)刪除，直到size<=maxSize.
其中最關(guān)鍵的就是map.eldest()這段代碼癣漆，拿到當(dāng)前最老的數(shù)據(jù)维咸，也就是說(shuō)最近最少訪問(wèn)的數(shù)據(jù)。
public Entry<K, V> eldest() {
LinkedEntry<K, V> eldest = header.nxt;
return eldest != header ? eldest : null;
}
由于在構(gòu)造LinkedMap的時(shí)候惠爽，構(gòu)造參數(shù)accessOrder是true,也就是說(shuō)當(dāng)前的鏈表的順序是根據(jù)訪問(wèn)時(shí)間去定當(dāng)前數(shù)據(jù)的位置癌蓖，越久沒訪問(wèn)，越前婚肆。
LinkedHashMap:
/**
* 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++;
}
上面就是每次調(diào)整數(shù)據(jù)順序的代碼租副。
--在如果做圖片處理的時(shí)候，可以復(fù)寫entryRemoved對(duì)從map里面移除的圖片進(jìn)行復(fù)用內(nèi)存较性。
get方法：
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
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.
*/
V createdValue = create(key);
if (createdValue == null) {
return null;
}
//下面代碼跟put的代碼差不多用僧，也是新建一個(gè)value放入map
synchronized (this) {
createCount++;
mapValue = map.put(key, createdValue);
if (mapValue != null) {
// There was a conflict so undo that last put
map.put(key, mapValue);
} else {
size += safeSizeOf(key, createdValue);
}
}
if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
trimToSize(maxSize);
return createdValue;
}
}
該方法有個(gè)特殊的地方就是，如果map里面沒有對(duì)應(yīng)的key的數(shù)據(jù)或者出于其他原因key對(duì)應(yīng)的數(shù)據(jù)被刪除了赞咙，提供了create(key)方法給用于去重新創(chuàng)建對(duì)應(yīng)的數(shù)據(jù)责循。
LruCache
