注：源碼系列文章主要是對(duì)某付費(fèi)專欄的總結(jié)記錄瑞佩。如有侵權(quán)，請(qǐng)聯(lián)系刪除垦缅。
1 LinkedHashMap 整體架構(gòu)
HashMap 是無序的自赔，TreeMap 可以按照 key 進(jìn)行排序，那有木有 Map 是可以維護(hù)插入的順序的呢背犯？接下來我們看看 LinkedHashMap坏瘩。
LinkedHashMap 本身是繼承 HashMap 的，所以它擁有 HashMap 的所有特性漠魏，在此基礎(chǔ)上倔矾，還提供了兩大特性：
- 按照插入順序進(jìn)行訪問；
- 實(shí)現(xiàn)了訪問最小最先刪除功能，其目的是把很久都沒有訪問的 key 自動(dòng)刪除哪自。
1.1 按照插入順序訪問
1.1.1 LinkedHashMap 鏈表結(jié)構(gòu)
// 鏈表頭
transient LinkedHashMap.Entry<K,V> head;
// 鏈表尾
transient LinkedHashMap.Entry<K,V> tail;
// 繼承 Node丰包，為數(shù)組的每個(gè)元素增加了 before 和 after 屬性
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
// 控制兩種訪問模式的字段，默認(rèn) false
// true: 按照訪問順序提陶，會(huì)把經(jīng)常訪問的 key 放到隊(duì)尾
// false: 按照插入順序提供訪問
final boolean accessOrder;
從新增的屬性可以看到，LinkedHashMap 的數(shù)據(jù)結(jié)構(gòu)很像是把 LinkedList 每個(gè)元素?fù)Q成了 HashMap 的 Node匹层，像是兩者的結(jié)合體隙笆，也正是因?yàn)樵黾恿诉@些結(jié)構(gòu)，從而能把 Map 的元素都串聯(lián)起來升筏，形成一個(gè)鏈表撑柔，而鏈表就可以保證順序了，就可以維護(hù)元素插入進(jìn)來的順序您访。
1.1.2 按照順序新增
LinkedHashMap 初始化時(shí)铅忿，默認(rèn)的 accessOrder 是 false，就是會(huì)按照插入順序提供訪問灵汪，插入方法使用的是父類 HashMap 的 put 方法檀训，不過覆寫了 put 方法執(zhí)行中調(diào)用的 newNode/newTreeNode 和 afterNodeAccess 方法。
newNode/newTreeNode 方法享言，控制新增節(jié)點(diǎn)追加到鏈表的尾部峻凫，這樣每次新節(jié)點(diǎn)都追加到尾部，即可保證插入順序了览露，我們以 newNode 源碼為例：
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
// 初始化一個(gè)新增的節(jié)點(diǎn)
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
// 追加到鏈表的尾部
linkNodeLast(p);
return p;
}
// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
// 緩存舊的尾節(jié)點(diǎn)
LinkedHashMap.Entry<K,V> last = tail;
// 賦值尾節(jié)點(diǎn)為新增節(jié)點(diǎn)
tail = p;
// 如果舊的尾節(jié)點(diǎn)為null則表示當(dāng)前鏈表為空荧琼，直接將新增節(jié)點(diǎn)賦值于頭節(jié)點(diǎn)
if (last == null)
head = p;
// 鏈表有數(shù)據(jù)，將舊的尾節(jié)點(diǎn)和新的尾節(jié)點(diǎn)互聯(lián)
else {
p.before = last;
last.after = p;
}
}
LinkedHashMap 通過新增頭節(jié)點(diǎn)差牛、尾節(jié)點(diǎn)命锄，給每個(gè)節(jié)點(diǎn)增加 before、after 屬性偏化，每次新增時(shí)脐恩，都把節(jié)點(diǎn)追加到尾節(jié)點(diǎn)等手段，在新增的時(shí)候侦讨，就已經(jīng)維護(hù)了按照插入順序的鏈表結(jié)構(gòu)了被盈。
1.1.3 按照順序訪問
LinkedHashMap 只提供了單向訪問，即按照插入的順序從頭到尾進(jìn)行訪問搭伤，不能像 LinkedList 那樣可以雙向訪問只怎。
我們主要通過迭代器進(jìn)行訪問，迭代器初始化的時(shí)候怜俐，默認(rèn)從頭節(jié)點(diǎn)開始訪問身堡，在迭代的過程中，不斷訪問當(dāng)前節(jié)點(diǎn)的 after 節(jié)點(diǎn)即可拍鲤。
Map 對(duì) key贴谎、value 和 entity（節(jié)點(diǎn)）都提供了迭代的方法汞扎，假設(shè)women攜帶 entity，就可以使用 LinkedHashMap.entrySet().iterator() 這種寫法直接返回 LinkedHashIterator擅这，LinkedHashIterator 是迭代器澈魄，我們通過調(diào)用迭代器的 nextNode() 方法就可以得到下一個(gè)節(jié)點(diǎn)，迭代器的源碼如下：
abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
// 初始化時(shí)仲翎，默認(rèn)從頭節(jié)點(diǎn)開始訪問
LinkedHashIterator() {
next = head;
expectedModCount = modCount;
current = null;
}
public final boolean hasNext() {
return next != null;
}
final LinkedHashMap.Entry<K,V> nextNode() {
// 當(dāng)前遍歷的節(jié)點(diǎn)
LinkedHashMap.Entry<K,V> e = next;
// 判斷 modCount
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
// 通過鏈表的 after 結(jié)構(gòu)痹扇，找到下一個(gè)迭代的節(jié)點(diǎn)
next = e.after;
return e;
}
}
在新增節(jié)點(diǎn)時(shí)，我們就已經(jīng)維護(hù)了元素之間的插入順序了溯香，所以迭代訪問是非常簡(jiǎn)答的鲫构，只需要不斷的訪問當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)即可。
1.2 訪問最少刪除策略
1.2.1 演示
這種策略也叫做 <a >LRU</a>（least recently used玫坛，最近最少使用）结笨，大概的意思就是經(jīng)常訪問的元素會(huì)被追加到隊(duì)尾，這樣不經(jīng)常訪問的數(shù)據(jù)自然就靠近隊(duì)頭湿镀，然后我們可以設(shè)置刪除策略炕吸，比如當(dāng) Map 元素個(gè)數(shù)大于多少時(shí)，把頭節(jié)點(diǎn)刪除勉痴，如下：
@Test
public void accessOrderTest() {
// 使用帶參構(gòu)造函數(shù)算途，分別指定初始化大小，加載因子蚀腿，訪問模式(accessOrder)
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>(5, 0.75f, true) {
{
put(1, 1);
put(2, 2);
put(3, 3);
put(4, 4);
put(5, 5);
}
// 覆寫了刪除策略方法嘴瓤，我們?cè)O(shè)定當(dāng)節(jié)點(diǎn)個(gè)數(shù)大于 4 時(shí)，就開始刪除頭節(jié)點(diǎn)
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > 4;
}
};
System.out.println("初始化: " + JSON.toJSONString(map));
map.get(3);
System.out.println("map.get(3): " + JSON.toJSONString(map));
map.get(2);
System.out.println("map.get(2): " + JSON.toJSONString(map));
}
執(zhí)行結(jié)果：
初始化: {2:2,3:3,4:4,5:5}
map.get(3): {2:2,4:4,5:5,3:3}
map.get(2): {4:4,5:5,3:3,2:2}
可以看到莉钙，map 初始化的時(shí)候廓脆，我們放進(jìn)去五個(gè)元素，但結(jié)果只有四個(gè)元素磁玉， 1 不見了停忿，這個(gè)主要是因?yàn)槲覀兏矊懥?removeEldestEntry 方法，我們實(shí)現(xiàn)了如果 map 中元素個(gè)數(shù)大于 4 時(shí)蚊伞，則就把隊(duì)頭的元素刪除席赂，當(dāng) put(5,5) 執(zhí)行的時(shí)候，正好把隊(duì)頭的 1 刪除时迫，這個(gè)體現(xiàn)了當(dāng)達(dá)到我們?cè)O(shè)定的刪除策略時(shí)颅停，會(huì)自動(dòng)刪除頭節(jié)點(diǎn)。
當(dāng)我們調(diào)用 map.get(3) 方法時(shí)掠拳，元素 3 移動(dòng)到了隊(duì)尾癞揉，調(diào)用 map.get(2) 方法時(shí)，元素 2 被移動(dòng)到了隊(duì)尾，這個(gè)體現(xiàn)了經(jīng)常被訪問的節(jié)點(diǎn)會(huì)被移動(dòng)到隊(duì)尾喊熟。
這個(gè)例子就很好的說明了訪問最少刪除策略柏肪，接下來看看原理。
1.2.2 元素被轉(zhuǎn)移到隊(duì)尾
為什么 get 時(shí)芥牌，元素會(huì)被移動(dòng)到隊(duì)尾：
public V get(Object key) {
Node<K,V> e;
// 調(diào)用 HashMap get 方法
if ((e = getNode(hash(key), key)) == null)
return null;
// 如果設(shè)置了 LRU 策略
if (accessOrder)
// 這個(gè)方法把當(dāng)前 key 移動(dòng)到隊(duì)尾
afterNodeAccess(e);
return e.value;
}
從上述源碼中烦味，可以看到，通過 afterNodeAccess 方法把當(dāng)前訪問節(jié)點(diǎn)移動(dòng)到了隊(duì)尾壁拉，其實(shí)不僅僅是 get 方法谬俄，執(zhí)行 getOrDefault、compute扇商、computeIfAbsent凤瘦、computeIfPresent宿礁、merge 方法時(shí)案铺，也會(huì)這么做，通過不斷的把經(jīng)常訪問的節(jié)點(diǎn)移動(dòng)到隊(duì)尾梆靖，那么靠近隊(duì)頭的節(jié)點(diǎn)控汉，自然就是很少被訪問的元素了。
1.2.3 刪除策略
上述例子中我們?cè)趫?zhí)行 put 方法時(shí)返吻，發(fā)現(xiàn)隊(duì)頭元素被刪除了姑子，LinkedHashMap 本身是沒有 put 方法實(shí)現(xiàn)的，調(diào)用的是 HashMap 的 put 方法测僵，但 LinkedHashMap 實(shí)現(xiàn)了 put 方法中的調(diào)用 afterNodeInsertion 方法街佑，這個(gè)方法實(shí)現(xiàn)了刪除，源碼如下：
// 刪除很少被訪問的元素捍靠，被 HashMap 的 put 方法所調(diào)用
void afterNodeInsertion(boolean evict) { // possibly remove eldest
// 得到鏈表的頭節(jié)點(diǎn)
LinkedHashMap.Entry<K,V> first;
// 如果隊(duì)列不為空沐旨，并且刪除策略允許的情況下. removeEldestEntry 為我們覆寫的刪除策略
if (evict && (first = head) != null && removeEldestEntry(first)) {
// 得到頭節(jié)點(diǎn)的 key
K key = first.key;
// 刪除頭節(jié)點(diǎn)
removeNode(hash(key), key, null, false, true);
}
}
1.3 小結(jié)
LinkedHashMap 提供了兩個(gè)很有意思的功能：按照插入順序訪問和刪除最少訪問元素策略，簡(jiǎn)單的通過鏈表的結(jié)構(gòu)就實(shí)現(xiàn)了榨婆，設(shè)計(jì)的非常巧妙磁携。
LinkedHashMap 在 HashMap 的基礎(chǔ)上簡(jiǎn)單的增加了鏈表結(jié)構(gòu)，就形成了節(jié)點(diǎn)的順序良风，非常巧妙谊迄。
------------------------------------- END -------------------------------------
