關于lruCache（最近最少使用）的算法，這是一個比較重要的算法聋亡，它的應用非常廣泛肘习，不僅僅在Android中使用，Linux系統(tǒng)等其他地方中也有使用坡倔；今天就來看一看這其中的奧秘漂佩；

講到LruCache，就不得不講一講LinkedHashMap罪塔，而對于LinkedHashMap投蝉，它繼承的是HashMap，那么我們就先從HashMap開始看起吧征堪；

注：此篇博客所講的所有知識都是在jdk1.8環(huán)境下的瘩缆，java8的hashmap相比之前的版本又做了一層優(yōu)化，當鏈表過長時（默認超過8）佃蚜，會改為采用紅黑樹這種自平衡的數(shù)據(jù)結構去進行存儲優(yōu)化

HashMap
我們知道庸娱，數(shù)據(jù)結構中的存在兩種常見的存儲結構，一個是數(shù)組谐算，一個是鏈表熟尉；兩者各有優(yōu)劣，首先數(shù)組的存儲空間在內(nèi)存中是連續(xù)的氯夷，這就就導致占用內(nèi)存嚴重臣樱，連續(xù)的大內(nèi)存進入老年代的可能性也會變大，但是正因為如此腮考，尋址就顯得簡單雇毫，也就是說查詢某個arr會有指定的下標，但是插入和刪除比較困難踩蔚，因為每次插入和刪除時棚放，如果數(shù)組在插入這個地方后面還有很多數(shù)據(jù)，那就要后面的數(shù)據(jù)整體往前或者往后移動馅闽。對于鏈表來說存儲空間是不連續(xù)的飘蚯，占用內(nèi)存比較寬松馍迄，它的基本結構是一個節(jié)點（node）都會包含下一個節(jié)點的信息（如果是雙向鏈表會存在兩個信息一個指向上一個一個指向下一個），正因為如此尋址就會變得比較困難局骤，插入和刪除就顯得容易攀圈，鏈表插入和刪除的時候只需要修改節(jié)點指向信息就可以了。

那么兩者各有優(yōu)劣峦甩，將它們兩者結合起來會有什么效果呢赘来？自然早就有大神嘗試過了，并且嘗試的很成功凯傲，它的產(chǎn)物就是HashMap哈希表犬辰，也叫散列表；

HashMap的主干是一個數(shù)組冰单，里面存儲的是一個個的Node幌缝，Node中包含了哈希值，key诫欠，value和下一個Node的引用涵卵；

Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
存儲在HashMap中的每一個值都需要一個key，這是為什么呢荒叼？這個問題可以再問細一點缘厢，hashmap是如何存放數(shù)據(jù)的？
我們先來看看他的一些基本屬性：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
這個屬性表示HashMap的初始容量大小是16甩挫；

static final int MAXIMUM_CAPACITY = 1 << 30;
最大容量為2^30;

static final float DEFAULT_LOAD_FACTOR = 0.75f;
這個表示加載因子默認為0.75贴硫，代表hashmap的填充程度，加載因子越大,填滿的元素越多,好處是,空間利用率高了,但:沖突的機會加大了.鏈表長度會越來越長,查找效率降低伊者。

反之,加載因子越小,填滿的元素越少,好處是:沖突的機會減小了,但:空間浪費多了.表中的數(shù)據(jù)將過于稀疏（很多空間還沒用英遭，就開始擴容了）

沖突的機會越大,則查找的成本越高.

因此,必須在 "沖突的機會"與"空間利用率"之間尋找一種平衡與折衷. 這種平衡與折衷本質上是數(shù)據(jù)結構中有名的"時-空"矛盾的平衡與折衷.

如果機器內(nèi)存足夠，并且想要提高查詢速度的話可以將加載因子設置小一點亦渗；相反如果機器內(nèi)存緊張挖诸，并且對查詢速度沒有什么要求的話可以將加載因子設置大一點。不過一般我們都不用去設置它法精，讓它默認為0.75就可以了多律；

/**

• The bin count threshold for using a tree rather than list for a
• bin. Bins are converted to trees when adding an element to a
• bin with at least this many nodes. The value must be greater
• than 2 and should be at least 8 to mesh with assumptions in
• tree removal about conversion back to plain bins upon
• shrinkage.
  */
  static final int TREEIFY_THRESHOLD = 8;

/**

• The bin count threshold for untreeifying a (split) bin during a
• resize operation. Should be less than TREEIFY_THRESHOLD, and at
• most 6 to mesh with shrinkage detection under removal.
  */
  static final int UNTREEIFY_THRESHOLD = 6;
  臨界值，這個字段主要是用于當HashMap的size大于它的時候搂蜓，需要觸發(fā)resize()方法進行擴容
  構造方法：

