一、前言
LinkedHashMap 繼承于 HashMap疚宇，因此亡鼠，建議在學(xué)習(xí)本篇內(nèi)容前，先學(xué)習(xí) HashMap系列敷待，這樣使得更加容易理解间涵。
HashMap系列
（一）HashMap系列：負(fù)載因子0.75
（二）HashMap系列：樹化閥值8，退化閥值6
（三）HashMap系列：2次方擴(kuò)容
（四）HashMap系列：put元素（不看完將后悔一生０褚尽）
二勾哩、LinkedHashMap使用
可能很多人會(huì)說(shuō)抗蠢，LinkedHashMap誰(shuí)不會(huì)用？你真的確定你會(huì)用思劳？
上例子之前迅矛，先寫幾個(gè)工具方法，以便后面理解方便：
public class Main {
// 字符串左對(duì)齊（未考慮中英文長(zhǎng)度潜叛，僅便于觀看）
private static String spaceFill(Object object) {
return String.format("%-20s", object);
}
// 反射獲取 HashMap 中的數(shù)組對(duì)象
// 啥秽褒？你不知道數(shù)組對(duì)象名稱？
// 建議去看看源碼威兜，或是看看我寫的 HashMap 系列
private static Map.Entry<Integer, String>[] getArray(Object object, Field field) throws Exception {
return (Map.Entry<Integer, String>[]) field.get(object);
}
// 反射獲取 Map.Entry
// 因?yàn)?HashMap.Node 是私有靜態(tài)類
private static Map.Entry<Integer, String> getObject(Object object, String name) throws Exception {
Field field = getField(object.getClass(), name);
return (Map.Entry<Integer, String>) field.get(object);
}
// 反射獲取指定字段
private static Field getField(Class<?> clazz, String name) {
if (clazz == null) {
return null;
}
Field field = null;
try {
field = clazz.getDeclaredField(name);
field.setAccessible(true);
} catch (NoSuchFieldException e) {
field = getField(clazz.getSuperclass(), name);
}
return field;
}
}
好了销斟，上面的工具方法已經(jīng)完成，后面的所有例子都會(huì)使用上面的方法椒舵。
我們來(lái)看兩個(gè)例子：
2.1蚂踊、例子一
public class Main {
public static void main(String[] args) {
// 一般大家都使用默認(rèn)構(gòu)造函數(shù)
LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
map.put(1, "chris");
map.put(2, "qingye");
map.put(3, "24854015@qq.com");
// 反射獲取 table 數(shù)組對(duì)象
Field field = getField(map.getClass(), "table");
if (field != null && field.getType().isArray()) {
try {
// 類型強(qiáng)轉(zhuǎn)
Map.Entry<Integer, String>[] table = getArray(map, field);
for (int i = 0; i < table.length; i ++) {
if (table[i] != null) {
// LinkedHashMap.Node 特有的 before & after 指針
Map.Entry<Integer, String> before = getObject(table[i], "before");
Map.Entry<Integer, String> after = getObject(table[i], "after");
if (before == null) {
System.out.print("This is Head ");
} else if (after == null) {
System.out.print("This is Tail ");
} else {
System.out.print("\t\t\t ");
}
System.out.println("[" + i + "] => " + spaceFill(table[i]) + ", before => " + spaceFill(before) + ", after => " + spaceFill(after));
}
}
} catch (Exception e) {
}
}
}
}
輸出結(jié)果：
This is Head [1] => 1=chris , before => null , after => 2=qingye
[2] => 2=qingye , before => 1=chris , after => 3=24854015@qq.com
This is Tail [3] => 3=24854015@qq.com , before => 2=qingye , after => null
2.2、例子二
public class Main {
public static void main(String[] args) {
// 指定構(gòu)造函數(shù)來(lái)初始化
LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);
map.put(1, "chris");
map.put(2, "qingye");
map.put(3, "24854015@qq.com");
map.get(1); // 注意：這里僅僅 get 了一下
Field field = getField(map.getClass(), "table");
if (field != null && field.getType().isArray()) {
try {
Map.Entry<Integer, String>[] table = getArray(map, field);
for (int i = 0; i < table.length; i ++) {
if (table[i] != null) {
Map.Entry<Integer, String> before = getObject(table[i], "before");
Map.Entry<Integer, String> after = getObject(table[i], "after");
if (before == null) {
System.out.print("This is Head ");
} else if (after == null) {
System.out.print("This is Tail ");
} else {
System.out.print("\t\t\t ");
}
System.out.println("[" + i + "] => " + spaceFill(table[i]) + ", before => " + spaceFill(before) + ", after => " + spaceFill(after));
}
}
} catch (Exception e) {
}
}
}
}
輸出結(jié)果：
This is Tail [1] => 1=chris , before => 3=24854015@qq.com , after => null
This is Head [2] => 2=qingye , before => null , after => 3=24854015@qq.com
[3] => 3=24854015@qq.com , before => 2=qingye , after => 1=chris
WTF 逮栅？悴势！發(fā)生了啥？怎么[1]元素從『Head』變成了『Tail』措伐？
這就是 LinkedHashMap 的其妙之處特纤！
三、深入解讀 LinkedHashMap 的奧秘
3.1侥加、LinkedHashMap 與 HashMap 的關(guān)系
本篇開頭也說(shuō)了捧存，前者繼承于后者，因此担败，LinkedHashMap 的 putXXX 和 getXXX 都直接繼承于 HashMap昔穴，并沒有重載，其 put & get 的邏輯也就和 HashMap 一樣提前。HashMap 的 put & get 是啥邏輯吗货？如果大家忘記了，建議去看看我寫的《HashMap系列：put元素》狈网。既然是繼承宙搬，同樣的，它們的數(shù)組結(jié)構(gòu)也就幾乎一致（99%的一致）：
數(shù)據(jù)結(jié)構(gòu)：數(shù)組 + 鏈表 <---> 紅黑樹
那 1% 的不一致在哪拓哺？
3.2勇垛、Map.Entry
HashMap 的節(jié)點(diǎn)實(shí)現(xiàn)了 Map.Entry：
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
那 LinkedHashMap的節(jié)點(diǎn)呢？
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
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);
}
}
}
額士鸥，真是簡(jiǎn)單的令人發(fā)指跋泄隆！
僅僅多了兩個(gè)索引（指針）節(jié)點(diǎn)：before & after 烤礁！
3.3讼积、HashMap.TreeNode
之前再講 HashMap 時(shí)肥照，并沒有提到 TreeNode 這個(gè)類型，因?yàn)樯婕暗?LinkedHashMap勤众，所以有所調(diào)整建峭，這里進(jìn)行補(bǔ)充：
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
完美的繼承：
3.4、before & after
根據(jù)這兩個(gè)字段的名稱决摧，我們就能很容易的猜測(cè)出，分別指向前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)（事實(shí)上凑兰，我們開頭的兩個(gè)例子掌桩，已經(jīng)證實(shí)了這種關(guān)系），那么姑食，具體是如何在數(shù)據(jù)結(jié)構(gòu)或者說(shuō)波岛，節(jié)點(diǎn)對(duì)象上表現(xiàn)出關(guān)聯(lián)關(guān)系的呢？
畫圖很辛苦......
LinkedHashMap 之所以加了 before 與 after 節(jié)點(diǎn)索引音半，主要目的：
- 雙向鏈表（即可以雙向訪問）则拷，從頭結(jié)點(diǎn)可以一直遍歷到最后一個(gè)節(jié)點(diǎn)，而不需要中途定位到桶曹鸠；
- 可以按照插入順序來(lái)訪問（默認(rèn)）煌茬，【例子一】；
四彻桃、LinkedHashMap 特殊之處
/**
* The iteration ordering method for this linked hash map: true for access-order, false for insertion-order.
*/
final boolean accessOrder;
該字段含義：
- true時(shí)坛善，遍歷雙向鏈表中元素是按照訪問順序來(lái)遍歷（LRU）；
- false時(shí)邻眷，遍歷雙向鏈表中的元素是按照插入順序來(lái)遍歷（默認(rèn)）眠屎；
Android系統(tǒng)中的 LRU 的實(shí)現(xiàn)，其實(shí)就是基于 LinkedHashMap肆饶，并采用了【例子二】的方式來(lái)初始化對(duì)象實(shí)例改衩。
五、LinkedHashMap索引的源碼實(shí)現(xiàn)
我們同樣從 put元素還是分析源碼驯镊，還記得我們分析 HashMap 的 putVal 時(shí)葫督，有兩個(gè)空函數(shù)么？
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
......
else {
......
if (e != null) { // 元素已經(jīng)存在
......
afterNodeAccess(e); // 調(diào)整節(jié)點(diǎn)順序
return oldValue;
}
}
......
afterNodeInsertion(evict); // 新增元素阿宅，調(diào)整節(jié)點(diǎn)順序
return null;
}
}
5.1候衍、LinkedHashMap.afterNodeAccess
該方法會(huì)被多個(gè)其它方法觸發(fā)，例如：put一個(gè)已存在的節(jié)點(diǎn)對(duì)象洒放，get對(duì)象蛉鹿，replace對(duì)象等等，該方法就是判斷是否需要調(diào)整的遍歷訪問順序往湿。
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// accessOrder = true妖异，表示 LRU
// 將要移動(dòng)的節(jié)點(diǎn)已經(jīng)在最后一個(gè)惋戏，那么就不用調(diào)整了
if (accessOrder && (last = tail) != e) {
// p 指向 e本身，b 指向 e前一個(gè)他膳，a 指向 e后一個(gè)
LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
// 如果 e的前一個(gè)為null响逢，表示 e 是頭節(jié)點(diǎn)，那么將頭節(jié)點(diǎn)指向 e的下一個(gè)元素
if (b == null)
head = a;
else
b.after = a; // 否則 e的上一個(gè)元素棕孙，其下一個(gè)指向從 e 改為 e的下一個(gè)
// a 為null 則表示 e 是尾節(jié)點(diǎn)
// 否則將 e的下一個(gè)元素舔亭，其上一個(gè)指向從 e 改為 e的上一個(gè)
if (a != null)
a.before = b;
else
last = b; // 否則，尾節(jié)點(diǎn)指向 e 的上一個(gè)元素
// 總之蟀俊，上面判斷：b钦铺，a 不為null，則互指
// 如果 last 為null肢预，則表示整個(gè) LinkedHashMap 只有一個(gè)元素
if (last == null)
head = p;
else {
// 否則矛洞，將 p 移至最后一個(gè)（訪問順序上，即邏輯上最后一個(gè)烫映，實(shí)際位置不會(huì)變）
p.before = last;
last.after = p;
}
tail = p; // 最后沼本，尾指向最后一個(gè)元素
++modCount;
}
}
}
5.2、LinkedHashMap.afterNodeInsertion
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
// 新增節(jié)點(diǎn)后锭沟，調(diào)用此方法判斷是否需要移除最老的節(jié)點(diǎn)
// 因?yàn)?accessOrder = true 時(shí)抽兆，訪問次數(shù)多的節(jié)點(diǎn)一定是在鏈尾，而訪問次數(shù)最少的則在鏈頭
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
// 如果需要移除最老的冈钦，則先從鏈頭開始移除
// 移除節(jié)點(diǎn)郊丛，調(diào)用的是 HashMap.removeNode 方法
// 同樣是從數(shù)組開始，再紅黑樹瞧筛，再鏈表查找厉熟，刪除，調(diào)整
removeNode(hash(key), key, null, false, true);
}
}
}
5.3较幌、LinkedHashMap.removeEldestEntry
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
// 該方法在 LinkedHashMap 中揍瑟，默認(rèn)返回 false，即不移除最老的元素
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
}
那為啥我還一直提到 LRU 呢乍炉？
因?yàn)榫钇覀內(nèi)绻约夯?LinkedHashMap 來(lái)實(shí)現(xiàn) LRU，就可以重載此方法岛琼，返回 true 底循，這樣就達(dá)到了 LRU 的效果。
好了槐瑞，LinkedHashMap 就聊到這里熙涤！
