一、Lru算法
Lru算法：最近最少使用算法账蓉；
算法的核心關鍵類是LinkedHashMap皮璧。
基本算法：將key-value鍵值對按照訪問順序進行排列放置疑俭，當存入的數(shù)據(jù)超過最大內存分配時，移除最久訪問的數(shù)據(jù)在孝；
所以要搞清楚LruCache的原理诚啃，首先需要研究LinkedHashMap這個類；
LinkedHashMap繼承自HashMap私沮，自然也就繼承了HashMap中的眾多方法，所以在研究LinkedHashMap之前和橙，有必要去研究下LinkedHashMap的父類HashMap;
二仔燕、Map接口
Map接口，key-value集合的抽象魔招，反映了單個的key映射著單個的value這樣一種數(shù)據(jù)結構晰搀；
它的核心行為是
存入key-value，對應著put(key,value)方法和根據(jù)key來取出value办斑，對應著get(key);
然后為了功能上的完善外恕，還提供了其他的接口：
//清除map中的所有數(shù)據(jù)
clear();
//是否包含某個key
containsKey(key);
//是否包含某個value
containsValue(value);
//map是否為空
isEmpty()
//根據(jù)某個key來移除key-values
remove(key)
三、HashMap——Map的實現(xiàn)乡翅；
3.1. HashMapEntry
它是HashMap中的一個內部類鳞疲，它是HashMap存儲的數(shù)據(jù)單元，HashMap中的存儲數(shù)組的存儲單位就是HashMapEntry
final K key;
V value;
final int hash;
HashMapEntry<K, V> next;
主要有四個值蠕蚜，key尚洽，values，hash和next靶累，這個next是為了解決hash沖突而設置的腺毫，當存在hash沖突時，next會鏈式地指向下一個HashMapEntry對象挣柬；這個具有相同table index的entry可以鏈式存儲到table中的同一個位置潮酒；
廢話不多說了，直接進入到HashMap的核心方法get(key)和put(key,value)方法邪蛔；
3.2. put(key,value)方法
public V put(K key, V value) {
if (key == null) {
return putValueForNullKey(value);
}
//根據(jù)key來計算hash值急黎，至于為什么是Collections.secondaryHash(key)？
//這樣做只是為了使得hash分布更均勻店溢，避免hash沖突叁熔；
//具體來參考大神的解釋：http://burtleburtle.net/bob/hash/integer.html
int hash = Collections.secondaryHash(key);
//這里就是要存儲數(shù)據(jù)的數(shù)組，基本元素是HashMapEntry
HashMapEntry<K, V>[] tab = table;
//根據(jù)hash值和table的長度來計算索引index值床牧，注意一點荣回，計算的index值不能超過數(shù)組的索引范圍
int index = hash & (tab.length - 1);
//這一步，需要自己品味和分析戈咳，首先拋出一個問題：如果兩個不同的key心软，計算得到的index恰巧相同壕吹，這種情況下怎么辦呢？
//上面的問題删铃，其實就是發(fā)生了hash沖突如何解決的問題耳贬，HashMap采用的方法是，當index值相同時猎唁，采用鏈式的存儲方式來存儲不同的key-value值
//這么說不明白咒劲？不要著急，看下面代碼诫隅，且聽我來細細道來（解釋廢話比較多腐魂，放在代碼后邊，文字里敘述逐纬，免得注釋過多）：
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
// No entry for (non-null) key is present; create one
modCount++;
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index);
return null;
}
首先處理key為null的情況蛔屹，根據(jù)成員屬性entryForNullKey是否為null，如果為null豁生，則調用addNewEntryForNullKey(value)方法來對其進行賦值：
void addNewEntryForNullKey(V value) {
entryForNullKey = new HashMapEntry<K, V>(null, value, 0, null);
}
這種情況不做過多的論述兔毒；
接下來，是重點哈哈哈哈~~~好像重點有點畫多了哈哈哈甸箱，不過下面是重點中的重點：
HashMap是通過基礎的數(shù)據(jù)類型數(shù)組HashMapEntry[] table來存入key-value鍵值對的育叁；
what？摇肌？沒有搞錯把擂红？搞了半天，HashMap是用數(shù)組來實現(xiàn)數(shù)據(jù)存儲的围小？昵骤？數(shù)組的使用我想大家都沒有問題把》》》
當我們往HashMap中存入鍵值對的時候，會根據(jù)key來計算出一個int類型的hash值肯适，然后再將這個hash值轉換成table長度范圍內的索引index变秦，再將value賦值給table[index],經過這樣一個過程，就實現(xiàn)了key-value到數(shù)組存儲的轉化框舔；
兩個不同的key蹦玫，計算得到index值一樣時，也就是存在hash沖突時刘绣，HashMap是如何處理的樱溉？
第一次得到index值時，此時的table[index]為null纬凤，所以直接存入addNewEntry(key, value, hash, index)福贞；
第二次得到index值時，此時的table[index]不為null停士，進入for循環(huán)挖帘，判斷是不是相同的key完丽，如果是，則存入newValue拇舀，返回oldValue逻族；
如果不是相同的key，for循環(huán)中if條件為false骄崩，走addNewEntry(key, value, hash, index)聘鳞；
//我們仔細回顧下，在執(zhí)行這個方法之前要拂，table[index]已經存入了第一次得到index時的hashMapEntryOne搁痛，
//那么new HashMapEntry<K, V>(key, value, hash, table[index]),生成新的對象hashMapEntryTwo，它的內部成員屬性next指向了hashMapEntryOne宇弛；
//結果就是table[index]存入了hashMapEntryTwo的引用，然后hashMapEntryTwo的next又指向了hashMapEntryOne源请；
//這樣存在hash沖突的兩個key-values鍵值對枪芒，就以鏈式數(shù)據(jù)結構，存儲到了table[index]下谁尸；
void addNewEntry(K key, V value, int hash, int index) {
table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
}
HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
this.key = key;
this.value = value;
this.hash = hash;
this.next = next;
}
3.3. get(key)方法
public V get(Object key) {
//首先處理key為null的情況舅踪，根據(jù)成員屬性entryForNullKey的值來返回null或者entryForNullKey的value；
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
return e == null ? null : e.value;
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
return e.value;
}
}
return null;
}
當根據(jù)key來獲取對應的value時良蛮，其實是上述過程的逆過程：
首先根據(jù)key的值來按照特定的算法計算出對應的hash值抽碌，然后將hash值轉換成數(shù)組table的索引index，然后取出table[index]中存儲的值hashMapEntry决瞳，依次去遍歷hashMapEntry中的值（鏈式存儲货徙，當存在hash沖突時，可能會有多個值，依次從next中取出值），在if條件判斷中比較hashMapEntry的key是否與參數(shù)key相同廷没，相同 的話幸乒，說明當前的hashMapEntry的value是我們要取的值；
否則的話硅急，返回null；
整個HashMap的核心就是將key映射到內部存儲結構table的index的方法+HashMapEntry鏈式數(shù)據(jù)結構來解決hash沖突：
四、幾個關鍵問題
4.1. 如何避免和解決hash沖突的
HashMap解決hash沖突的方法：
hash復用泻仙，同一個hash值，鏈式地加入多個value量没；
即如果不同的key玉转，計算出的table index相同的話，那么會將這些值存入table[index]中允蜈，而table[index]的值HashMapEntry為鏈式存儲結構冤吨，可以鏈式的的放入多個值蒿柳；
4.2.如何解決HashMap容量不足的問題
前面解決了hash沖突的問題，那么現(xiàn)在如何解決容量不足的問題了漩蟆。
考慮這樣的情況垒探，如果用戶大量地調用put方法，在這種情況下怠李，如果容量不變圾叼，那么勢必會出現(xiàn)大量的沖突，調用get方法時捺癞，可能需要很長長度的遍歷才能得到答案夷蚊，性能損失嚴重，因此髓介，我們可以發(fā)現(xiàn)put(key,value)源碼中有這樣一種方法doubleCapacity(),這個方法在HashMap存儲容量到達閾值時調用惕鼓，使得HashMap的存儲容量增加一倍；
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
這個方法的具體原理唐础，有興趣的可以去看下源碼箱歧，這里我只想說一下，擴容之后一膨，舊數(shù)組和新數(shù)組的index之前的關系：
int highBit = e.hash & oldCapacity;
HashMapEntry<K, V> broken = null;
newTable[j | highBit] = e;
oldCapacity假設為16(00010000), int highBit = e.hash & oldCapacity 能夠得到高位的值呀邢，因為低位全為0，經過與操作過后豹绪，低位一定是0价淌。J 在這里是index，J 與 高位的值進行‘|’操作過后瞒津，就能得到在擴容后面的新的index值蝉衣。
設想一下，理論上我們得到的新的值應該是 newValue = hash & (newCapacity - 1) 仲智，與 oldValue = hash & (oldCapacity - 1) 的區(qū)別僅在于高位上买乃。 因此我們用 J | highBit 就可以得到新的index值。
4.3.如何解決迭代問題的
4.4.HashMap 是如何實現(xiàn)序列化接口的
這兩個問題钓辆，可以參考下面這篇文章：
http://www.woaitqs.cc/program/2015/04/14/read-source-code-about-hashmap
五剪验、LinkedHashMap——有序的Map接口實現(xiàn)；
5.1
有序指的是元素可以按照插入順序或者訪問順序排列前联；
既然有兩種順序選擇功戚，就需要一個標志位來確定應用中選擇哪種排序方式；
LinkedHashMap成員屬性boolean accessOrder就是這樣一個標志位：
如果為true的話似嗤，LinkedHashMap應用訪問順序排序啸臀；
如果為false的話，LinkedHashMap應用插入順序排序；
5.2.
LinkedHashMap內部包含一個雙向循環(huán)鏈表乘粒，元素排序就是根據(jù)這個雙向循環(huán)鏈表來進行的豌注；
其數(shù)據(jù)結構示意圖如下：
雙向循環(huán)鏈表示意圖：
雙向循環(huán)鏈表頭部存儲的是最久訪問或者最先插入的節(jié)點；
尾部存放的是最近訪問或者最近插入的節(jié)點灯萍；
迭代器的遍歷方向是從鏈表的頭部開始到鏈表的尾部結束轧铁；
鏈表的頭部（也可以叫尾部，叫法不一樣旦棉，但不影響它的本質）有一個空的節(jié)點header齿风；
該節(jié)點不存放key-value鍵值，是LinkedHashMap類的成員屬性绑洛，是雙向循環(huán)鏈表的入口救斑；
5.3.LinkedHashMap中的雙向鏈表的操作
示意圖
說了這么多，都是描述性的語言真屯，看了似乎很明白很直白脸候，但是還是要提醒一點哦，真理還是在源碼中绑蔫，哈哈哈~
六纪他、LinkedHashMap源碼解析
有了HashMap的源碼分析，LinkedHashMap的源碼應該不難理解晾匠；
在get(key)方法中會根據(jù)訪問的key來，調用makeTail(e)來調整hashMapEntry[] table中的數(shù)據(jù)順序梯刚；
6.1.
LinkedHashMap是一個雙向循環(huán)鏈表凉馆，它的每一個數(shù)據(jù)結點都有兩個指針，分別指向直接前驅和直接后繼亡资，這一個我們可以從它的內部類LinkedEntry中看出澜共，其定義如下：
static class LinkedEntry<K, V> extends HashMapEntry<K, V> {
LinkedEntry<K, V> nxt;
LinkedEntry<K, V> prv;
/** Create the header entry */
LinkedEntry() {
super(null, null, 0, null);
nxt = prv = this;
}
/** Create a normal entry */
LinkedEntry(K key, V value, int hash, HashMapEntry<K, V> next,
LinkedEntry<K, V> nxt, LinkedEntry<K, V> prv) {
super(key, value, hash, next);
this.nxt = nxt;
this.prv = prv;
}
}
加入一個新的節(jié)點時，執(zhí)行方法锥腻，新插入的節(jié)點放置在尾部：
@Override void addNewEntry(K key, V value, int hash, int index) {
LinkedEntry<K, V> header = this.header;
// Remove eldest entry if instructed to do so.
LinkedEntry<K, V> eldest = header.nxt;
if (eldest != header && removeEldestEntry(eldest)) {
remove(eldest.key);
}
// Create new entry, link it on to list, and put it into table
LinkedEntry<K, V> oldTail = header.prv;
LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
key, value, hash, table[index], header, oldTail);
table[index] = oldTail.nxt = header.prv = newTail;
}
當accessOrder為true時嗦董，訪問一個節(jié)點會執(zhí)行方法makeTail()，將這個節(jié)點移動到尾部瘦黑；
6.2. makeTail(e)方法
private void makeTail(LinkedEntry<K, V> e) {
// Unlink e
e.prv.nxt = e.nxt;
e.nxt.prv = e.prv;
// Relink e as tail
LinkedEntry<K, V> header = this.header;
LinkedEntry<K, V> oldTail = header.prv;
e.nxt = header;
e.prv = oldTail;
oldTail.nxt = header.prv = e;
modCount++;
}
理解makeTail()方法京革，直接看下面兩個過程示意圖：
unlink過程
relink過程
references：
http://www.cnblogs.com/chenpi/p/5294077.html
http://www.woaitqs.cc/program/2015/04/14/read-source-code-about-hashmap