public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
可以清晰的看到當new一個HashMap時狼荞，并沒有為數(shù)組分配內(nèi)存空間（有一個傳入map參數(shù)的構造方法除外）；

幾個核心方法：

put方法實際調(diào)用的就是putVal方法帮碰，所以我們先看putVal方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
這里的邏輯由于是java8相味，所以會復雜一點，里面有幾個關鍵點殉挽，記錄下來丰涉，對比著源碼看：

（1）putVal方法其實就可以理解為put方法拓巧，我們使用hashmap的時候，什么時候才會使用put方法呢一死，當你想要存儲數(shù)據(jù)的時候會調(diào)用肛度，那么putVal方法的邏輯就是為了把你需要存儲的數(shù)據(jù)按位置存放好就可以了；

（2）具體的存放邏輯是通過復雜的if判斷來完成的投慈，首先會判斷當前通過key和hash函數(shù)計算出的數(shù)組下標位置的是否為null贤斜，如果是空，直接將Node對象存進去逛裤；如果不為空，那么就將key值與桶中的Node的key一一比較猴抹，在比較的過程中带族，如果桶中的對象是由紅黑樹構造而來，那么就使用紅黑樹的方法去進行存儲蟀给，如果不是蝙砌，那么就繼續(xù)判斷當前桶中的元素是否大于8，大于8的話就使用紅黑樹處理（調(diào)用treeifybin方法）跋理，如果小于8择克，那么進行最后的判斷是否key值相同，如果相同前普，就直接將舊的node對象替換為新的node對象肚邢；這樣就保證了存儲的正確性；

（3）在putVal中有這么一句

++modCount;
這里的modCount的作用是用來判斷當前HashMap是否在由一個線程操作拭卿，因為hashmap本身是線程不安全的骡湖，多線程操作會造成其中數(shù)據(jù)不安全等多種問題，modcount記錄的是put的次數(shù)峻厚，如果modcount不等于put的node的個數(shù)的話响蕴，就代表有多個線程同時操作，就會報ConcurrentModificationException異常惠桃；

再來看看get方法浦夷，get方法其實調(diào)用的是getNode方法

final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
這里也有幾個點：

bucket里的第一個節(jié)點，直接命中辜王；
如果有沖突劈狐，則通過key.equals(k)去查找對應的entry
若為樹，則在樹中通過key.equals(k)查找呐馆，O(logn)懈息；
若為鏈表，則在鏈表中通過key.equals(k)查找摹恰，O(n)辫继。
接下來看看hashmap中邏輯最復雜但是也最為經(jīng)典的擴容機制怒见，他主要是由resize方法實現(xiàn)的：

final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
說到擴容，就不得不提到上述的幾個屬性

（1）Capacity：hashmap的容量姑宽，其實就是hashmap數(shù)組的長度遣耍，也就是capacity=array.length

（2）threshold：擴容的臨界值，當數(shù)組中元素的個數(shù)達到這個值的時候炮车，就會進行擴容

（3）loadFactor：加載因子舵变，表示數(shù)組的填充程度，默認為0.75（不要輕易修改）

這三者的關系是threshold/loadFactor=Capacity瘦穆；

resize方法中主要是做了如何去擴容的邏輯判斷纪隙，其中包括

（1）如果此時hashmap的容量大于2^{30，那么就不擴容扛或，不擴容的方法是將threshold的值賦值為2}30-1绵咱，就不會擴容了

（2）一次擴容的大小是擴容一倍，如果初始大小為16熙兔，那么擴容后為32

（3）Java8的hashmap由于引入了紅黑樹悲伶，所以如果采用桶內(nèi)的存儲結構為紅黑樹的話，那么會調(diào)用相應紅黑樹的算法住涉，如果是鏈表麸锉，那么就會將鏈表拆分為兩個鏈表，再將兩個鏈表重新放入相對應的的位置中舆声，這里是需要重新計算每個元素的hash值的花沉，因為要保證，舊的數(shù)組和新的數(shù)組的元素的索引要保證相同媳握；

到這里主穗，有幾個問題要回答：

什么時候會使用HashMap？他有什么特點毙芜？

是基于Map接口的實現(xiàn)忽媒，存儲鍵值對時，它可以接收null的鍵值腋粥，是非同步的晦雨，HashMap存儲著Entry(hash, key, value, next)對象。

你知道HashMap的工作原理嗎隘冲？

