目錄
從零實現(xiàn)ImageLoader（一）—— 架構
從零實現(xiàn)ImageLoader（二）—— 基本實現(xiàn)
從零實現(xiàn)ImageLoader（三）—— 線程池詳解
從零實現(xiàn)ImageLoader（四）—— Handler的內(nèi)心獨白
從零實現(xiàn)ImageLoader（五）—— 內(nèi)存緩存LruCache
從零實現(xiàn)ImageLoader（六）—— 磁盤緩存DiskLruCache
LRU算法
在同步加載與異步加載的實現(xiàn)之后固蚤，終于又迎來了圖片加載框架的另一個重要特性——內(nèi)存緩存夕玩。至于加入內(nèi)存緩存原因，之前也已經(jīng)提到了尸昧，主要有以下兩點：
- 圖片的加載是需要時間的烹俗，不論是從網(wǎng)絡萍程，還是從磁盤茫负，都會造成應用不同程度的卡頓忍法，而直接從內(nèi)存中加載就可以避免這種情況。
- 內(nèi)存的大小并不是無限的缔赠，如果一味的將圖片放入內(nèi)存而不加管理衍锚，很快就會觸發(fā)OOM，所以一個好的內(nèi)存管理也是必不可少的嗤堰。
而Android就給我們提供了這樣一個工具戴质，這就是LruCache。
LRU踢匣，全稱Least Recently Used告匠，近期最少使用算法，主要是基于如果數(shù)據(jù)很久沒有被訪問過离唬，那么它將來被訪問的幾率也很小的思想后专。它會優(yōu)先淘汰掉那些很久都沒有被訪問的數(shù)據(jù)输莺，而這也正是內(nèi)存緩存想要做到的事戚哎。
加入內(nèi)存緩存
我們創(chuàng)建一個新類MemoryCache用來封裝LruCache：
public class MemoryCache {
private LruCache<String, Bitmap> mLruCache;
public MemoryCache(int maxSize) {
mLruCache = new LruCache<String, Bitmap>(maxSize) {
@Override
protected int sizeOf(String key, Bitmap value) {
return value.getByteCount();
}
};
}
public Bitmap get(String key) {
return mLruCache.get(key);
}
public void put(String key, Bitmap bitmap) {
mLruCache.put(key, bitmap);
}
}
LruCache的使用非常簡單，唯一需要注意的是需要重寫sizeOf()方法嫂用。sizeOf()是用來計算每條數(shù)據(jù)的大小的型凳，默認會返回1，也就是每張圖片都會被當做1Byte對待嘱函，如果不重寫甘畅，恐怕內(nèi)存都撐爆了也沒有一個圖片被淘汰。
現(xiàn)在我們就可以在Dispatcher.get()方法中加入內(nèi)存緩存代碼了：
public Bitmap get() throws IOException {
//從內(nèi)存獲取
Bitmap image = mMemoryCache.get(mKey);
if(image == null) {
image = NetworkUtil.getBitmap(mUrl);
synchronized(mMemoryCache) {
if(mMemoryCache.get(mKey) != null) {
mMemoryCache.put(mKey, image);
}
}
}
return image;
}
get()方法會首先嘗試從內(nèi)存中獲取圖片，如果沒有再從網(wǎng)絡上進行下載疏唾，并加入內(nèi)存緩存蓄氧。這里之所以要加鎖重新判斷，主要是為了避免有其他線程在我們下載圖片時將同樣的數(shù)據(jù)已經(jīng)加入緩存槐脏，導致緩存數(shù)據(jù)的重復喉童。
這里的key我們選擇使用圖片URL的MD5值：
private String getKeyByUrl(String url) {
MessageDigest digest;
try {
digest = MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException e) {
throw new RuntimeException(e);
}
byte[] md5 = digest.digest(url.getBytes());
StringBuilder result = new StringBuilder();
for (byte aMd5 : md5) {
if ((0xFF & aMd5) < 0x10) {
result.append('0').append(Integer.toHexString(0xFF & aMd5));
} else {
result.append(Integer.toHexString(0xFF & aMd5));
}
}
return result.toString();
}
還有一個問題就是圖片緩存的大小，一般來說顿天，為了平衡圖片緩存的效率與內(nèi)存的占用泄朴，我們都會選擇使用1/8內(nèi)存大小：
private int calculateMemoryCacheSize(Context context) {
ActivityManager activityManager = (ActivityManager) context.getSystemService(Context.ACTIVITY_SERVICE);
int memorySize = activityManager.getMemoryClass() * 1024 * 1024;
return memorySize / 8;
}
這樣我們就實現(xiàn)了一個完整的內(nèi)存緩存方案露氮。
LruCache原理
當然，我們學習LruCache钟沛，不僅要知其然畔规，還要知其所以然，下面我們就一起來探索LruCache的實現(xiàn)原理恨统。
LruCache內(nèi)部維護了一個LinkedHashMap類叁扫，所有的數(shù)據(jù)都是在這個里面存儲的：
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);
}
而get()和put()的實現(xiàn)也很簡單：
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++;
}
...
}
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);
}
}
...
trimToSize(maxSize);
return previous;
}
為了邏輯的清晰我去掉了一些回調(diào)代碼，不過剩下的好像除了一些狀態(tài)記錄變量的更新就是對map的put和get了畜埋，難道LRU算法的實現(xiàn)都是在最后一句的trimToSize()方法里莫绣？
public void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
...
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++;
}
...
}
}
依舊是對LinkedHashMap的操作，連獲取最久的數(shù)據(jù)都是使用LinkedHashMap.eldest()方法悠鞍，原來你是這樣的LruCache对室！看來LRU算法的核心實現(xiàn)都在LinkedHashMap里面了。
LinkedHashMap概覽
LinkedHashMap繼承自HashMap咖祭，所以內(nèi)部數(shù)據(jù)的存儲方式依然是數(shù)組加鏈表掩宜，有所不同的是，LinkedHashMap還單獨維護了一個雙向循環(huán)鏈表么翰，也正是這個鏈表賦予了它排序的功能牺汤。所以LinkedHashMap里的數(shù)據(jù)結構看起來就像這樣：
上面的虛線箭頭就代表著LinkedHashMap內(nèi)部維護的雙向循環(huán)鏈表，需要注意的是這里有一個鏈表頭Header浩嫌，而Header是一個空節(jié)點檐迟，且沒有存儲在Hash表內(nèi)，只是用來維持鏈表的正常運作的码耐。
而借助這個雙向鏈表追迟，LinkedHashMap內(nèi)部實現(xiàn)了兩種排序方法，由accessOrder狀態(tài)控制伐坏，當accessOrder為false時會按照數(shù)據(jù)插入的順序排序怔匣，為true時則會按照數(shù)據(jù)訪問的順序排序，而這也就是實現(xiàn)LRU算法的關鍵。
鏈表節(jié)點
要想弄清楚雙向鏈表是怎么實現(xiàn)LRU算法的每瞒，我們首先得搞清楚鏈表節(jié)點是怎么實現(xiàn)的：
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);
}
/**
* Removes this entry from the linked list.
*/
private void remove() {
before.after = after;
after.before = before;
}
/**
* Inserts this entry before the specified existing entry in the list.
*/
private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
...
}
和一般的雙向鏈表節(jié)點差不多金闽，LinkedHashMapEntry持有before和after兩個節(jié)點。而addBefore()方法確保了每個新插入的數(shù)據(jù)都在老數(shù)據(jù)的前面剿骨。重點則是這里的recordAccess()代芜，該方法會在每次數(shù)據(jù)被訪問的時候調(diào)用，如果accessOrder為true浓利，也就是按照數(shù)據(jù)訪問順序排序挤庇，該數(shù)據(jù)將會被移動到鏈表的最開始。下面我們就來看看LinkedHashMap到底是不是這樣實現(xiàn)的贷掖。
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;
}
get()方法的邏輯非常簡單嫡秕，調(diào)用父類的getEntry()方法獲取數(shù)據(jù)后，再調(diào)用recordAccess()方法將元素移動到鏈表開頭苹威，實現(xiàn)了越久沒有訪問的數(shù)據(jù)越靠后昆咽。
奇怪的put方法
put()方法就比較麻煩了，我在LinkedHashMap里找了一圈也沒有找到put()方法的實現(xiàn)牙甫，難道LinkedHashMap使用了父類HashMap的put()方法掷酗？可這又怎么做到維護雙向鏈表的更新呢？原來HashMap.put()方法在完成數(shù)據(jù)的插入之后窟哺，最終會回調(diào)一個createEntry()方法泻轰，而LinkedHashMap正是依靠重寫這個方法實現(xiàn)的鏈表更新：
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++;
}
就在這個方法里LinkedHashMap用自定義的LinkedHashMapEntry節(jié)點替換掉了HashMap創(chuàng)建的HashMapEntry，并且將節(jié)點加入到雙向鏈表的開頭且轨。
eldest方法
public Map.Entry<K, V> eldest() {
Entry<K, V> eldest = header.after;
return eldest != header ? eldest : null;
}
由于是雙向鏈表浮声，所以header另一邊肯定就是最后一個數(shù)據(jù)了。
至此殖告，整個LRU算法的實現(xiàn)也就呈現(xiàn)在大家眼前了阿蝶。
