前言
有一定經(jīng)驗的開發(fā)者都知道這個類乳绕， 大多數(shù)情況 LruCache 類都被用在圖片緩存這一塊， 而其中使用了一個聽起來高大上的算法 —— “近期最少使用算法”礼烈。 在經(jīng)過一輪源碼的解析之后， 我們會發(fā)現(xiàn)內部是使用了簡單的技巧來實現(xiàn)的瞻润。
源碼剖析
首先我們來看一下 LruCache 的構造方法
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 實現(xiàn)版扩。
在一般情況下废离， 當需要緩存某個對象時， 調用的是 put 方法
LruCache#put
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;
}
我們來看一下 ②礁芦， 調用了 safeSizeOf 方法蜻韭， 該方法用來計算 value 占用大小的。
private int safeSizeOf(K key, V value) {
int result = sizeOf(key, value);
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.
*
* <p>An entry's size must not change while it is in the cache.
*/
protected int sizeOf(K key, V value) {
return 1;
}
可以看到 sizeof 方法默認返回1宴偿， 所以我們在使用 LruCache 類時常常需要重寫該方法湘捎， 指定 key 和 value 的占用空間大小。
再回到 put 方法中窄刘， 研究一下③方法， 調用了 map 的 put 方法舷胜， map 即為初始化時候的 LinkedHashMap娩践， 而 LinkedHashMap 繼承了 HashMap 的 put 方法。
HashMap#put
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
// hash 值與 length -1 作與操作烹骨， 相當于取余翻伺， 計算出位標
int i = indexFor(hash, table.length);
// 找到 i 位置hash和key相同的位置， 如果不為空沮焕， 且 hash 值與 key 值相同吨岭， 替換舊數(shù)值
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
要注意 LinkedHashMap 重寫了 HashMap 的 addEntry 方法， 該方法沒處理什么峦树， 接著看 HashMap 的方法辣辫。
LinkedHashMap#addEntry
void addEntry(int hash, K key, V value, int bucketIndex) {
// Previous Android releases called removeEldestEntry() before actually
// inserting a value but after increasing the size.
// The RI is documented to call it afterwards.
// **** THIS CHANGE WILL BE REVERTED IN A FUTURE ANDROID RELEASE ****
// Remove eldest entry if instructed
LinkedHashMapEntry<K,V> eldest = header.after;
if (eldest != header) {
boolean removeEldest;
size++;
try {
removeEldest = removeEldestEntry(eldest);
} finally {
size--;
}
if (removeEldest) {
removeEntryForKey(eldest.key);
}
}
super.addEntry(hash, key, value, bucketIndex);
}
HashMap#addEntry
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); //擴容到原來的2倍
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
可以看到， 如果添加對象過后的大小大于指定值魁巩， 將進行擴容急灭， 在這里先不管它。 繼續(xù)看方法末尾調用的 createEntry 方法谷遂。
HashMap#createEntry
/**
* This override differs from addEntry in that it doesn't resize the
* table or remove the eldest entry.
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> old = table[bucketIndex];
LinkedHashMapEntry<K,V> e = new LinkedHashMapEntry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
}
private static class LinkedHashMapEntry<K,V> extends HashMapEntry<K,V> {
// These fields comprise the doubly linked list used for iteration.
LinkedHashMapEntry<K,V> before, after;
LinkedHashMapEntry(int hash, K key, V value, HashMapEntry<K,V> next) {
super(hash, key, value, next);
}
...
}
我們可以看到葬馋， 新增結點除了初始化 LinkedHashMapEntry （實質初始化 HashMapEntry 的內部屬性， 初始化時使用鏈地址法解決沖突) 內的屬性外肾扰， 還調用了 LinkedHashMapEntry 對象的 addBefore 方法畴嘶。
LinkedHashMapEntry#addBefore
private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
這個 header 又是個啥？
我們看看 header 對象的初始化過程集晚， 在構造 LinkedHashMap 初始化的過程窗悯， （同時父類 HashMap 也初始化， 并調用 init 方法）甩恼， 調用了 init 方法蟀瞧。
/**
* The head of the doubly linked list. 雙向鏈表的頭沉颂， 初始化時 header 的前驅后繼都指向自己
*/
private transient LinkedHashMapEntry<K,V> header;
@Override
void init() {
header = new LinkedHashMapEntry<>(-1, null, null, null);
header.before = header.after = header;
}
header 是默認沒有鍵和值的， 默認前驅和后繼都指向自己悦污。 如圖：
所以調用完上面的 addBefore 方法后铸屉， 結構是這樣的：
如果添加第二個結點的話， 還是看 addBefore 方法切端， 結構是這樣的：
最后讓我們回到 LruCache 的 put 方法彻坛， 看最后一步 ④， trimToSize 是干嘛的呢踏枣？
LruCache#trimToSize
/**
* Remove the eldest entries until the total of remaining entries is at or
* below the requested size.
*
* @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) {
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 || 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);
}
}
可以看到官方注釋昌屉， 如果請求的空間不夠時， 將移除最近未使用的 entry 鍵值對茵瀑， 近期最少使用是怎么判斷的呢间驮。 先獲取存放所有 Entry 的 set 容器， 直接移除 next 方法獲取的 Entry马昨， 移除 entry 直到 size 小于 maxSize竞帽， 這個技巧真是 666；
現(xiàn)在來研究一下 entrySet 方法和 iterator 方法和 next 方法鸿捧。 entrySet 方法 LinkedHashMap 是從 HashMap 繼承過來的
// ---------------- HashMap--------------
public Set<Map.Entry<K,V>> entrySet() {
return entrySet0();
}
private Set<Map.Entry<K,V>> entrySet0() {
Set<Map.Entry<K,V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return newEntryIterator(); // !!!!!!!!! 看這
}
...
}
這里要注意一下這個 newEntryIterator 是調用誰的方法的屹篓， 我們可以看到 HashMap 和 LinkedHashMap 都有這個方法
// HashMap
Iterator<Map.Entry<K,V>> newEntryIterator() {
return new EntryIterator();
}
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> { // ①
public Map.Entry<K,V> next() {
return nextEntry();
}
}
// LinkedHashMap 肯定重寫了父類 newEntryIterator 方法
Iterator<Map.Entry<K,V>> newEntryIterator() {
return new EntryIterator();
}
private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> { // ②
public Map.Entry<K,V> next() { return nextEntry(); }
}
① 和 ② 明顯就不一樣， 父類不同匙奴。 剛開始我研究的時候堆巧， 就看錯研究對象了， 搞得最后一臉懵逼泼菌。 我們這里研究的對象是 LinkedHashMap谍肤， 所以調用 next 方法后， 將會調用 LinkedHashIterator 的 nextEntry 方法灶轰。
LinkedHashMap 內部類 LinkedHashIterator
private abstract class LinkedHashIterator<T> implements Iterator<T> {
LinkedHashMapEntry<K,V> nextEntry = header.after;
LinkedHashMapEntry<K,V> lastReturned = null;
...
Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == header)
throw new NoSuchElementException();
LinkedHashMapEntry<K,V> e = lastReturned = nextEntry;
nextEntry = e.after;
return e;
}
}
第一次進行 Iterator 遍歷時谣沸， 最先得到的即是 header.after 指向的對象， 結合上面的 trimToSize 方法笋颤， 可以發(fā)現(xiàn)乳附， 第一次 next 得到的對象， map 對其直接作 remove 處理伴澄。 厲害了赋除， 那就說明 header.after 指向的對象就是最近最少使用對象。
那非凌， 如果我通過 get 方法举农， 取出對象使用， LinkedHashMap 的內部結構又會有什么變化呢敞嗡。
所以我們看看颁糟， LinkedHashMap 的 get 方法航背。
LinkedHashMap#get
public V get(Object key) {
// ①
LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
if (e == null)
return null;
// ②
e.recordAccess(this);
return e.value;
}
咱們先看看 ① 做了什么。
HashMap#getEntry
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
這個方法沒什么特殊的棱貌， 找到 hash 對應位標玖媚， 再找到 hash 值與 key 值相同的對象， 最后依次對象返回婚脱。
我們回到 get 方法今魔， 看 ② 發(fā)生了什么， 這個方法更厲害了Ｕ厦场错森！
LinkedHashMapEntry#recordAccess
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) { // accessOrder 在 LruCache 初始化 LinkedHashMap 過程中置為 true 了
lm.modCount++;
remove(); //
addBefore(lm.header);
}
}
先看 remove 方法。
private void remove() {
before.after = after;
after.before = before;
}
調用完 remove 后篮洁， 結構如圖：（假設我們要 get 的是圖中 ① 對象）
現(xiàn)在看看 addBefore 方法
private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
調用完 addBefore 后涩维， 最終的結構如圖：
所以當通過 get 方法 “使用” 了一個對象， 該對象將會放在鏈表最末端嘀粱， 所以近期最少使用的對象也就是 header.after 指向的對象了激挪。