通過hash的方法闹瞧，通過put和get存儲和獲取對象。存儲對象時展辞，我們將K/V傳給put方法時奥邮，它調(diào)用hashCode計算hash從而得到bucket位置，進一步存儲，HashMap會根據(jù)當前bucket的占用情況自動調(diào)整容量(超過Load Facotr則resize為原來的2倍)洽腺。獲取對象時脚粟，我們將K傳給get，它調(diào)用hashCode計算hash從而得到bucket位置蘸朋，并進一步調(diào)用equals()方法確定鍵值對核无。如果發(fā)生碰撞的時候，Hashmap通過鏈表將產(chǎn)生碰撞沖突的元素組織起來藕坯，在Java 8中团南，如果一個bucket中碰撞沖突的元素超過某個限制(默認是8)，則使用紅黑樹來替換鏈表炼彪，從而提高速度吐根。

你知道get和put的原理嗎？equals()和hashCode()的都有什么作用辐马？

通過對key的hashCode()進行hashing拷橘，并計算下標( n-1 & hash)，從而獲得buckets的位置齐疙。如果產(chǎn)生碰撞，則利用key.equals()方法去鏈表或樹中去查找對應的節(jié)點

你知道hash的實現(xiàn)嗎旭咽？為什么要這樣實現(xiàn)贞奋？

在Java 1.8的實現(xiàn)中，是通過hashCode()的高16位異或低16位實現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)穷绵，主要是從速度轿塔、功效、質量來考慮的仲墨，這么做可以在bucket的n比較小的時候勾缭，也能保證考慮到高低bit都參與到hash的計算中，同時不會有太大的開銷目养。

如果HashMap的大小超過了負載因子(load factor)定義的容量俩由，怎么辦？

如果超過了負載因子(默認0.75)癌蚁，則會重新resize一個原來長度兩倍的HashMap幻梯，并且重新調(diào)用hash方法。
關于Java集合的小抄中是這樣描述的：
以Entry[]數(shù)組實現(xiàn)的哈希桶數(shù)組努释，用Key的哈希值取模桶數(shù)組的大小可得到數(shù)組下標碘梢。
插入元素時苗胀，如果兩條Key落在同一個桶(比如哈希值1和17取模16后都屬于第一個哈希桶)忠寻，Entry用一個next屬性實現(xiàn)多個Entry以單向鏈表存放，后入桶的Entry將next指向桶當前的Entry聋迎。
查找哈希值為17的key時，先定位到第一個哈希桶恩沛，然后以鏈表遍歷桶里所有元素在扰，逐個比較其key值。
當Entry數(shù)量達到桶數(shù)量的75%時(很多文章說使用的桶數(shù)量達到了75%复唤，但看代碼不是)健田，會成倍擴容桶數(shù)組，并重新分配所有原來的Entry佛纫，所以這里也最好有個預估值妓局。
取模用位運算(hash & (arrayLength-1))會比較快，所以數(shù)組的大小永遠是2的N次方呈宇， 你隨便給一個初始值比如17會轉為32好爬。默認第一次放入元素時的初始值是16。
iterator()時順著哈希桶數(shù)組來遍歷甥啄，看起來是個亂序存炮。

當兩個對象的hashcode相同會發(fā)生什么？

因為hashcode相同蜈漓，所以它們的bucket位置相同穆桂，‘碰撞’會發(fā)生。因為HashMap使用鏈表存儲對象融虽，這個Entry(包含有鍵值對的Map.Entry對象)會存儲在鏈表中享完。

如果兩個鍵的hashcode相同，你如何獲取值對象有额？

找到bucket位置之后般又，會調(diào)用keys.equals()方法去找到鏈表中正確的節(jié)點，最終找到要找的值對象巍佑。因此茴迁，設計HashMap的key類型時，如果使用不可變的萤衰、聲明作final的對象堕义，并且采用合適的equals()和hashCode()方法的話，將會減少碰撞的發(fā)生脆栋，提高效率胳螟。不可變性能夠緩存不同鍵的hashcode，這將提高整個獲取對象的速度筹吐，使用String糖耸，Interger這樣的wrapper類作為鍵是非常好的選擇

如果HashMap的大小超過了負載因子(load factor)定義的容量，怎么辦丘薛？

默認的負載因子大小為0.75嘉竟，也就是說，當一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣舍扰，將會創(chuàng)建原來HashMap大小的兩倍的bucket數(shù)組倦蚪，來重新調(diào)整map的大小，并將原來的對象放入新的bucket數(shù)組中边苹。這個過程叫作rehashing陵且，因為它調(diào)用hash方法找到新的bucket位置

你了解重新調(diào)整HashMap大小存在什么問題嗎？

當重新調(diào)整HashMap大小的時候个束，確實存在條件競爭慕购，因為如果兩個線程都發(fā)現(xiàn)HashMap需要重新調(diào)整大小了，它們會同時試著調(diào)整大小茬底。在調(diào)整大小的過程中沪悲，存儲在鏈表中的元素的次序會反過來，因為移動到新的bucket位置的時候阱表，HashMap并不會將元素放在鏈表的尾部殿如，而是放在頭部，這是為了避免尾部遍歷(tail traversing)最爬。如果條件競爭發(fā)生了涉馁，那么就死循環(huán)了。因此在并發(fā)環(huán)境下爱致，我們使用CurrentHashMap來替代HashMap

