先看再點贊，給自己一點思考的時間，微信搜尋【沉默王二】關注這個有顔值卻假裝靠才華苟且的程式員。
本文 GitHub github.com/itwanger 已收錄，裡面還有我精心為你準備的一線大廠面試題。
同學們好啊，還記得 HashMap 那篇嗎？我自己感覺寫得非常棒啊，既通俗易懂，又深入源碼，真的是分析得透透徹徹、清清楚楚、明明白白的。（一不小心又上仨成語？）HashMap 哪哪都好，真的，隻要你想用鍵值對，第一時間就應該想到它。
但俗話說了，“金無足赤人無完人”，HashMap 也不例外。有一種需求它就滿足不了，假如我們需要一個按照插入順序來排列的鍵值對集合，那 HashMap 就無能為力了。因為為了提高查找效率，HashMap 在插入的時候對鍵做了一次雜湊演算法，這就導緻插入的元素是無序的。
對這一點還不太明白的同學，可以再回到 HashMap 那一篇，看看我對
put()
方法的講解。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
// ①、數組 table 為 null 時，調用 resize 方法建立預設大小的數組
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// ②、計算下标，如果該位置上沒有值，則填充
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
}
這個公式
i = (n - 1) & hash
計算後的值并不是按照 0、1、2、3、4、5 這樣有序的下标将鍵值對插入到數組當中的，而是有一定的随機性。
那 LinkedHashMap 就是為這個需求應運而生的。LinkedHashMap 繼承了 HashMap，是以 HashMap 有的關于鍵值對的功能，它也有了。
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>{}
此外，LinkedHashMap 内部又追加了雙向連結清單，來維護元素的插入順序。注意下面代碼中的 before 和 after，它倆就是用來維護目前元素的前一個元素和後一個元素的順序的。
static class Entry<K,V> extends HashMap.Node<K,V> {
LinkedHashMap.Entry<K,V> before, after;
Entry(int hash, K key, V value, HashMap.Node<K,V> next) {
super(hash, key, value, next);
}
}
關于雙向連結清單，同學們可以回頭看一遍我寫的 LinkedList 那篇文章，會對了解本篇的 LinkedHashMap 有很大的幫助。
在繼續下面的内容之前，我先貼一張圖檔，給大家增添一點樂趣——看我這心操的。 UUID 那篇文章的标題裡用了“可笑”和“你”，結果就看到了下面這麼樂呵的留言。
（到底是知道還是不知道，我搞不清楚了。。。）那 LinkedHashMap 這篇也用了“你”和“可笑”，不知道到時候會不會有人繼續對号入座啊，想想就覺得特别歡樂。
01、插入順序
在 HashMap 那篇文章裡，我有講解到一點，不知道同學們記不記得，就是 null 會插入到 HashMap 的第一位。
Map<String, String> hashMap = new HashMap<>();
hashMap.put("沉", "沉默王二");
hashMap.put("默", "沉默王二");
hashMap.put("王", "沉默王二");
hashMap.put("二", "沉默王二");
hashMap.put(null, null);
for (String key : hashMap.keySet()) {
System.out.println(key + " : " + hashMap.get(key));
}
輸出的結果是：
null : null
默 : 沉默王二
沉 : 沉默王二
王 : 沉默王二
二 : 沉默王二
雖然 null 最後一位 put 進去的，但在周遊輸出的時候，跑到了第一位。
那再來對比看一下 LinkedHashMap。
Map<String, String> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("沉", "沉默王二");
linkedHashMap.put("默", "沉默王二");
linkedHashMap.put("王", "沉默王二");
linkedHashMap.put("二", "沉默王二");
linkedHashMap.put(null, null);
for (String key : linkedHashMap.keySet()) {
System.out.println(key + " : " + linkedHashMap.get(key));
}
輸出結果是：
沉 : 沉默王二
默 : 沉默王二
王 : 沉默王二
二 : 沉默王二
null : null
null 在最後一位插入，在最後一位輸出。
輸出結果可以再次證明，HashMap 是無序的，LinkedHashMap 是可以維持插入順序的。
那 LinkedHashMap 是如何做到這一點呢？我相信同學們和我一樣，非常希望知道原因。
要想搞清楚，就需要深入研究一下 LinkedHashMap 的源碼。LinkedHashMap 并未重寫 HashMap 的
put()
方法，而是重寫了
put()
方法需要調用的内部方法
newNode()
。
HashMap.Node<K,V> newNode(int hash, K key, V value, HashMap.Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<>(hash, key, value, e);
linkNodeLast(p);
return p;
}
前面說了，LinkedHashMap.Entry 繼承了 HashMap.Node，并且追加了兩個字段 before 和 after。
那，緊接着來看看
linkNodeLast()
方法：
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;
}
}
看到了吧，LinkedHashMap 在添加第一個元素的時候，會把 head 指派為第一個元素，等到第二個元素添加進來的時候，會把第二個元素的 before 指派為第一個元素，第一個元素的 afer 指派為第二個元素。
這就保證了鍵值對是按照插入順序排列的，明白了吧？
注：我用到的 JDK 版本為 14。
02、通路順序
LinkedHashMap 不僅能夠維持插入順序，還能夠維持通路順序。通路包括調用
get()
方法、
remove()
方法和
put()
方法。
要維護通路順序，需要我們在聲明 LinkedHashMap 的時候指定三個參數。
LinkedHashMap<String, String> map = new LinkedHashMap<>(16, .75f, true);
第一個參數和第二個參數，看過 HashMap 的同學們應該很熟悉了，指的是初始容量和負載因子。
第三個參數如果為 true 的話，就表示 LinkedHashMap 要維護通路順序；否則，維護插入順序。預設是 false。
Map<String, String> linkedHashMap = new LinkedHashMap<>(16, .75f, true);
linkedHashMap.put("沉", "沉默王二");
linkedHashMap.put("默", "沉默王二");
linkedHashMap.put("王", "沉默王二");
linkedHashMap.put("二", "沉默王二");
System.out.println(linkedHashMap);
linkedHashMap.get("默");
System.out.println(linkedHashMap);
linkedHashMap.get("王");
System.out.println(linkedHashMap);
輸出的結果如下所示：
{沉=沉默王二, 默=沉默王二, 王=沉默王二, 二=沉默王二}
{沉=沉默王二, 王=沉默王二, 二=沉默王二, 默=沉默王二}
{沉=沉默王二, 二=沉默王二, 默=沉默王二, 王=沉默王二}
當我們使用
get()
方法通路鍵位“默”的元素後，輸出結果中，
默=沉默王二
在最後；當我們通路鍵位“王”的元素後，輸出結果中，
王=沉默王二
在最後，
默=沉默王二
在倒數第二位。
也就是說，最不經常通路的放在頭部，這就有意思了。有意思在哪呢？
我們可以使用 LinkedHashMap 來實作 LRU 緩存，LRU 是 Least Recently Used 的縮寫，即最近最少使用，是一種常用的頁面置換算法，選擇最近最久未使用的頁面予以淘汰。
public class MyLinkedHashMap<K, V> extends LinkedHashMap<K, V> {
private static final int MAX_ENTRIES = 5;
public MyLinkedHashMap(
int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor, accessOrder);
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}
}
MyLinkedHashMap 是一個自定義類，它繼承了 LinkedHashMap，并且重寫了
removeEldestEntry()
方法——使 Map 最多可容納 5 個元素，超出後就淘汰。
我們來測試一下。
MyLinkedHashMap<String,String> map = new MyLinkedHashMap<>(16,0.75f,true);
map.put("沉", "沉默王二");
map.put("默", "沉默王二");
map.put("王", "沉默王二");
map.put("二", "沉默王二");
map.put("一枚有趣的程式員", "一枚有趣的程式員");
System.out.println(map);
map.put("一枚有顔值的程式員", "一枚有顔值的程式員");
System.out.println(map);
map.put("一枚有才華的程式員","一枚有才華的程式員");
System.out.println(map);
輸出結果如下所示：
{沉=沉默王二, 默=沉默王二, 王=沉默王二, 二=沉默王二, 一枚有趣的程式員=一枚有趣的程式員}
{默=沉默王二, 王=沉默王二, 二=沉默王二, 一枚有趣的程式員=一枚有趣的程式員, 一枚有顔值的程式員=一枚有顔值的程式員}
{王=沉默王二, 二=沉默王二, 一枚有趣的程式員=一枚有趣的程式員, 一枚有顔值的程式員=一枚有顔值的程式員, 一枚有才華的程式員=一枚有才華的程式員}
沉=沉默王二
和
默=沉默王二
依次被淘汰出局。
假如在 put “一枚有才華的程式員”之前 get 了鍵位為“默”的元素：
MyLinkedHashMap<String,String> map = new MyLinkedHashMap<>(16,0.75f,true);
map.put("沉", "沉默王二");
map.put("默", "沉默王二");
map.put("王", "沉默王二");
map.put("二", "沉默王二");
map.put("一枚有趣的程式員", "一枚有趣的程式員");
System.out.println(map);
map.put("一枚有顔值的程式員", "一枚有顔值的程式員");
System.out.println(map);
map.get("默");
map.put("一枚有才華的程式員","一枚有才華的程式員");
System.out.println(map);
那輸出結果就變了，對吧？
{沉=沉默王二, 默=沉默王二, 王=沉默王二, 二=沉默王二, 一枚有趣的程式員=一枚有趣的程式員}
{默=沉默王二, 王=沉默王二, 二=沉默王二, 一枚有趣的程式員=一枚有趣的程式員, 一枚有顔值的程式員=一枚有顔值的程式員}
{二=沉默王二, 一枚有趣的程式員=一枚有趣的程式員, 一枚有顔值的程式員=一枚有顔值的程式員, 默=沉默王二, 一枚有才華的程式員=一枚有才華的程式員}
沉=沉默王二
王=沉默王二
被淘汰出局了。
那 LinkedHashMap 是如何來維持通路順序呢？同學們感興趣的話，可以研究一下下面這三個方法。
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
afterNodeAccess()
會在調用
get()
方法的時候被調用，
afterNodeInsertion()
put()
afterNodeRemoval()
remove()
方法的時候被調用。
我來以
afterNodeAccess()
為例來講解一下。
void afterNodeAccess(HashMap.Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
哪個元素被 get 就把哪個元素放在最後。了解了吧？
那同學們可能還想知道，為什麼 LinkedHashMap 能實作 LRU 緩存，把最不經常通路的那個元素淘汰？
在插入元素的時候，需要調用
put()
方法，該方法最後會調用
afterNodeInsertion()
方法，這個方法被 LinkedHashMap 重寫了。
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
removeEldestEntry()
方法會判斷第一個元素是否超出了可容納的最大範圍，如果超出，那就會調用
removeNode()
方法對最不經常通路的那個元素進行删除。
03、最後
由于 LinkedHashMap 要維護雙向連結清單，是以 LinkedHashMap 在插入、删除操作的時候，花費的時間要比 HashMap 多一些。
這也是沒辦法的事，對吧，欲戴皇冠必承其重嘛。既然想要維護元素的順序，總要付出點代價才行。
那這篇文章就到此戛然而止了，同學們要覺得意猶未盡，請肆無忌憚地留言告訴我哦。（一不小心又在文末甩仨成語，有點文化底蘊，對吧？）
我是沉默王二，一枚有顔值卻假裝靠才華苟且的程式員。關注即可提升學習效率，别忘了三連啊，點贊、收藏、留言，我不挑，奧利給🌹。
注：如果文章有任何問題，歡迎毫不留情地指正。
如果你覺得文章對你有些幫助，歡迎微信搜尋「沉默王二」第一時間閱讀，回複關鍵字「小白」可以免費擷取我肝了 4 萬+字的 《Java 小白從入門到放肆》2.0 版；本文 GitHub github.com/itwanger 已收錄，歡迎 star。
微信掃描左側二維碼，關注作者的微信公衆号：「
沉默王二」
背景回複“
666”即可擷取一份 500G 的高清教學視訊，并且已經分門别類，可以按需下載下傳，速去！
本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。
如果覺得還有幫助的話，可以點一下右下角的【推薦】。