“三級緩存”這個詞我想搞Android 都知道，與其相關(guān)的就是LruCache，今天我們就來說說LruCache。
LruCache（Least Recently Used），即最近最少使用算法。
在android源碼包名為android.util下就有這么一個類：LruCache，已經(jīng)幫我們實現(xiàn)好了LruCache算法。
在說LruCache之前，總少不要說LinkedHashMap，而LinkedHashMap是繼承于HashMap的，而HashMap相關(guān)東西可參考筆者之前寫的：HashMap、ArrayMap、SparseArray
我們還是直接上demo：
System.out.println("————————LinkedList——————————");
LinkedList<String> linkedList=new LinkedList<>();
linkedList.add("1");
linkedList.add("2");
linkedList.add("3");
linkedList.add("4");
System.out.println("獲取第二個數(shù)據(jù)："+linkedList.get(1));
for(String string:linkedList){
System.out.println("數(shù)據(jù)："+string);
}
System.out.println("—————————HashMap—————————");
HashMap<Integer,String> hashMap=new HashMap<>();
hashMap.put(10,"1");
hashMap.put(2,"2");
hashMap.put(3,"3");
hashMap.put(4,"4");
System.out.println("獲取key為2的數(shù)據(jù)："+hashMap.get(2));
for (Map.Entry<Integer,String> entry:hashMap.entrySet()){
System.out.println("數(shù)據(jù)："+entry.getValue());
}
打印出來的結(jié)果如下：
————————LinkedList——————————
獲取第二個數(shù)據(jù)：2
數(shù)據(jù)：1
數(shù)據(jù)：2
數(shù)據(jù)：3
數(shù)據(jù)：4
—————————HashMap—————————
獲取key為2的數(shù)據(jù)：2
數(shù)據(jù)：2
數(shù)據(jù)：3
數(shù)據(jù)：4
數(shù)據(jù)：1
很顯然LinkedList是有序的，而HashMap是無序的，所以，我們今天要說的LinkedHashMap就應運而生了，我們繼續(xù)看demo：
System.out.println("—————LinkedHashMap（無參）——————");
LinkedHashMap<Integer,String> linkedHashMap0=new LinkedHashMap<>();
linkedHashMap0.put(10,"1");
linkedHashMap0.put(2,"2");
linkedHashMap0.put(3,"3");
linkedHashMap0.put(4,"4");
System.out.println("獲取key為2的數(shù)據(jù)："+linkedHashMap0.get(2));
for (Map.Entry<Integer,String> entry:linkedHashMap0.entrySet()){
System.out.println("數(shù)據(jù)："+entry.getValue());
}
System.out.println("—————LinkedHashMap（有參）——————");
LinkedHashMap<Integer,String> linkedHashMap=new LinkedHashMap<>(0, 0.75f, true);
linkedHashMap.put(10,"1");
linkedHashMap.put(2,"2");
linkedHashMap.put(3,"3");
linkedHashMap.put(4,"4");
System.out.println("獲取key為2的數(shù)據(jù)："+linkedHashMap.get(2));
for (Map.Entry<Integer,String> entry:linkedHashMap.entrySet()){
System.out.println("數(shù)據(jù)："+entry.getValue());
}
打印出來的結(jié)果如下：
—————LinkedHashMap（無參）——————
獲取key為2的數(shù)據(jù)：2
數(shù)據(jù)：1
數(shù)據(jù)：2
數(shù)據(jù)：3
數(shù)據(jù)：4
—————LinkedHashMap（有參）——————
獲取key為2的數(shù)據(jù)：2
數(shù)據(jù)：1
數(shù)據(jù)：3
數(shù)據(jù)：4
數(shù)據(jù)：2
第一個LinkedHashMap無參實現(xiàn)了有序的Map
第二個LinkedHashMap有參（第三個參數(shù)accessOrder為true時）不止實現(xiàn)了有序的Map，而且將最近一次調(diào)用get獲取的數(shù)據(jù)置于隊尾。
好啦，LinkedHashMap基本的東西也就這樣子了，接下來我們來看看LruCache的源碼，首先在這個類最開始部分的注釋已經(jīng)給了使用示例，如下圖：
用法非常簡單，接下來我們看看其構(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);
}
原來在初始化的時候就創(chuàng)建了LinkedHashMap，而且就是上面LinkedHashMap有參的形式，就是利用其來實現(xiàn)最近最少使用算法的。
LruCache的源碼非常簡單，沒什么好說的，但是里面有一個方法卻讓人有點摸不著頭腦：
/**
* @param maxSize the maximum size of the cache before returning. May be -1
* to evict even 0-sized elements.
*/
private 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;
}
// BEGIN LAYOUTLIB CHANGE
// get the last item in the linked list.
// This is not efficient, the goal here is to minimize the changes
// compared to the platform version.
Map.Entry<K, V> toEvict = null;
for (Map.Entry<K, V> entry : map.entrySet()) {
toEvict = entry;
}
// END LAYOUTLIB CHANGE
if (toEvict == null) {
break;
}
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
這個方法是用來當存于LinkedHashMap中數(shù)據(jù)大小超過最大限制數(shù)時，將最近最少使用的數(shù)據(jù)進行移除的，按照LinkedHashMap特性，最近使用到會至于隊尾，然而我們摘取上面關(guān)鍵的代碼：
Map.Entry<K, V> toEvict = null;
for (Map.Entry<K, V> entry : map.entrySet()) {
toEvict = entry;
}
這樣找到的不就是最后一個元素嗎？如果按照這代碼執(zhí)行的話，被移除的就是最后一個元素，也就是最近使用過的元素，這根本就違背了“最近最少使用”原則嘛！
這到底是怎么回事？
我越看越不對勁，這代碼這么簡單我沒理由會理解錯的??！難不成我對“最近最少使用算法”本來就存在誤解？嚇得我趕緊百度一番，沒錯??！
于是，我寫了個demo來驗證一下：
LruCache<String,Integer> lruCache=new LruCache<>(4);
lruCache.put("1",1);
lruCache.put("2",2);
lruCache.put("3",3);
lruCache.put("4",4);
lruCache.get("2");
Map<String, Integer> snapshot = lruCache.snapshot();
for(Map.Entry<String,Integer> entry:snapshot.entrySet()){
LogUtil.loge("數(shù)據(jù)："+entry.getValue());
}
LogUtil.loge("------------------超出后------------------");
lruCache.put("5",5);
snapshot = lruCache.snapshot();
for(Map.Entry<String,Integer> entry:snapshot.entrySet()){
LogUtil.loge("數(shù)據(jù)："+entry.getValue());
}
打印出來的結(jié)果如下：
數(shù)據(jù)：1
數(shù)據(jù)：3
數(shù)據(jù)：4
數(shù)據(jù)：2
------------------超出后------------------
數(shù)據(jù)：3
數(shù)據(jù)：4
數(shù)據(jù)：2
數(shù)據(jù)：5
幸好結(jié)果正常，還有沒顛覆我對LruCache算法的理解O(∩_∩)O
那到底是為什么呢？干脆點，打斷點進去看看啊，然而我驚奇地發(fā)現(xiàn)，上面我有疑問的代碼變成了這樣子的：
Map.Entry<K, V> toEvict = map.eldest();
if (toEvict == null) {
break;
}
如果是這樣子的話倒是沒錯，因為在LinkedHashMap中有這么一個方法，返回的就是對頭元素，這樣確實符合LruCache算法，當超出時最開始加入的會被移除。
// Android-added: eldest(), for internal use in LRU caches
/**
* Returns the eldest entry in the map, or {@code null} if the map is empty.
* @hide
*/
public Map.Entry<K, V> eldest() {
return head;
}
其實，你用斷點進去發(fā)現(xiàn)代碼不一樣時，你會發(fā)現(xiàn)原來是android版本的問題，比如筆者用的夜神模擬器版本為19，其源碼就是上面那樣子的。而一開始我查看源碼時用的是項目里配的目標版本為28的源碼，這就是區(qū)別！
于是，我又打開了AndroidStudio自帶的API為28的模擬器，我想繼續(xù)進斷點看看，結(jié)果呢？詭異的事又發(fā)生了，怎么感覺錯行了呢？感覺執(zhí)行的和我看到的不是同一行呢？而且也沒有運行上面那個詭異代碼的循環(huán)，好像到附近也是一行跳過，倒跟API 19的那個有點像了····
最后，我終于注意到那詭異源碼上的那些英文注釋：
// BEGIN LAYOUTLIB CHANGE
// get the last item in the linked list.
// This is not efficient, the goal here is to minimize the changes
// compared to the platform version.
然后我一口氣查看最近幾個版本的源碼，發(fā)現(xiàn)原來在API 22的時候LruCache類中就出現(xiàn)了這樣子的注釋和詭異代碼，而API 23-27又恢復正常，現(xiàn)在API 28又變成這樣子詭異了，簡直了······
其實嘛，從上面的英文注釋我們大概也能猜到是為了兼容性吧，算了，這里就不作深究了，畢竟注釋也說清楚了，那代碼是無效的，我想這也是斷點進去會詭異的原因吧。
我們來說另外一個吧，LinkedHashMap如何獲取頭部元素和尾部元素呢？
最簡單的做法：
Map.Entry<Integer,String> first=null;
Map.Entry<Integer,String> last=null;
for (Map.Entry<Integer,String> entry:linkedHashMap.entrySet()){
if(first==null){
first=entry;
//break;
}
last=entry;
}
這樣寫當然沒毛病，就是在獲取尾部元素時效率有點低。
我們注意到上面LruCache中正常代碼有用到LinkedHashMap的一個方法：eldest()，根據(jù)注釋，我們知道這個方法是android為LruCache加的，而且使用了@hide注解，所以，我們是無法直接訪問到的，嘿嘿，這話的意思是，我們可以間接訪問到，必須滴，反射大法上！
try {
Field headField = linkedHashMap.getClass().getDeclaredField("head");
Field tailField = linkedHashMap.getClass().getDeclaredField("tail");
headField.setAccessible(true);
tailField.setAccessible(true);
Map.Entry<Integer,String> head = (Map.Entry<Integer, String>) headField.get(linkedHashMap);
Map.Entry<Integer,String> tail = (Map.Entry<Integer, String>) tailField.get(linkedHashMap);
if(head!=null){
System.out.println("頭部元素："+head.getValue());
}
if(tail!=null){
System.out.println("尾部元素："+tail.getValue());
}
} catch (IllegalAccessException e) {
e.printStackTrace();
} catch (NoSuchFieldException e) {
e.printStackTrace();
}
代碼也非常簡單，就不多說了！