為什么String, Interger這樣的wrapper類適合作為鍵烤送？

因為String是不可變的，也是final的蒜鸡，而且已經(jīng)重寫了equals()和hashCode()方法了胯努。其他的wrapper類也有這個特點牢裳。不可變性是必要的逢防，因為為了要計算hashCode()，就要防止鍵值改變蒲讯，如果鍵值在放入時和獲取時返回不同的hashcode的話忘朝，那么就不能從HashMap中找到你想要的對象。不可變性還有其他的優(yōu)點如線程安全判帮。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的局嘁，那么請這么做吧。因為獲取對象的時候要用到equals()和hashCode()方法晦墙，那么鍵對象正確的重寫這兩個方法是非常重要的悦昵。如果兩個不相等的對象返回不同的hashcode的話，那么碰撞的幾率就會小些晌畅，這樣就能提高HashMap的性能

這就是關于HashMap的解析但指，下面看看LinkedHashMap的源碼解析，LinkedHashMap繼承自HashMap，所以理解了HashMap棋凳，LinkedHashMap就很簡單了拦坠；

LinkedHashMap
首先看一下他的繼承關系：

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
繼承HashMap，實現(xiàn)了Map接口

再看看他的成員變量

transient LinkedHashMapEntry<K,V> head;
用于指向雙向鏈表的頭部

transient LinkedHashMapEntry<K,V> tail;
用于指向雙向鏈表的尾部

final boolean accessOrder;
用于LinkedHashMap的迭代順序剩岳，true表示基于訪問的順序來排列贞滨，也就是說，最近訪問的Node放置在鏈表的尾部拍棕，false表示按照插入的順序來排列晓铆；

構造方法：

跟HashMap類似的構造方法這里就不一一贅述了，里面唯一的區(qū)別就是添加了前面提到的accessOrder莫湘，默認賦值為false——按照插入順序來排列尤蒿，這里主要說明一下不同的構造方法。

public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
get（）方法：

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;
}
這里的afterNodeAccess方法是按照訪問順序排列的關鍵：

void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMapEntry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
這里的get方法比hashmap就復雜了一些幅垮，因為他在得到值的同時腰池，還需要將得到的元素放在鏈表的尾部，至于是怎么放置的忙芒，無非就是數(shù)據(jù)結構中的雙向循環(huán)鏈表的知識示弓，分四種情況：

正常情況下：查詢的p在鏈表中間，那么將p設置到末尾后呵萨，它原先的前節(jié)點b和后節(jié)點a就變成了前后節(jié)點奏属。

情況一：p為頭部，前一個節(jié)點b不存在潮峦，那么考慮到p要放到最后面囱皿，則設置p的后一個節(jié)點a為head
情況二：p為尾部，后一個節(jié)點a不存在忱嘹，那么考慮到統(tǒng)一操作嘱腥，設置last為b
情況三：p為鏈表里的第一個節(jié)點，head=p

put方法：

在LinkedHashMap中是找不到put方法的拘悦，因為齿兔，它使用的是父類HashMap的put方法，不過它將hashmap中的put方法中調(diào)用的相關方法去重寫了础米，具體的就是newNode（）分苇，afterNodeAccess和afterNodeInsertion方法

先看newNode方法：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMapEntry<K,V> p =
new LinkedHashMapEntry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
LinkedHashMapEntry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
主要功能就是把新加的元素添加到鏈表的尾部；

有關LinkedHashMap屁桑，因為與HashMap相似医寿，我只提了里面的存儲順序問題，這也是LinkedHashMap的最主要的功能蘑斧；

LruCache內(nèi)存緩存原理
在講LruCache之前 靖秩，先看看它是怎么使用的艾帐，拿它在圖片緩存的應用來說，看下面的代碼：

private LruCache<String,Bitmap> lruCache;

public MemoryCacheUtils(){
//獲取手機最大內(nèi)存的1/8
long memory=Runtime.getRuntime().maxMemory()/8;
lruCache=new LruCache<String, Bitmap>((int)memory){
@Override
protected int sizeOf(String key, Bitmap value) {
return value.getByteCount();
}
};
}

/**

• 從內(nèi)存中讀圖片
• @param url
• @return
  */
  public Bitmap getBitmapFromMemory(String url) {
  Bitmap bitmap = lruCache.get(url);
  return bitmap;
  }

