LinkedHashMap簡(jiǎn)介
LinkedHashMap是HashMap的子類，與HashMap有著同樣的存儲(chǔ)結(jié)構(gòu)，但它加入了一個(gè)雙向鏈表的頭結(jié)點(diǎn)，將所有put到LinkedHashmap的節(jié)點(diǎn)一一串成了一個(gè)雙向循環(huán)鏈表，因此它保留了節(jié)點(diǎn)插入的順序，可以使節(jié)點(diǎn)的輸出順序與輸入順序相同改备。
LinkedHashMap可以用來(lái)實(shí)現(xiàn)LRU算法（這會(huì)在下面的源碼中進(jìn)行分析）。
LinkedHashMap同樣是非線程安全的蔓倍，只在單線程環(huán)境下使用悬钳。
LinkedHashMap源碼剖析
LinkedHashMap源碼如下（加入了詳細(xì)的注釋）：
package java.util;
import java.io.*;
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
private static final long serialVersionUID = 3801124242820219131L;
//雙向循環(huán)鏈表的頭結(jié)點(diǎn)，整個(gè)LinkedHashMap中只有一個(gè)header偶翅，
//它將哈希表中所有的Entry貫穿起來(lái)默勾，header中不保存key-value對(duì)，只保存前后節(jié)點(diǎn)的引用
private transient Entry<K,V> header;
//雙向鏈表中元素排序規(guī)則的標(biāo)志位聚谁。
//accessOrder為false母剥，表示按插入順序排序
//accessOrder為true，表示按訪問(wèn)順序排序
private final boolean accessOrder;
//調(diào)用HashMap的構(gòu)造方法來(lái)構(gòu)造底層的數(shù)組
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false; //鏈表中的元素默認(rèn)按照插入順序排序
}
//加載因子取默認(rèn)的0.75f
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
//加載因子取默認(rèn)的0.75f，容量取默認(rèn)的16
public LinkedHashMap() {
super();
accessOrder = false;
}
//含有子Map的構(gòu)造方法环疼，同樣調(diào)用HashMap的對(duì)應(yīng)的構(gòu)造方法
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super(m);
accessOrder = false;
}
//該構(gòu)造方法可以指定鏈表中的元素排序的規(guī)則
public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
//覆寫父類的init()方法（HashMap中的init方法為空）习霹，
//該方法在父類的構(gòu)造方法和Clone、readObject中在插入元素前被調(diào)用炫隶，
//初始化一個(gè)空的雙向循環(huán)鏈表淋叶，頭結(jié)點(diǎn)中不保存數(shù)據(jù)，頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)才開始保存數(shù)據(jù)伪阶。
void init() {
header = new Entry<K,V>(-1, null, null, null);
header.before = header.after = header;
}
//覆寫HashMap中的transfer方法煞檩，它在父類的resize方法中被調(diào)用，
//擴(kuò)容后望门，將key-value對(duì)重新映射到新的newTable中
//覆寫該方法的目的是為了提高復(fù)制的效率形娇，
//這里充分利用雙向循環(huán)鏈表的特點(diǎn)進(jìn)行迭代，不用對(duì)底層的數(shù)組進(jìn)行for循環(huán)筹误。
void transfer(HashMap.Entry[] newTable) {
int newCapacity = newTable.length;
for (Entry<K,V> e = header.after; e != header; e = e.after) {
int index = indexFor(e.hash, newCapacity);
e.next = newTable[index];
newTable[index] = e;
}
}
//覆寫HashMap中的containsValue方法，
//覆寫該方法的目的同樣是為了提高查詢的效率癣缅，
//利用雙向循環(huán)鏈表的特點(diǎn)進(jìn)行查詢厨剪，少了對(duì)數(shù)組的外層for循環(huán)
public boolean containsValue(Object value) {
// Overridden to take advantage of faster iterator
if (value==null) {
for (Entry e = header.after; e != header; e = e.after)
if (e.value==null)
return true;
} else {
for (Entry e = header.after; e != header; e = e.after)
if (value.equals(e.value))
return true;
}
return false;
}
//覆寫HashMap中的get方法，通過(guò)getEntry方法獲取Entry對(duì)象友存。
//注意這里的recordAccess方法祷膳，
//如果鏈表中元素的排序規(guī)則是按照插入的先后順序排序的話，該方法什么也不做屡立，
//如果鏈表中元素的排序規(guī)則是按照訪問(wèn)的先后順序排序的話直晨，則將e移到鏈表的末尾處。
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
//清空HashMap膨俐，并將雙向鏈表還原為只有頭結(jié)點(diǎn)的空鏈表
public void clear() {
super.clear();
header.before = header.after = header;
}
//Enty的數(shù)據(jù)結(jié)構(gòu)勇皇，多了兩個(gè)指向前后節(jié)點(diǎn)的引用
private static class Entry<K,V> extends HashMap.Entry<K,V> {
// These fields comprise the doubly linked list used for iteration.
Entry<K,V> before, after;
//調(diào)用父類的構(gòu)造方法
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
//雙向循環(huán)鏈表中，刪除當(dāng)前的Entry
private void remove() {
before.after = after;
after.before = before;
}
//雙向循環(huán)立鏈表中焚刺，將當(dāng)前的Entry插入到existingEntry的前面
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
//覆寫HashMap中的recordAccess方法（HashMap中該方法為空）敛摘，
//當(dāng)調(diào)用父類的put方法，在發(fā)現(xiàn)插入的key已經(jīng)存在時(shí)乳愉，會(huì)調(diào)用該方法兄淫，
//調(diào)用LinkedHashmap覆寫的get方法時(shí)，也會(huì)調(diào)用到該方法蔓姚，
//該方法提供了LRU算法的實(shí)現(xiàn)捕虽，它將最近使用的Entry放到雙向循環(huán)鏈表的尾部，
//accessOrder為true時(shí)坡脐，get方法會(huì)調(diào)用recordAccess方法
//put方法在覆蓋key-value對(duì)時(shí)也會(huì)調(diào)用recordAccess方法
//它們導(dǎo)致Entry最近使用泄私，因此將其移到雙向鏈表的末尾
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//如果鏈表中元素按照訪問(wèn)順序排序，則將當(dāng)前訪問(wèn)的Entry移到雙向循環(huán)鏈表的尾部，
//如果是按照插入的先后順序排序挖滤，則不做任何事情崩溪。
if (lm.accessOrder) {
lm.modCount++;
//移除當(dāng)前訪問(wèn)的Entry
remove();
//將當(dāng)前訪問(wèn)的Entry插入到鏈表的尾部
addBefore(lm.header);
}
}
void recordRemoval(HashMap<K,V> m) {
remove();
}
}
//迭代器
private abstract class LinkedHashIterator<T> implements Iterator<T> {
Entry<K,V> nextEntry = header.after;
Entry<K,V> lastReturned = null;
/**
* The modCount value that the iterator believes that the backing
* List should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
int expectedModCount = modCount;
public boolean hasNext() {
return nextEntry != header;
}
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
LinkedHashMap.this.remove(lastReturned.key);
lastReturned = null;
expectedModCount = modCount;
}
//從head的下一個(gè)節(jié)點(diǎn)開始迭代
Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == header)
throw new NoSuchElementException();
Entry<K,V> e = lastReturned = nextEntry;
nextEntry = e.after;
return e;
}
}
//key迭代器
private class KeyIterator extends LinkedHashIterator<K> {
public K next() { return nextEntry().getKey(); }
}
//value迭代器
private class ValueIterator extends LinkedHashIterator<V> {
public V next() { return nextEntry().value; }
}
//Entry迭代器
private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() { return nextEntry(); }
}
// These Overrides alter the behavior of superclass view iterator() methods
Iterator<K> newKeyIterator() { return new KeyIterator(); }
Iterator<V> newValueIterator() { return new ValueIterator(); }
Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
//覆寫HashMap中的addEntry方法，LinkedHashmap并沒有覆寫HashMap中的put方法斩松，
//而是覆寫了put方法所調(diào)用的addEntry方法和recordAccess方法伶唯，
//put方法在插入的key已存在的情況下，會(huì)調(diào)用recordAccess方法惧盹，
//在插入的key不存在的情況下乳幸，要調(diào)用addEntry插入新的Entry
void addEntry(int hash, K key, V value, int bucketIndex) {
//創(chuàng)建新的Entry，并插入到LinkedHashMap中
createEntry(hash, key, value, bucketIndex);
//雙向鏈表的第一個(gè)有效節(jié)點(diǎn)（header后的那個(gè)節(jié)點(diǎn)）為近期最少使用的節(jié)點(diǎn)
Entry<K,V> eldest = header.after;
//如果有必要钧椰，則刪除掉該近期最少使用的節(jié)點(diǎn)粹断，
//這要看對(duì)removeEldestEntry的覆寫,由于默認(rèn)為false，因此默認(rèn)是不做任何處理的嫡霞。
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
//擴(kuò)容到原來(lái)的2倍
if (size >= threshold)
resize(2 * table.length);
}
}
void createEntry(int hash, K key, V value, int bucketIndex) {
//創(chuàng)建新的Entry瓶埋，并將其插入到數(shù)組對(duì)應(yīng)槽的單鏈表的頭結(jié)點(diǎn)處，這點(diǎn)與HashMap中相同
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
table[bucketIndex] = e;
//每次插入Entry時(shí)诊沪，都將其移到雙向鏈表的尾部养筒，
//這便會(huì)按照Entry插入LinkedHashMap的先后順序來(lái)迭代元素，
//同時(shí)端姚，新put進(jìn)來(lái)的Entry是最近訪問(wèn)的Entry晕粪，把其放在鏈表末尾 ，符合LRU算法的實(shí)現(xiàn)
e.addBefore(header);
size++;
}
//該方法是用來(lái)被覆寫的渐裸，一般如果用LinkedHashmap實(shí)現(xiàn)LRU算法巫湘，就要覆寫該方法，
//比如可以將該方法覆寫為如果設(shè)定的內(nèi)存已滿昏鹃，則返回true尚氛，這樣當(dāng)再次向LinkedHashMap中put
//Entry時(shí)，在調(diào)用的addEntry方法中便會(huì)將近期最少使用的節(jié)點(diǎn)刪除掉（header后的那個(gè)節(jié)點(diǎn)）盆顾。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
}
幾點(diǎn)總結(jié)
關(guān)于LinkedHashMap的源碼怠褐，給出以下幾點(diǎn)比較重要的總結(jié)：
1、從源碼中可以看出您宪，LinkedHashMap中加入了一個(gè)head頭結(jié)點(diǎn)奈懒，將所有插入到該LinkedHashMap中的Entry按照插入的先后順序依次加入到以head為頭結(jié)點(diǎn)的雙向循環(huán)鏈表的尾部。
1宪巨、實(shí)際上就是HashMap和LinkedList兩個(gè)集合類的存儲(chǔ)結(jié)構(gòu)的結(jié)合磷杏。在LinkedHashMapMap中，所有put進(jìn)來(lái)的Entry都保存在如第一個(gè)圖所示的哈希表中捏卓，但它又額外定義了一個(gè)以head為頭結(jié)點(diǎn)的空的雙向循環(huán)鏈表极祸，每次put進(jìn)來(lái)Entry慈格，除了將其保存到對(duì)哈希表中對(duì)應(yīng)的位置上外，還要將其插入到雙向循環(huán)鏈表的尾部遥金。
2浴捆、LinkedHashMap由于繼承自HashMap，因此它具有HashMap的所有特性稿械，同樣允許key和value為null选泻。
3、注意源碼中的accessOrder標(biāo)志位美莫，當(dāng)它false時(shí)页眯，表示雙向鏈表中的元素按照Entry插入LinkedHashMap到中的先后順序排序，即每次put到LinkedHashMap中的Entry都放在雙向鏈表的尾部厢呵，這樣遍歷雙向鏈表時(shí)窝撵，Entry的輸出順序便和插入的順序一致，這也是默認(rèn)的雙向鏈表的存儲(chǔ)順序襟铭；當(dāng)它為true時(shí)碌奉，表示雙向鏈表中的元素按照訪問(wèn)的先后順序排列，可以看到寒砖，雖然Entry插入鏈表的順序依然是按照其put到LinkedHashMap中的順序道批，但put和get方法均有調(diào)用recordAccess方法（put方法在key相同，覆蓋原有的Entry的情況下調(diào)用recordAccess方法）入撒，該方法判斷accessOrder是否為true，如果是椭岩，則將當(dāng)前訪問(wèn)的Entry（put進(jìn)來(lái)的Entry或get出來(lái)的Entry）移到雙向鏈表的尾部（key不相同時(shí)茅逮，put新Entry時(shí)，會(huì)調(diào)用addEntry判哥，它會(huì)調(diào)用creatEntry献雅，該方法同樣將新插入的元素放入到雙向鏈表的尾部，既符合插入的先后順序塌计，又符合訪問(wèn)的先后順序挺身，因?yàn)檫@時(shí)該Entry也被訪問(wèn)了），否則锌仅，什么也不做章钾。
4、注意構(gòu)造方法热芹，前四個(gè)構(gòu)造方法都將accessOrder設(shè)為false贱傀，說(shuō)明默認(rèn)是按照插入順序排序的，而第五個(gè)構(gòu)造方法可以自定義傳入的accessOrder的值伊脓，因此可以指定雙向循環(huán)鏈表中元素的排序規(guī)則府寒，一般要用LinkedHashMap實(shí)現(xiàn)LRU算法，就要用該構(gòu)造方法，將accessOrder置為true株搔。
5剖淀、LinkedHashMap并沒有覆寫HashMap中的put方法，而是覆寫了put方法中調(diào)用的addEntry方法和recordAccess方法纤房，我們回過(guò)頭來(lái)再看下HashMap的put方法：
// 將“key-value”添加到HashMap中
public V put(K key, V value) {
// 若“key為null”纵隔，則將該鍵值對(duì)添加到table[0]中。
if (key == null)
return putForNullKey(value);
// 若“key不為null”帆卓，則計(jì)算該key的哈希值巨朦，然后將其添加到該哈希值對(duì)應(yīng)的鏈表中。
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 若“該key”對(duì)應(yīng)的鍵值對(duì)已經(jīng)存在剑令，則用新的value取代舊的value糊啡。然后退出！
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 若“該key”對(duì)應(yīng)的鍵值對(duì)不存在吁津，則將“key-value”添加到table中
modCount++;
//將key-value添加到table[i]處
addEntry(hash, key, value, i);
return null;
}
當(dāng)要put進(jìn)來(lái)的Entry的key在哈希表中已經(jīng)在存在時(shí)棚蓄，會(huì)調(diào)用recordAccess方法，當(dāng)該key不存在時(shí)碍脏，則會(huì)調(diào)用addEntry方法將新的Entry插入到對(duì)應(yīng)槽的單鏈表的頭部梭依。
我們先來(lái)看recordAccess方法：
//覆寫HashMap中的recordAccess方法（HashMap中該方法為空），
//當(dāng)調(diào)用父類的put方法典尾，在發(fā)現(xiàn)插入的key已經(jīng)存在時(shí)役拴，會(huì)調(diào)用該方法，
//調(diào)用LinkedHashmap覆寫的get方法時(shí)钾埂，也會(huì)調(diào)用到該方法河闰，
//該方法提供了LRU算法的實(shí)現(xiàn)，它將最近使用的Entry放到雙向循環(huán)鏈表的尾部褥紫，
//accessOrder為true時(shí)姜性，get方法會(huì)調(diào)用recordAccess方法
//put方法在覆蓋key-value對(duì)時(shí)也會(huì)調(diào)用recordAccess方法
//它們導(dǎo)致Entry最近使用，因此將其移到雙向鏈表的末尾
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//如果鏈表中元素按照訪問(wèn)順序排序髓考，則將當(dāng)前訪問(wèn)的Entry移到雙向循環(huán)鏈表的尾部部念，
//如果是按照插入的先后順序排序，則不做任何事情氨菇。
if (lm.accessOrder) {
lm.modCount++;
//移除當(dāng)前訪問(wèn)的Entry
remove();
//將當(dāng)前訪問(wèn)的Entry插入到鏈表的尾部
addBefore(lm.header);
}
}
該方法會(huì)判斷accessOrder是否為true儡炼，如果為true，它會(huì)將當(dāng)前訪問(wèn)的Entry（在這里指put進(jìn)來(lái)的Entry）移動(dòng)到雙向循環(huán)鏈表的尾部门驾，從而實(shí)現(xiàn)雙向鏈表中的元素按照訪問(wèn)順序來(lái)排序（最近訪問(wèn)的Entry放到鏈表的最后射赛，這樣多次下來(lái)，前面就是最近沒有被訪問(wèn)的元素奶是，在實(shí)現(xiàn)楣责、LRU算法時(shí)竣灌，當(dāng)雙向鏈表中的節(jié)點(diǎn)數(shù)達(dá)到最大值時(shí)，將前面的元素刪去即可秆麸，因?yàn)榍懊娴脑厥亲罱钌偈褂玫模┏踵冢駝t什么也不做。
再來(lái)看addEntry方法：
//覆寫HashMap中的addEntry方法沮趣，LinkedHashmap并沒有覆寫HashMap中的put方法屯烦，
//而是覆寫了put方法所調(diào)用的addEntry方法和recordAccess方法，
//put方法在插入的key已存在的情況下房铭，會(huì)調(diào)用recordAccess方法驻龟，
//在插入的key不存在的情況下，要調(diào)用addEntry插入新的Entry
void addEntry(int hash, K key, V value, int bucketIndex) {
//創(chuàng)建新的Entry缸匪，并插入到LinkedHashMap中
createEntry(hash, key, value, bucketIndex);
//雙向鏈表的第一個(gè)有效節(jié)點(diǎn)（header后的那個(gè)節(jié)點(diǎn)）為近期最少使用的節(jié)點(diǎn)
Entry<K,V> eldest = header.after;
//如果有必要翁狐，則刪除掉該近期最少使用的節(jié)點(diǎn)，
//這要看對(duì)removeEldestEntry的覆寫,由于默認(rèn)為false凌蔬，因此默認(rèn)是不做任何處理的露懒。
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
//擴(kuò)容到原來(lái)的2倍
if (size >= threshold)
resize(2 * table.length);
}
}
void createEntry(int hash, K key, V value, int bucketIndex) {
//創(chuàng)建新的Entry，并將其插入到數(shù)組對(duì)應(yīng)槽的單鏈表的頭結(jié)點(diǎn)處砂心，這點(diǎn)與HashMap中相同
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
table[bucketIndex] = e;
//每次插入Entry時(shí)懈词，都將其移到雙向鏈表的尾部，
//這便會(huì)按照Entry插入LinkedHashMap的先后順序來(lái)迭代元素辩诞，
//同時(shí)坎弯，新put進(jìn)來(lái)的Entry是最近訪問(wèn)的Entry，把其放在鏈表末尾 译暂，符合LRU算法的實(shí)現(xiàn)
e.addBefore(header);
size++;
}
同樣是將新的Entry插入到table中對(duì)應(yīng)槽所對(duì)應(yīng)單鏈表的頭結(jié)點(diǎn)中荞怒，但可以看出，在createEntry中秧秉，同樣把新put進(jìn)來(lái)的Entry插入到了雙向鏈表的尾部，從插入順序的層面來(lái)說(shuō)衰抑，新的Entry插入到雙向鏈表的尾部象迎，可以實(shí)現(xiàn)按照插入的先后順序來(lái)迭代Entry，而從訪問(wèn)順序的層面來(lái)說(shuō)呛踊，新put進(jìn)來(lái)的Entry又是最近訪問(wèn)的Entry砾淌，也應(yīng)該將其放在雙向鏈表的尾部。
上面還有個(gè)removeEldestEntry方法谭网，該方法如下：
//該方法是用來(lái)被覆寫的汪厨，一般如果用LinkedHashmap實(shí)現(xiàn)LRU算法，就要覆寫該方法愉择，
//比如可以將該方法覆寫為如果設(shè)定的內(nèi)存已滿劫乱，則返回true织中，這樣當(dāng)再次向LinkedHashMap中put
//Entry時(shí)，在調(diào)用的addEntry方法中便會(huì)將近期最少使用的節(jié)點(diǎn)刪除掉（header后的那個(gè)節(jié)點(diǎn)）衷戈。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
}
該方法默認(rèn)返回false狭吼，我們一般在用LinkedHashMap實(shí)現(xiàn)LRU算法時(shí)，要覆寫該方法殖妇，一般的實(shí)現(xiàn)是刁笙，當(dāng)設(shè)定的內(nèi)存（這里指節(jié)點(diǎn)個(gè)數(shù)）達(dá)到最大值時(shí)，返回true谦趣，這樣put新的Entry（該Entry的key在哈希表中沒有已經(jīng)存在）時(shí)疲吸，就會(huì)調(diào)用removeEntryForKey方法，將最近最少使用的節(jié)點(diǎn)刪除（head后面的那個(gè)節(jié)點(diǎn)前鹅，實(shí)際上是最近沒有使用）摘悴。
6、LinkedHashMap覆寫了HashMap的get方法：
//覆寫HashMap中的get方法嫡纠，通過(guò)getEntry方法獲取Entry對(duì)象烦租。
//注意這里的recordAccess方法，
//如果鏈表中元素的排序規(guī)則是按照插入的先后順序排序的話除盏，該方法什么也不做叉橱，
//如果鏈表中元素的排序規(guī)則是按照訪問(wèn)的先后順序排序的話，則將e移到鏈表的末尾處者蠕。
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
先取得Entry窃祝，如果不為null，一樣調(diào)用recordAccess方法踱侣，上面已經(jīng)說(shuō)得很清楚粪小，這里不在多解釋了。
7抡句、最后說(shuō)說(shuō)LinkedHashMap是如何實(shí)現(xiàn)LRU的探膊。首先，當(dāng)accessOrder為true時(shí)待榔，才會(huì)開啟按訪問(wèn)順序排序的模式逞壁，才能用來(lái)實(shí)現(xiàn)LRU算法。我們可以看到锐锣，無(wú)論是put方法還是get方法腌闯，都會(huì)導(dǎo)致目標(biāo)Entry成為最近訪問(wèn)的Entry，因此便把該Entry加入到了雙向鏈表的末尾（get方法通過(guò)調(diào)用recordAccess方法來(lái)實(shí)現(xiàn)雕憔，put方法在覆蓋已有key的情況下姿骏，也是通過(guò)調(diào)用recordAccess方法來(lái)實(shí)現(xiàn)，在插入新的Entry時(shí)斤彼，則是通過(guò)createEntry中的addBefore方法來(lái)實(shí)現(xiàn)）分瘦，這樣便把最近使用了的Entry放入到了雙向鏈表的后面蘸泻，多次操作后，雙向鏈表前面的Entry便是最近沒有使用的擅腰，這樣當(dāng)節(jié)點(diǎn)個(gè)數(shù)滿的時(shí)候蟋恬，刪除的最前面的Entry(head后面的那個(gè)Entry)便是最近最少使用的Entry。
