一营罢、引言
關于 LruCache 的總結犯戏，因為工作推遲了好長一段時間势腮，因此趁現(xiàn)在有點空趕緊記錄下來。
相信很多童鞋也跟我一樣烈钞，最初都是使用 LruCache 作為 ImageLoader 圖片緩存中的一環(huán)泊碑，但是使用的過程中，我們并不關心它這個“最近使用原則”到底源碼怎么實現(xiàn)的棵磷，而僅僅在意它具備這樣的特性蛾狗。因此，本文要做的工作如下：
- 從基本使用解釋”最近使用“這一特性仪媒；
- 結合源碼分析”最近使用“的實現(xiàn)沉桌；
二、從使用到源碼
首先來說說“最近使用”的特點：假設頭部為最近的地方算吩，而尾部是最遠的地方留凭，那么最先插入的元素會放到尾部，而最后插入的元素會被放到頭部偎巢，并且如果我們使用了其中的某個元素蔼夜，那么這個元素會被放到頭部；如果容量到達了限定值压昼，那么再次插入元素的時候就會刪除掉尾部使用頻率最低的元素以插入新元素求冷。 這一特性可解釋如下圖：
通常我們會這樣使用 LruCache，假定限制內存大小為 5M窍霞，那么可以這么做：
// 限定大小
final int maxSize = 1024 * 1024 * 5;
LruCache<String, Bitmap> lruCache = new LruCache<String, Bitmap>(maxSize){
@Override
protected int sizeOf(String key, Bitmap value) {
return value.getRowBytes() * value.getHeight() / 1024 ;
}
@Override
protected void entryRemoved(boolean evicted, String key, Bitmap oldValue,Bitmap newValue) {
// 如果在列表請求時這樣實現(xiàn)匠题，那么快速滑動時肯定會造成內存抖動，因此實際使用中
// 可以先將這些需要清理掉的圖片緩存一下但金，然后在某個時間節(jié)點上集中清理掉
if (!oldValue.isRecycled()){
oldValue.recycle();
}
}
};
跟進到它的構造方法韭山，可以看到它創(chuàng)建了一個 LinkedHashMap ，并且僅僅是基于這一數(shù)據結構來實現(xiàn)：
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<Integer, Integer> linkedHashMap= new LinkedHashMap<>(0, 0.75f, true);
linkedHashMap.put(1, 1);
linkedHashMap.put(2, 2);
linkedHashMap.put(3, 3);
linkedHashMap.put(4, 4);
linkedHashMap.put(5, 5);
for (Map.Entry<Integer, Integer> e : linkedHashMap.entrySet()){
Log.i(TAG, e.getKey() + " <->" + e.getValue());
}
// 這里模擬先后使用 4 和 3 這兩個元素
linkedHashMap.get(4);
linkedHashMap.get(3);
Log.i(TAG, "-----------------");
for (Map.Entry<Integer, Integer> e : linkedHashMap.entrySet()){
Log.i(TAG, e.getKey() + " <->" + e.getValue());
}
// 這里模擬到達內存限定值，刪除最不常用的那個元素
Log.i(TAG, "delete: " + linkedHashMap.keySet().iterator().next());
輸出如下：
1 <->1
2 <->2
3 <->3
4 <->4
5 <->5
-------------
1 <->1
2 <->2
5 <->5
4 <->4
3 <->3
delete: 1 // 要刪除的元素
根據結果可見钱磅，這確實跟我們跟我們前面所理解的一樣梦裂，只不過上面是模擬操作，我們接下來看看 LruCache 對這部分的實現(xiàn)盖淡。首先定位到 put 方法年柠，可見每次添加新元素時都會統(tǒng)計數(shù)量和空間大小、進行新舊元素的替換禁舷，然后檢查是否超出空間限定值彪杉，如果超出毅往，移除尾部最不常用的元素：
public final V put(K key, V value) {
// 不允許 key牵咙、value 為 null
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {
// 統(tǒng)計添加到容器的元素數(shù)量
putCount++;
// 統(tǒng)計容器中元素所占用的空間大小
size += safeSizeOf(key, value);
previous = map.put(key, value);
// 如果 key 位置上已經存在元素，那么用新元素替換舊元素攀唯，并重新統(tǒng)計空間大小
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
// 將 key 上的舊元素刪除掉
if (previous != null) {
entryRemoved(false, key, previous, value);
}
// 超出容量時刪除尾部最不常用的元素
trimToSize(maxSize);
return previous;
}
上面的 trimToSize 源碼如下洁桌，跟集合自身的 trimToSize 功能不一樣之處在于，集合自身的 trimToSize 用于去除多余的沒有存放元素的空間侯嘀，而這里是移除尾部最不常用的元素另凌，些許類似：
private void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
// 1. 統(tǒng)計錯誤的情況
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName()
+ ".sizeOf() is reporting inconsistent results!");
}
// 2. 還有足夠空間容量的情況
if (size <= maxSize) {
break;
}
// 3. 超出限定容量的情況
Map.Entry<K, V> toEvict = null;
// 定位到尾部最不常用的元素，標記為刪除
for (Map.Entry<K, V> entry : map.entrySet()) {
toEvict = entry;
}
// 如如果容器沒有元素戒幔，直接退出
if (toEvict == null) {
break;
}
key = toEvict.getKey();
value = toEvict.getValue();
// 否則吠谢，刪除元素、重新統(tǒng)計空間容量
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}
// 通知元素已經從容器中刪除诗茎，可以做寫清理工作
entryRemoved(true, key, value, null);
}
}
三工坊、關于 LinkedHashMap
注意： 本文中
LinkedHashMap、HashMap版本基于JDK8敢订；在Android中則基于Android N
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
LinkedHashMap 繼承自 HashMap王污，因此我們先來回顧一下 HashMap 和祖先 Hashtable 的特性：
內部構造：
- 當發(fā)生沖突（
key的哈希值相同，但是他們并不equals）的量數(shù)據量較少（< 8）時楚午，HashMap和Hashtable都采用 數(shù)組 + 單向鏈表 這種結構作為解決方案昭齐； - 當發(fā)生沖突的數(shù)據量較大（
> 8）時，不同于Hashtable矾柜，HashMap采用了數(shù)組 + 紅黑樹的解決方案阱驾； -
HashMap是一種非線程安全的數(shù)據結構，而Hashtable是
上面描述了 HashMap 和 Hashtable 的主要區(qū)別怪蔑，這種差異導致 HashMap 在操作性能和使用場景上都比 Hashtable 更勝一籌里覆，并且你完全可以放棄使用 Hashtable ，而在并發(fā)場景下使用 ConcurrentHashMap饮睬；
回到 HashMap租谈， 為什么 采用 數(shù)組 + 單向鏈表 和 數(shù)組 + 紅黑樹 兩種切換方案呢？原因很簡單，因為數(shù)據量很小時割去，使用單向鏈表的操作效率已經夠高了窟却，并且單向鏈表內部構造簡單，能減少額外的空間分配呻逆；相應的夸赫，數(shù)據量大時采用紅黑樹，因為紅黑樹能夠保證各操作的做壞時間復雜度為 log(n)咖城，因此適用于數(shù)據量大且操作頻繁的場景茬腿；
OK， 有了上面的回顧內容宜雀，我們可以對 LinkedHashMap 有個初步的了解切平，接下來我們主要看看 LinkedHashMap中新增的排序規(guī)則。
首先來看看它的構造器辐董，初始容量（initialCapacity）悴品、加載因子（loadFactor）就不解釋了，看到 參數(shù) accessOrder简烘，它用于控制是否開啟 就近使用原則：
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
這里我們假設開啟了就近使用原則苔严，獲取元素時是這樣的：
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
這里的節(jié)點是雙向鏈表的節(jié)點,繼承自 HashMap.Node，如下：
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
LinkedHashMapEntry<K,V> before, after;
LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
注意到上面的 afterNodeAccess孤澎，源碼如下届氢，在這里會將節(jié)點移動到尾部，而這里的尾部代表最常使用的節(jié)點覆旭，也是最近節(jié)點退子。
void afterNodeAccess(Node<K,V> e) {
LinkedHashMapEntry<K,V> last;
if (accessOrder && (last = tail) != e) { // 節(jié)點不在尾部
LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, // 當前節(jié)點
b = p.before, // 前一個節(jié)點
a = p.after; // 后一個節(jié)點
p.after = null; // 剪斷 當自己與后一個節(jié)點的連接
// 1. 將自己從鏈表中分離出來
if (b == null) // 前面沒節(jié)點了，說明它自己是頭部姐扮，那么直接讓位給下一個節(jié)點
head = a;
else // 前面還有節(jié)點絮供，那么將前一個節(jié)點連接到下一個節(jié)點，讓位
b.after = a;
if (a != null) // 因為是雙向鏈表茶敏，所以這里 a 節(jié)點存在的時候需要重置一下前一個連接壤靶，
a.before = b;
else
last = b; // 不存在則直接把 befor 當成尾部
if (last == null) // 說明當前鏈表無節(jié)點， 那么直接把當前節(jié)點作為頭部
head = p;
else { // 已經存在節(jié)點的話惊搏，那么將當前節(jié)點連接到尾部
p.before = last;
last.after = p;
}
tail = p; // 尾部重新賦值一下
++modCount;
}
}
相對于 HashMap 而言贮乳， LinkedHashMap 使用雙向鏈表而不是單向鏈表，并且有排序規(guī)則恬惯，能夠對元素進行排序向拆。
三、總結
嗯~酪耳，寫到最后發(fā)現(xiàn)沒啥話可說的了...嘿嘿
文中主要分析總結了一下 LruCache 的最近使用原則浓恳，接著回顧了一下 LinkedHashMap 相關的一些知識刹缝，如 HashMap 和 Hashtable，并具體分析了一下它在get元素時進行的操作規(guī)則;
總的來說颈将，LruCache相當于LinkedHashMap的一層代理梢夯，自身控制內存大小，而將存儲操作委托給了LinkedHashMap晴圾；