public void setBitmapToMemory(String url, Bitmap bitmap) {
lruCache.put(url,bitmap);
}
這是最簡單的圖片的三級緩存中的內(nèi)存緩存的寫法盆偿，我們先看使用構造器new一個LruCache發(fā)生了什么：

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);
}
可以看見LruCache的構造器主要是定義了緩存的最大值柒爸，并且調(diào)用了LinkedHashMap的三個參數(shù)的構造方法，保證按照訪問順序來排列元素事扭，生成一個LinkedHashMap對象捎稚，賦值給map；

在看它的get方法

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++;
}

/*
 * Attempt to create a value. This may take a long time, and the map
 * may be different when create() returns. If a conflicting value was
 * added to the map while create() was working, we leave that value in
 * the map and release the created value.
 */

V createdValue = create(key);
if (createdValue == null) {
    return null;
}

synchronized (this) {
    createCount++;
    mapValue = map.put(key, createdValue);

    if (mapValue != null) {
        // There was a conflict so undo that last put
        map.put(key, mapValue);
    } else {
        size += safeSizeOf(key, createdValue);
    }
}

if (mapValue != null) {
    entryRemoved(false, key, createdValue, mapValue);
    return mapValue;
} else {
    trimToSize(maxSize);
    return createdValue;
}

}
這里面主要做了兩件事求橄，首先會根據(jù)key查找map中是否存在對應的Value今野，也就是對應key值的緩存，如果找到罐农，直接命中条霜，返回此份緩存，如果沒有找到涵亏，會調(diào)用create（）方法去嘗試創(chuàng)建一個Value宰睡，但是我看了create（）源碼，是返回null的气筋；

protected V create(K key) {
return null;
}
也就是說拆内，如果你不主動重寫create方法，LruCache是不會幫你創(chuàng)建Value的宠默；其實麸恍，正常情況下，不需要去重寫create方法的搀矫，因為一旦我們get不到緩存抹沪，就應該去網(wǎng)絡請求了；

再看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;

}
主要邏輯是瓤球，計算新增加的大小融欧，加入size，然后把key-value放入map中冰垄，如果是更新舊的數(shù)據(jù)（map.put(key, value)會返回之前的value）蹬癌，則減去舊數(shù)據(jù)的大小权她，并調(diào)用entryRemoved(false, key, previous, value)方法通知舊數(shù)據(jù)被更新為新的值虹茶，最后也是調(diào)用trimToSize(maxSize)修整緩存的大小。

LruCache大致源碼就是這樣隅要，它對LRU算法的實現(xiàn)主要是通過LinkedHashMap來完成蝴罪。另外，使用LRU算法步清，說明我們需要設定緩存的最大大小要门，而緩存對象的大小在不同的緩存類型當中的計算方法是不同的虏肾，計算的方法通過protected int sizeOf(K key, V value)實現(xiàn)，我們要緩存Bitmap對象欢搜，則需要重寫這個方法封豪，并返回bitmap對象的所有像素點所占的內(nèi)存大小之和。還有炒瘟，LruCache在實現(xiàn)的時候考慮到了多線程的訪問問題吹埠，所以在對map進行更新時，都會加上同步鎖疮装。

DiskLruCache硬盤緩存原理
講完LruCache之后缘琅，我們趁熱打鐵，抓緊看一下DiskLruCache硬盤緩存的相關原理廓推，DiskLruCache和LruCache內(nèi)部都是使用了LinkedHashMap去實現(xiàn)緩存算法的刷袍，只不過前者針對的是將緩存存在本地，而后者是直接將緩存存在內(nèi)存樊展；

先看看它是如何使用的吧呻纹，這里和LruCache不一樣，DiskLruCache不在Android API內(nèi)专缠，所以如果我們要使用它居暖，必須將其源碼下載，可以點擊這里進行下載藤肢，下載完成后太闺，導入到你自己的項目中就可以使用了；

首先你要知道嘁圈，DiskLruCache是不能new出實例的省骂，如果我們要創(chuàng)建一個DiskLruCache的實例，則需要調(diào)用它的open()方法最住，接口如下所示：

public static DiskLruCache open(File directory, int appVersion, int valueCount, long maxSize)
open()方法接收四個參數(shù)钞澳，第一個參數(shù)指定的是數(shù)據(jù)的緩存地址，第二個參數(shù)指定當前應用程序的版本號涨缚，第三個參數(shù)指定同一個key可以對應多少個緩存文件轧粟，基本都是傳1，第四個參數(shù)指定最多可以緩存多少字節(jié)的數(shù)據(jù)脓魏。

其中緩存地址通常都會存放在 /sdcard/Android/data/<application package>/cache 這個路徑下面兰吟，但同時我們又需要考慮如果這個手機沒有SD卡，或者SD正好被移除了的情況茂翔，因此比較優(yōu)秀的程序都會專門寫一個方法來獲取緩存地址混蔼，如下所示：

