阿里面試官：LinkedHashMap是怎么保證元素有序的？
阿里的上下班時間是1095，這么忙也不能耽誤更新《解讀Java源碼專欄》，在這個系列中，我將手把手帶著大家剖析Java核心組件的源碼，內(nèi)容包含集合、線程、線程池、并發(fā)、隊列等，深入了解其背后的設(shè)計思想和實現(xiàn)細(xì)節(jié)，輕松應(yīng)對工作面試。
這是解讀Java源碼系列的第五篇，將跟大家一起學(xué)習(xí)Java中比較神秘的數(shù)據(jù)結(jié)構(gòu) - LinkedHashMap。
引言
新手程序員在使用HashMap的時候，會有個疑問，為什么存到HashMap中的數(shù)據(jù)不是有序的？
這其實跟HashMap的底層設(shè)計有關(guān)，HashMap并不是像ArrayList那樣，按照元素的插入順序存儲。而是先計算key的哈希值，再用哈希值對數(shù)組長度求余，算出數(shù)組下標(biāo)，存儲到下標(biāo)所在的位置，如果該位置上存在鏈表或者紅黑樹，再把這個元素插入到鏈表或者紅黑樹上面。
這樣設(shè)計，可以實現(xiàn)快速查詢，也就犧牲了存儲順序。因為不同key的哈希值差別很大，所以在數(shù)組中存儲是無序的。
然而，有時候我們在遍歷HashMap的時候，又希望按照元素插入順序迭代，有沒有什么方式能實現(xiàn)這個需求？
有的，就是今天的主角LinkedHashMap，不但保證了HashMap的性能，還實現(xiàn)了按照元素插入順序或者訪問順序進(jìn)行迭代。
在這篇文章中，你將學(xué)到以下內(nèi)容：
- LinkedHashMap與HashMap區(qū)別？
- LinkedHashMap特點有哪些？
- LinkedHashMap底層實現(xiàn)原理？
- 怎么使用``LinkedHashMap實現(xiàn) LRU 緩存？
簡介
LinkedHashMap繼承自HashMap，是HashMap的子類，內(nèi)部額外維護(hù)了一個雙鏈表，來保證元素的插入順序或訪問順序，用空間換時間。 與HashMap相比，LinkedHashMap有三個優(yōu)點：
- 維護(hù)了元素插入順序，支持以元素插入順序進(jìn)行迭代。
- 維護(hù)了元素的訪問順序，支持以元素訪問順序進(jìn)行迭代。最近訪問或者更新的元素，會被移動到鏈表末尾，類似于LRU（Least Recently Used，最近最少使用）。當(dāng)面試的時候，手寫LRU緩存，需要用到或者參考LinkedHashMap。
- 迭代效率更高，迭代LinkedHashMap的時候，不需要遍歷整個數(shù)組，只需遍歷雙鏈表即可，效率更高。
圖片
類屬性
public class LinkedHashMap<K, V> extends HashMap<K, V> implements Map<K, V> {
/**
* 頭節(jié)點
*/
transient Entry<K, V> head;
/**
* 尾節(jié)點
*/
transient Entry<K, V> tail;
/**
* 迭代排序方式，true表示按照訪問順序，false表示按照插入順序
*/
final boolean accessOrder;
/**
* 雙鏈表的節(jié)點類
*/
static class Entry<K, V> extends HashMap.Node<K, V> {
/**
* 雙鏈表的前驅(qū)節(jié)點和后繼節(jié)點
*/
Entry<K, V> before, after;
/**
* 構(gòu)造雙鏈表的節(jié)點
*
* @param hash 哈希值
* @param key 鍵
* @param value 值
* @param next 后繼節(jié)點
*/
Entry(int hash, K key, V value, Node<K, V> next) {
super(hash, key, value, next);
}
}
}可以看出LinkedHashMap繼承自HashMap，在HashMap的單鏈表Node節(jié)點的基礎(chǔ)上，增加了前驅(qū)節(jié)點before、后繼節(jié)點after、頭節(jié)點head、尾節(jié)點tail，擴(kuò)展成了雙鏈表節(jié)點Entry，并記錄了迭代排序方式accessOrder。
初始化
LinkedHashMap常見的初始化方法有四個方法：
- 無參初始化
- 指定容量大小的初始化
- 指定容量大小、負(fù)載系數(shù)的初始化
- 指定容量大小、負(fù)載系數(shù)、迭代順序的初始化
/**
* 無參初始化
*/
Map<Integer, Integer> map1 = new LinkedHashMap<>();
/**
* 指定容量大小的初始化
*/
Map<Integer, Integer> map2 = new LinkedHashMap<>(16);
/**
* 指定容量大小、負(fù)載系數(shù)的初始化
*/
Map<Integer, Integer> map3 = new LinkedHashMap<>(16, 0.75f);
/**
* 指定容量大小、負(fù)載系數(shù)、迭代順序的初始化
*/
Map<Integer, Integer> map4 = new LinkedHashMap<>(16, 0.75f, true);再看一下構(gòu)造方法的底層實現(xiàn)：
/**
* 無參初始化
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
/**
* 指定容量大小的初始化
*/
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
/**
* 指定容量大小、負(fù)載系數(shù)的初始化
*
* @param initialCapacity 初始容量
* @param loadFactor 負(fù)載系數(shù)
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
/**
* 指定容量大小、負(fù)載系數(shù)、迭代順序的初始化
*
* @param initialCapacity 初始容量
* @param loadFactor 負(fù)載系數(shù)
* @param accessOrder 迭代順序，true表示按照訪問順序，false表示按照插入順序
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}LinkedHashMap的構(gòu)造方法底層都是調(diào)用的HashMap的構(gòu)造方法，迭代順序accessOrder默認(rèn)是false，表示按照元素插入順序迭代，可以在初始化LinkedHashMap的時候指定為 true，表示按照訪問順序迭代。
put源碼
LinkedHashMap的put方法完全使用的是HashMap的put方法，并沒有重新實現(xiàn)。不過HashMap中定義了一些空方法，留給子類LinkedHashMap去實現(xiàn)。 有以下三個方法：
public class HashMap<K, V> {
/**
* 在訪問節(jié)點后執(zhí)行的操作
*/
void afterNodeAccess(Node<K, V> p) {
}
/**
* 在插入節(jié)點后執(zhí)行的操作
*/
void afterNodeInsertion(boolean evict) {
}
/**
* 在刪除節(jié)點后執(zhí)行的操作
*/
void afterNodeRemoval(Node<K, V> p) {
}
}在HashMap的put源碼中就調(diào)用前兩個方法：
圖片
看一下afterNodeInsertion()方法的源碼，看一下再插入節(jié)點后要執(zhí)行哪些操作？ 在插入節(jié)點后，只執(zhí)行了一個操作，就是判斷是否刪除最舊的節(jié)點。removeEldestEntry()方法默認(rèn)返回false，表示不需要刪除節(jié)點。我們也可以重寫removeEldestEntry()方法，當(dāng)元素數(shù)量超過閾值時，返回true，表示刪除最舊的節(jié)點。
/**
* 在插入節(jié)點后執(zhí)行的操作（刪除最舊的節(jié)點）
*/
void afterNodeInsertion(boolean evict) {
Entry<K, V> first;
// 判斷是否需要刪除當(dāng)前節(jié)點
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
// 調(diào)用HashMap的刪除節(jié)點的方法
removeNode(hash(key), key, null, false, true);
}
}
/**
* 是否刪除最舊的節(jié)點，默認(rèn)是false，表示不刪除
*/
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return false;
}創(chuàng)建節(jié)點
由于afterNodeInsertion()方法并沒有把新節(jié)點插入到雙鏈表中，所以LinkedHashMap又重寫創(chuàng)建節(jié)點的newNode()方法，在newNode()方法中把新節(jié)點插入到雙鏈表。
public class LinkedHashMap<K, V> extends HashMap<K, V> implements Map<K, V> {
/**
* 創(chuàng)建鏈表節(jié)點
*/
@Override
Node<K, V> newNode(int hash, K key, V value, Node<K, V> e) {
// 1. 創(chuàng)建雙鏈表節(jié)點
LinkedHashMap.Entry<K, V> p = new LinkedHashMap.Entry<K, V>(hash, key, value, e);
// 2. 追加到鏈表末尾
linkNodeLast(p);
return p;
}
/**
* 創(chuàng)建紅黑樹節(jié)點
*/
@Override
TreeNode<K, V> newTreeNode(int hash, K key, V value, Node<K, V> next) {
// 1. 創(chuàng)建紅黑樹節(jié)點
TreeNode<K, V> p = new TreeNode<K, V>(hash, key, value, next);
// 2. 追加到鏈表末尾
linkNodeLast(p);
return p;
}
/**
* 追加到鏈表末尾
*/
private void linkNodeLast(LinkedHashMap.Entry<K, V> p) {
LinkedHashMap.Entry<K, V> last = tail;
tail = p;
if (last == null) {
head = p;
} else {
p.before = last;
last.after = p;
}
}
}get源碼
再看一下 get 方法源碼，LinkedHashMap的 get 方法是直接調(diào)用的HashMap的get方法邏輯，在獲取到value 后，判斷 value 不為空，就執(zhí)行afterNodeAccess()方法邏輯，把該節(jié)點移動到鏈表末尾，afterNodeAccess()方法邏輯在前面已經(jīng)講過。
/**
* get方法入口
*/
public V get(Object key) {
Node<K,V> e;
// 直接調(diào)用HashMap的get方法源碼
if ((e = getNode(hash(key), key)) == null) {
return null;
}
// 如果value不為空，并且設(shè)置了accessOrder為true（表示迭代順序為訪問順序），就執(zhí)行訪問節(jié)點后的操作
if (accessOrder) {
afterNodeAccess(e);
}
return e.value;
}看一下afterNodeAccess()方法的源碼實現(xiàn)，看一下在訪問節(jié)點要做哪些操作？afterNodeAccess()方法的邏輯也很簡單，核心邏輯就是把當(dāng)前節(jié)點移動到鏈表末尾，分為三步：
- 斷開當(dāng)前節(jié)點與后繼節(jié)點的連接
- 斷開當(dāng)前節(jié)點與前驅(qū)節(jié)點的連接
- 把當(dāng)前節(jié)點插入到鏈表末尾
/**
* 在訪問節(jié)點后執(zhí)行的操作（把節(jié)點移動到鏈表末尾）
*/
void afterNodeAccess(Node<K, V> e) {
Entry<K, V> last;
// 當(dāng)accessOrder為true時，表示按照訪問順序，這時候才需要更新鏈表
// 并且判斷當(dāng)前節(jié)點不是尾節(jié)點
if (accessOrder && (last = tail) != e) {
Entry<K, V> p = (Entry<K, V>) e, b = p.before, a = p.after;
// 1. 斷開當(dāng)前節(jié)點與后繼節(jié)點的連接
p.after = null;
if (b == null) {
head = a;
} else {
b.after = a;
}
// 2. 斷開當(dāng)前節(jié)點與前驅(qū)節(jié)點的連接
if (a != null) {
a.before = b;
} else {
last = b;
}
// 3. 把當(dāng)前節(jié)點插入到鏈表末尾
if (last == null) {
head = p;
} else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}remove源碼
LinkedHashMap的 remove 方法完全使用的是 HashMap 的 remove 方法，并沒有重新實現(xiàn)。不過 HashMap的 remove 中調(diào)用了afterNodeRemoval?()，執(zhí)行刪除節(jié)點后邏輯，LinkedHashMap重寫了該方法的邏輯。
圖片
/**
* 在刪除節(jié)點后執(zhí)行的操作（從雙鏈表中刪除該節(jié)點）
*/
void afterNodeRemoval(Node<K, V> e) {
LinkedHashMap.Entry<K, V> p =
(LinkedHashMap.Entry<K, V>) e, b = p.before, a = p.after;
p.before = p.after = null;
// 1. 斷開當(dāng)前節(jié)點與前驅(qū)節(jié)點的連接
if (b == null) {
head = a;
} else {
b.after = a;
}
// 2. 斷開當(dāng)前節(jié)點與后繼節(jié)點的連接
if (a == null) {
tail = b;
} else {
a.before = b;
}
}總結(jié)
現(xiàn)在可以回答文章開頭提出的問題：
- LinkedHashMap與HashMap區(qū)別？
答案：LinkedHashMap繼承自HashMap，是HashMap的子類。
- LinkedHashMap特點有哪些？
答案：除了保證了與HashMap一樣高效的查詢和插入性能外，還支持以插入順序或者訪問順序進(jìn)行迭代訪問。
- LinkedHashMap底層實現(xiàn)原理？
答案：LinkedHashMap底層源碼都是使用了HashMap的邏輯實現(xiàn)，使用雙鏈表維護(hù)元素的順序，并重寫了以下三個方法：
- afterNodeAccess()，在訪問節(jié)點后執(zhí)行的操作
- afterNodeInsertion()，在插入節(jié)點后執(zhí)行的操作。
- afterNodeRemoval()，在刪除節(jié)點后執(zhí)行的操作。
- 怎么使用``LinkedHashMap實現(xiàn) LRU 緩存？
答案：由于LinkedHashMap內(nèi)部已經(jīng)實現(xiàn)按照訪問元素的迭代順序，所以只需復(fù)用LinkedHashMap的邏輯，繼承LinkedHashMap，重寫removeEldestEntry()方法。
import java.util.LinkedHashMap;
import java.util.Map;
/**
* @author 一燈架構(gòu)
* @apiNote 使用LinkedHashMap實現(xiàn)LRU緩存
*/
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
/**
* 緩存容量大小
*/
private final int capacity;
/**
* 構(gòu)造方法
*
* @param capacity 緩存容量大小
*/
public LRUCache(int capacity) {
// 底層使用LinkedHashMap的構(gòu)造方法
super(capacity, 0.75f, true);
this.capacity = capacity;
}
/**
* 當(dāng)緩存容量達(dá)到上限時，移除最久未使用的節(jié)點
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
public static void main(String[] args) {
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "One");
cache.put(2, "Two");
cache.put(3, "Three");
System.out.println(cache); // 輸出: {1=One, 2=Two, 3=Three}
cache.get(2);
System.out.println(cache); // 輸出: {1=One, 3=Three, 2=Two}
cache.put(4, "Four");
System.out.println(cache); // 輸出: {3=Three, 2=Two, 4=Four}
}
}
