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