public File getDiskCacheDir(Context context, String uniqueName) {
String cachePath;
if (Environment.MEDIA_MOUNTED.equals(Environment.getExternalStorageState()) || !Environment.isExternalStorageRemovable()) {
cachePath = context.getExternalCacheDir().getPath();
} else {
cachePath = context.getCacheDir().getPath();
}
return new File(cachePath + File.separator + uniqueName);
}
可以看到，當SD卡存在或者SD卡不可被移除的時候珊燎，就調(diào)用getExternalCacheDir()方法來獲取緩存路徑惭嚣，否則就調(diào)用getCacheDir()方法來獲取緩存路徑遵湖。前者獲取到的就是 /sdcard/Android/data/<application package>/cache 這個路徑，而后者獲取到的是 /data/data/<application package>/cache 這個路徑晚吞。

接著是應用程序版本號延旧，我們可以使用如下代碼簡單地獲取到當前應用程序的版本號：

public int getAppVersion(Context context) {
try {
PackageInfo info = context.getPackageManager().getPackageInfo(context.getPackageName(), 0);
return info.versionCode;
} catch (PackageManager.NameNotFoundException e) {
e.printStackTrace();
}
return 1;
}
后面兩個參數(shù)就沒什么需要解釋的了，第三個參數(shù)傳1槽地，第四個參數(shù)通常傳入10M的大小就夠了垄潮，這個可以根據(jù)自身的情況進行調(diào)節(jié)。

因此闷盔，一個非常標準的open()方法就可以這樣寫：

private DiskLruCache getDiskLruCache(Context context){
try {
File cacheDir = getDiskCacheDir(context, "bitmap");
if (!cacheDir.exists()) {
cacheDir.mkdirs();
}
mDiskLruCache = DiskLruCache.open(cacheDir, getAppVersion(context), 1, 10 * 1024 * 1024);
} catch (IOException e) {
e.printStackTrace();
}
return mDiskLruCache;
}
關于寫入緩存：

寫入的操作是借助DiskLruCache.Editor這個類完成的弯洗。類似地，這個類也是不能new的逢勾，需要調(diào)用DiskLruCache的edit()方法來獲取實例牡整，接口如下所示：

public Editor edit(String key) throws IOException
現(xiàn)在就可以這樣寫來得到一個DiskLruCache.Editor的實例：
public void setBitmapToLocal(Context context,String url, InputStream inputStream) {
BufferedOutputStream out = null;
BufferedInputStream in = null;
try {
DiskLruCache.Editor editor = getDiskLruCache(context).edit(getMD5String(url));
if (editor != null) {
OutputStream outputStream = editor.newOutputStream(0);
in = new BufferedInputStream(inputStream, 8 * 1024);
out = new BufferedOutputStream(outputStream, 8 * 1024);
int b;
while ((b = in.read()) != -1) {
out.write(b);
}
editor.commit();
}
mDiskLruCache.flush();
} catch (IOException e) {
e.printStackTrace();
}
}
讀取緩存：

讀取的方法要比寫入簡單一些，主要是借助DiskLruCache的get()方法實現(xiàn)的溺拱，接口如下所示：

public synchronized Snapshot get(String key) throws IOException
所以逃贝，你可以這樣讀取：

public Bitmap getBitmapFromLocal(String url) {
try {
DiskLruCache.Snapshot snapShot = mDiskLruCache.get(getMD5String(url));
if (snapShot != null) {
InputStream is = snapShot.getInputStream(0);
Bitmap bitmap = BitmapFactory.decodeStream(is);
return bitmap;
}
} catch (IOException e) {
e.printStackTrace();
}
return null;
}
了解怎么使用還不夠迫摔，DiskLruCache會自動生成journal文件沐扳，這個文件是日志文件，主要記錄的是緩存的操作句占；

第一行是個固定的字符串“l(fā)ibcore.io.DiskLruCache”沪摄，標志著我們使用的是DiskLruCache技術。第二行是DiskLruCache的版本號纱烘，這個值是恒為1的杨拐。第三行是應用程序的版本號，我們在open()方法里傳入的版本號是什么這里就會顯示什么擂啥。第四行是valueCount哄陶，這個值也是在open()方法中傳入的，通常情況下都為1哺壶。第五行是一個空行屋吨。前五行也被稱為journal文件的頭，這部分內(nèi)容還是比較好理解的

