之前經(jīng)常聽(tīng)到okhttp和glide都使用的lru緩存蘸吓，那什么是lru緩存呢善炫？android 又是如何實(shí)現(xiàn)lru緩存 的呢？
LRU库继，即Least Recently Used的縮寫(xiě)箩艺，就是最近最少使用，通俗意思就是最近最少被使用的會(huì)最先被從內(nèi)存中除去宪萄，舉個(gè)例子：內(nèi)存大小為3艺谆，我們要1，2雨膨，3擂涛，4读串，2聊记，3 六個(gè)數(shù)字,則：
首次調(diào)用1，內(nèi)存里為1恢暖；
調(diào)用2排监，內(nèi)存里為2，1
調(diào)用3杰捂，內(nèi)存里為3舆床，2，1
調(diào)用4嫁佳，內(nèi)存里為4挨队，3，2
調(diào)用2蒿往，內(nèi)存里為2盛垦，4，3
調(diào)用3瓤漏，內(nèi)存里為3腾夯，2，4
之后我們?cè)诖嫒胍粋€(gè)7蔬充，則內(nèi)存里為7蝶俱，3，2
這里我們看出來(lái)饥漫，最先被放進(jìn)內(nèi)存的榨呆，會(huì)被最先刪除，如果先被放入內(nèi)存而被調(diào)用庸队，則會(huì)放到最前面
我們知道了lrucache的原理愕提，那Android是怎么實(shí)現(xiàn)LruCache的呢馒稍？
在Android中，使用了LinkedHashMap來(lái)實(shí)現(xiàn)Lru,
我們知道浅侨，Java中HashMap是一個(gè)哈希表纽谒，hashmap本身是無(wú)順序的，而LinkedHashMap是有序的如输，LinkedHashMap使用雙向鏈表的形式來(lái)存儲(chǔ)MapEntry的鼓黔，我們依次往LinkedHashMap中插入1,2,3,4,5,6 六個(gè)數(shù)字，然后打印遍歷結(jié)果
然后我們?cè)趃et("key3"),再插入一個(gè)數(shù)據(jù)7不见，之后再遍歷
我們發(fā)現(xiàn)順序變成了1澳化，2，4稳吮，5缎谷，6，3灶似，7 其中g(shù)et 3后3到了表尾列林，插入7后7到了表尾，為什么會(huì)這樣呢酪惭？這和LinkedHashMap的實(shí)現(xiàn)有關(guān)：
這樣希痴，我們添加數(shù)據(jù)會(huì)添加到鏈表最后的位置，而LinkedHashMap在初始化中春感，可以設(shè)置為按插入順序來(lái)插入還是get讀取順序
LinkedHashMap在get數(shù)據(jù)的時(shí)候砌创，會(huì)先查找表，如果有鲫懒，則從鏈表里刪除嫩实，移動(dòng)到表尾，沒(méi)有窥岩，則返回null
//LinkedHashMap get數(shù)據(jù)
publicVget(Object key) {
? ? LinkedHashMapEntry e = (LinkedHashMapEntry)getEntry(key)甲献；//查找表里是否有
//數(shù)據(jù)，getEntry()為L(zhǎng)inkedHashMap繼承HashMap方法
? ? if(e ==null)
? ? ? ? return null;
? ? e.recordAccess(this);//調(diào)用LinkedHashMapEntry的recordAccess()方法
? ? returne.value;
}
我們看LinkedHashMapEntry類
/**
* LinkedHashMap entry.
*/
private static class LinkedHashMapEntry?extends HashMapEntry {
? ? LinkedHashMapEntrybefore,after;
? ? LinkedHashMapEntry(inthash,Kkey,Vvalue,HashMapEntry next) {
? ? super(hash,key,value,next);
? ? }
? ? private void remove() {
? ? ? ? before.after=after;
? ? ? ? after.before=before;
? ? }
? ? private void addBefore(LinkedHashMapEntry existingEntry) {
? ? ? ? after= existingEntry;//add value next指向header
? ? ? ? before= existingEntry.before;//add value before指向 之前表尾
? ? ? ? before.after=this;//之前表尾 next指向 add value
? ? ? ? after.before=this;//header before指向 add value
? ? }
? ? void recordAccess(HashMap m) {
? ? ? ? LinkedHashMap lm = (LinkedHashMap)m;
? ? ? ? if(lm.accessOrder) {//get模式
? ? ? ? ? ? lm.modCount++;
? ? ? ? ? ? remove();//從鏈表中刪除
? ? ? ? ? ? addBefore(lm.header);//添加到表尾
? ? ? ? }
? ? }
void recordRemoval(HashMap m) {
? ? ? ? remove();
? ? }
}
通過(guò)LinkedHashMapEntry的recordAccess我們看到谦秧，如果鏈表中有鏈表會(huì)先將原先的entry 從鏈表中刪除竟纳，然后再放到表尾，例如我們使用get方法get 上面 的value1后的鏈表為以下內(nèi)容：
我們發(fā)現(xiàn),LinkedHashMap和Lru的思路是相同的疚鲤，最近使用的被放在表尾（內(nèi)存頭）锥累，而最遠(yuǎn)時(shí)間使用的唄放在表頭（內(nèi)存尾），這樣集歇，就可以使用LinkedHashMap來(lái)實(shí)現(xiàn)lru
我們?cè)诔跏蓟疞ruCache的時(shí)候桶略，給LruCache設(shè)置最大大小
//LruCache get數(shù)據(jù)方法
public final V get(Kkey) {
? ? if(key ==null) {
? ? ? ? throw newNullPointerException("key == null");
? ? }
? ? V mapValue;
? ? synchronized(this) {
? ? ? ? mapValue =map.get(key);//從LinkedHashMap中查找，找到則放到表尾
? ? ? ? ? ? if(mapValue !=null) {
? ? ? ? ? ? ? ? hitCount++;//命中次數(shù)+1
? ? ? ? ? ? ? ? return mapValue;
? ? ? ? ? ? }
? ? ? ? ? ? missCount++;//沒(méi)有找到，miss次數(shù)加1
? ? }
? ? V? createdValue = create(key);//創(chuàng)建新的value
? ? if(createdValue ==null) {//創(chuàng)建失敗返回null
? ? ? ? ? ?return null;//未找到际歼，返回null
? ? }
? ? synchronized(this) {
? ? ? ? createCount++;//創(chuàng)建成功 惶翻，創(chuàng)建次數(shù)+1
? ? ? ? mapValue =map.put(key,createdValue);//put到linkedHashMap中，放到表尾
//如果表中原先有數(shù)據(jù)并且和creat的不一致鹅心，返回舊數(shù)據(jù)吕粗，否則返回null
? ? ? ? if(mapValue !=null) {
? ? ? ? ? ? // There was a conflict so undo that last put
? ? ? ? ? ? map.put(key,mapValue);//撤銷put 新的createValue
? ? ? ? ?}else{
? ? ? ? ? ? ? ?size+= safeSizeOf(key,createdValue);//size大小加上新加數(shù)據(jù)size
? ? ? ? }
? ?}
? ?if(mapValue !=null) {
? ? ? ? ?entryRemoved(false,key,createdValue,mapValue);
? ? ? ? ? return mapValue;
? ? ? ? ?}else{
? ? ? ? ? ? ? trimToSize(maxSize);//重新計(jì)算空間大小，是否能插入下條數(shù)據(jù)
? ? ? ? ? ? ? returncreatedValue;
? ? ? ?}
}
get 數(shù)據(jù)的時(shí)候旭愧，如果有數(shù)據(jù)則返回?cái)?shù)據(jù)颅筋，沒(méi)有則創(chuàng)建數(shù)據(jù)，如果創(chuàng)建失敗了输枯，則返回null议泵，成功了則插入數(shù)據(jù)并返回，創(chuàng)建成功其實(shí)和put是差不多的
put 的時(shí)候桃熄，先計(jì)算新加數(shù)據(jù)的大小先口，size增加，如果之前有key的數(shù)據(jù)瞳收，size再減去之前數(shù)據(jù)的大小碉京，最后再重新計(jì)算空間大小
trimToSize方法是重新計(jì)算空間，如果空間足夠缎讼，則插入收夸，不夠則從表中刪除最早插入數(shù)據(jù)坑匠，直到空間足夠位置血崭，每次在map中插入數(shù)據(jù)都要重新計(jì)算空間
//LruCatch釋放空間
public void trimToSize(intmaxSize) {
? ? while(true) {
? ? ? ? K key;
? ? ? ? V value;
? ? ? ? synchronized(this) {
? ? ? ? ? ? ?if(size<0|| (map.isEmpty() &&size!=0)) {
? ? ? ? ? ? ? ? ? throw newIllegalStateException(getClass().getName()
? ? ? ? ? ? ? ? ? ? ? ? ? +".sizeOf() is reporting inconsistent results!");
? ? ? ? ? ? ? }
? ? ? ? ? ? if(size<= maxSize) {//size<=maxSize，返回
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? ?Map.Entry toEvict =map.eldest();//獲取map最早插入數(shù)據(jù)
? ? ? ? ? ? ?if(toEvict ==null) {
? ? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? }
? ? ? ? ? ? key = toEvict.getKey();
? ? ? ? ? ? value = toEvict.getValue();
? ? ? ? ? ? map.remove(key);//刪除數(shù)據(jù)
? ? ? ? ? ? size-= safeSizeOf(key,value);//size減少
? ? ? ? ? ? ?evictionCount++;
? ? ? ? ?}
? ? ? ? ?entryRemoved(true,key,value, null);
? ? ?}
}
以上就是Android中自帶LruCache的基本實(shí)現(xiàn)厘灼，其實(shí)LruCache的思路就是通過(guò)LinkedHashMap去存儲(chǔ)或刪除數(shù)據(jù)夹纫，最主要的還是get(),put()以及釋放數(shù)據(jù) 的trimToSize()方法，當(dāng)然這個(gè)LruCache只是google簡(jiǎn)單實(shí)現(xiàn)的緩存设凹，我們可以根據(jù)需求使用LinkedHashMap自己去實(shí)現(xiàn)需要的LruCache
原創(chuàng)舰讹，轉(zhuǎn)載請(qǐng)注明
