這是LRU算法的核心妙同，比如Glide里無(wú)論是內(nèi)存緩存還是硬盤(pán)緩存坝咐，其實(shí)核心都是用到了LRU算法唧垦，而LRU算法核心是靠這個(gè)LinedHashMap來(lái)實(shí)現(xiàn)的。
先來(lái)看一下定義的一些方法煤禽，因?yàn)槭抢^承的HashMap铐达，所以?xún)?nèi)部大部分方法是和HashMap一樣，不同的是HashMap中的Node方法是只有next的單向鏈表檬果，而在LinedHashMap中因?yàn)樾枰３植迦牖蛘咦x取順序瓮孙，所以變成了雙向的鏈表LinkedHashMapEntry中是包含before和after。
盜用一下大佬的圖
image.png
public class LinkedHashMap<K,V> extends HashMap<K,V>
implements Map<K,V>
{
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
LinkedHashMapEntry<K,V> before, after;
LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMapEntry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMapEntry<K,V> tail;
·····
put方法是直接繼承的hashmap的选脊，沒(méi)有重新（通過(guò)newNode實(shí)現(xiàn)的雙鏈表操作）杭抠，我們主要看一下get這個(gè)方法，是如何實(shí)現(xiàn)get之后改變位置的恳啥。首先根據(jù)key偏灿，把當(dāng)前節(jié)點(diǎn)搞出來(lái) getNode(hash(key)，然后判斷一下是不是accessOrder=true钝的，如果true翁垂，則會(huì)把訪問(wèn)過(guò)的元素放在鏈表后面铆遭，放置順序是訪問(wèn)的順序 ，如果false沿猜，按出入順序遍歷
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方法枚荣，這是節(jié)點(diǎn)變化的核心方法，盡量注釋的詳細(xì)到每一行啼肩。
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 //拿到當(dāng)前的節(jié)點(diǎn)
, b = p.before // 拿到當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
, a = p.after; //拿到當(dāng)前節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
p.after = null; //因?yàn)楫?dāng)前節(jié)點(diǎn)要當(dāng)做最后一個(gè)節(jié)點(diǎn)橄妆，所以當(dāng)前節(jié)點(diǎn)后邊不需任何節(jié)點(diǎn)了，置空
if (b == null) //如果當(dāng)前節(jié)點(diǎn)前邊一個(gè)節(jié)點(diǎn)是空的祈坠，在代表當(dāng)前節(jié)點(diǎn)是頭節(jié)點(diǎn)
head = a; //這就好說(shuō)了呼畸，頭結(jié)點(diǎn)變成后邊一個(gè)節(jié)點(diǎn)了
else
b.after = a;//如果不是，那就把前邊節(jié)點(diǎn)的后連接和后邊節(jié)點(diǎn)連起來(lái)
if (a != null) //如果后一個(gè)節(jié)點(diǎn)不是空的
a.before = b;//那把后邊一個(gè)節(jié)點(diǎn)的前連接和上一個(gè)節(jié)點(diǎn)連起來(lái)
else
last = b; //如果后邊節(jié)點(diǎn)是空的颁虐，那當(dāng)前就是最后一個(gè)節(jié)點(diǎn)
if (last == null) // 如果當(dāng)前l(fā)ast是空的，沒(méi)有數(shù)據(jù)卧须？
head = p;//那直接把頭節(jié)點(diǎn)變成前節(jié)點(diǎn)
else {
p.before = last; //如果前邊都沒(méi)有 是正常的鏈表 另绩，把當(dāng)前的頭節(jié)點(diǎn)和最后個(gè)連接起來(lái)
last.after = p;//把最后一個(gè)的后節(jié)點(diǎn)和當(dāng)前的節(jié)點(diǎn)連接起來(lái)
}
tail = p; //當(dāng)前節(jié)點(diǎn)賦值給全局變量的最后節(jié)點(diǎn)
++modCount; //整體節(jié)點(diǎn)累加
}
}
image.png
感謝 coolblog大佬 。