第六行是以一個DIRTY前綴開始的山宾，后面緊跟著緩存圖片的key至扰。通常我們看到DIRTY這個字樣都不代表著什么好事情，意味著這是一條臟數(shù)據(jù)塌碌。沒錯渊胸，每當我們調(diào)用一次DiskLruCache的edit()方法時旬盯，都會向journal文件中寫入一條DIRTY記錄台妆，表示我們正準備寫入一條緩存數(shù)據(jù)翎猛，但不知結果如何。然后調(diào)用commit()方法表示寫入緩存成功接剩，這時會向journal中寫入一條CLEAN記錄切厘，意味著這條“臟”數(shù)據(jù)被“洗干凈了”，調(diào)用abort()方法表示寫入緩存失敗懊缺，這時會向journal中寫入一條REMOVE記錄疫稿。也就是說，每一行DIRTY的key鹃两，后面都應該有一行對應的CLEAN或者REMOVE的記錄遗座，否則這條數(shù)據(jù)就是“臟”的，會被自動刪除掉俊扳。其中152313是圖片的大小

接下來我們就開始對源碼分析：

在分析之前途蒋，我們可以這樣想，有了上面的LruCache緩存方式之后馋记，DiskLruCache的原理會是怎樣号坡，LruCache將圖片存到內(nèi)存中，DiskLruCache存在硬盤中梯醒，那么不就相當于把內(nèi)存中的圖片存到本地中么宽堆，這么想會簡單許多：

首先還是從open入口看：

public static DiskLruCache open(File directory, int appVersion, int valueCount, long maxSize)
throws IOException {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
if (valueCount <= 0) {
throw new IllegalArgumentException("valueCount <= 0");
}

// If a bkp file exists, use it instead.
File backupFile = new File(directory, JOURNAL_FILE_BACKUP);
if (backupFile.exists()) {
File journalFile = new File(directory, JOURNAL_FILE);
// If journal file also exists just delete backup file.
if (journalFile.exists()) {
backupFile.delete();
} else {
renameTo(backupFile, journalFile, false);
}
}

// Prefer to pick up where we left off.
DiskLruCache cache = new DiskLruCache(directory, appVersion, valueCount, maxSize);
if (cache.journalFile.exists()) {
try {
cache.readJournal();
cache.processJournal();
return cache;
} catch (IOException journalIsCorrupt) {
System.out
.println("DiskLruCache "
+ directory
+ " is corrupt: "
+ journalIsCorrupt.getMessage()
+ ", removing");
cache.delete();
}
}

// Create a new empty cache.
directory.mkdirs();
cache = new DiskLruCache(directory, appVersion, valueCount, maxSize);
cache.rebuildJournal();
return cache;
}
DiskLruCache對象初始化初始化的時候做的事情就兩件事：第一通過日志文件頭信息去判斷之前緩存是否可用、第二解析之前緩存信息到LinkedHashMap茸习；

首先判斷是否有日志文件畜隶，如果有日志文件說明之前有緩存過信息，對上次的緩存信息做處理号胚，關鍵的東西在journal文件里面代箭，從journal文件解析到之前的緩存信息；在日志文件中涕刚，去讀里面之前的緩存信息嗡综。判斷緩存是否過期，同時把之前的緩存信息記錄保存到lruEntries杜漠，Map里面去极景。對讀到的上次緩存信息做處理，計算size驾茴，把沒有調(diào)用Edit.commit（）的緩存剔除掉

讀日志文件的方法readJournal（）

private void readJournal() throws IOException {
StrictLineReader reader = new StrictLineReader(new FileInputStream(journalFile), Util.US_ASCII);
try {
String magic = reader.readLine();
String version = reader.readLine();
String appVersionString = reader.readLine();
String valueCountString = reader.readLine();
String blank = reader.readLine();
if (!MAGIC.equals(magic)
|| !VERSION_1.equals(version)
|| !Integer.toString(appVersion).equals(appVersionString)
|| !Integer.toString(valueCount).equals(valueCountString)
|| !"".equals(blank)) {
throw new IOException("unexpected journal header: [" + magic + ", " + version + ", "
+ valueCountString + ", " + blank + "]");
}

int lineCount = 0;
while (true) {
  try {
    readJournalLine(reader.readLine());
    lineCount++;
  } catch (EOFException endOfJournal) {
    break;
  }
}
redundantOpCount = lineCount - lruEntries.size();

// If we ended on a truncated line, rebuild the journal before appending to it.
if (reader.hasUnterminatedLine()) {
  rebuildJournal();
} else {
  journalWriter = new BufferedWriter(new OutputStreamWriter(
      new FileOutputStream(journalFile, true), Util.US_ASCII));
}

} finally {
Util.closeQuietly(reader);
}
}
其中主要做兩件事：

（1）讀日志文件的頭部信息盼樟，標記，緩存版本锈至，應用版本晨缴，進而判斷日志文件是否過期

（2）把日志文件的緩存記錄讀取到lruEntries，map中峡捡；

處理緩存信息的方法processJournal（）方法

private void processJournal() throws IOException {
deleteIfExists(journalFileTmp);
for (Iterator<Entry> i = lruEntries.values().iterator(); i.hasNext(); ) {
Entry entry = i.next();
if (entry.currentEditor == null) {
for (int t = 0; t < valueCount; t++) {
size += entry.lengths[t];
}
} else {
entry.currentEditor = null;
for (int t = 0; t < valueCount; t++) {
deleteIfExists(entry.getCleanFile(t));
deleteIfExists(entry.getDirtyFile(t));
}
i.remove();
}
}
}
這里主要做兩件事：

（1）計算整個緩存文件的大小

（2）把正在被編輯的key（上次保存緩存的時候沒有調(diào)用Edit.commit()）,可以認為是沒有寫成功的緩存击碗，重置掉（相應的緩存文件刪除筑悴，并且從lruEntries中刪除）

保存緩存操作edit

private synchronized Editor edit(String key, long expectedSequenceNumber) throws IOException {
checkNotClosed();
validateKey(key);
Entry entry = lruEntries.get(key);
if (expectedSequenceNumber != ANY_SEQUENCE_NUMBER && (entry == null
|| entry.sequenceNumber != expectedSequenceNumber)) {
return null; // Snapshot is stale.
}
if (entry == null) {
entry = new Entry(key);
lruEntries.put(key, entry);
} else if (entry.currentEditor != null) {
return null; // Another edit is in progress.
}

Editor editor = new Editor(entry);
entry.currentEditor = editor;

// Flush the journal before creating files to prevent file leaks.
journalWriter.write(DIRTY + ' ' + key + '\n');
journalWriter.flush();
return editor;
}
要保存緩存的時候，要做兩件事一是保存緩存文件稍途，二是寫緩存日志文件阁吝。為了保存緩存文件我們寫的得到Edit對象，然后通過Edit對象得到OutputStream對象然后才可以寫入文件械拍，最后commit（）提交保存突勇。總的來說五個步驟坷虑；

（1）調(diào)用edit（）得到Edit對象

（2）調(diào)用Editt.newOutputStream（）得到OutputStream

（3）調(diào)用OutputStream.write（）把緩存寫入文件

（4）Edit.commit（）確定緩存寫入【commit不用每次都調(diào)用甲馋，可以挑個合適的時間調(diào)用】

（5）最后調(diào)用flush（）。

讀取緩存操作get

public synchronized Snapshot get(String key) throws IOException {
checkNotClosed();
validateKey(key);
Entry entry = lruEntries.get(key);
if (entry == null) {
return null;
}

if (!entry.readable) {
return null;
}

// Open all streams eagerly to guarantee that we see a single published
// snapshot. If we opened streams lazily then the streams could come
// from different edits.
InputStream[] ins = new InputStream[valueCount];
try {
for (int i = 0; i < valueCount; i++) {
ins[i] = new FileInputStream(entry.getCleanFile(i));
}
} catch (FileNotFoundException e) {
// A file must have been deleted manually!
for (int i = 0; i < valueCount; i++) {
if (ins[i] != null) {
Util.closeQuietly(ins[i]);
} else {
break;
}
}
return null;
}

redundantOpCount++;
journalWriter.append(READ + ' ' + key + '\n');
if (journalRebuildRequired()) {
executorService.submit(cleanupCallable);
}

return new Snapshot(key, entry.sequenceNumber, ins, entry.lengths);
}
讀緩存記錄這個就簡單了迄损，得到Snapshot摔刁，然后通過Snapshot去得到InputStream或者直接得到具體的緩存內(nèi)容。都會從緩存文件中去讀取信息海蔽。
總結來說：

DiskLruCache的實現(xiàn)兩個部分：日志文件和具體的緩存文件共屈。每次對緩存存儲的時候除了對緩存文件做相應的操作，還會在日志文件做相應的記錄党窜。每條日志文件有四種情況：CLEAN（調(diào)用了edit（）之后拗引，保存了緩存，并且調(diào)用了Edit.commit（）了）幌衣、DIRTY（緩存正在編輯矾削，調(diào)用edit（）函數(shù)）、REMOVE（緩存寫入失敾砘ぁ）哼凯、READ（讀緩存）。要想根據(jù)key從緩存文件中讀取到具體的緩存信息楚里，先得到Snapshot断部，然后根據(jù)Snapshot的一些方法做一些了的操作得到具體緩存信息。要保存一個緩存信息的時候寫得到Editor班缎，然后根據(jù)Editor對緩存文件做一些列的操作最后如果是保存了緩存信息記得commit下確認提交蝴光。
————————————————
原文鏈接：https://blog.csdn.net/pgg_cold/article/details/79457987