注：感謝美團點評技術團隊的分享~，部落格部分內容摘抄自其中。侵刪！
今天我們來探究一下 HashMap 的內部實現機制。
明確 JDK 1.8 中的 HashMap 使用陣列 + 連結串列 + 紅黑樹的結構進行實現。
HashMap 的底層思想主要是雜湊表，我們來看看 Java 的設計者們是怎麼使用陣列 + 連結串列 + 紅黑樹設計出 HashMap 的。
1 HashMap的基本屬性既然是用雜湊表進行實現，那麼基本的資料結構就是陣列了，HashMap 部分原始碼如下：
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { transient Node<K,V>[] table; // HashMap 底層資料結構（Node 陣列） transient int size; // HashMap 中實際存在的鍵值對數量 transient int modCount; // 記錄 HashMap 內部結構發生變化的次數，用於快速失敗機制 int threshold; // 所能容納的 key-value 對極限（我將之稱為“負載”） final float loadFactor; // 負載因子：預設 0.75}除了 table 陣列之外，我將原始碼中的常用欄位也貼了出來。對於上面的程式碼，我們需要注意以下幾點：
不瞭解 AbstractMap<K,V> 抽象類、Map<K,V>, Cloneable, Serializable 介面的請自行百度transient 關鍵字：阻止本欄位進行序列化（具體使用請自行百度）threshold = length（雜湊表長度） * loadFactormodCount 記錄的是 HashMap 內部結構發生變化的次數，內部結構發生變化指的是結構發生變化，例如 put 新鍵值對，但是某個 key 對應的 value 值被覆蓋不屬於結構變化。有了對 table 陣列的認識，那麼我們用一張圖來描述一下 HashMap 中的雜湊表結構（來自 "美團點評技術團隊" 侵刪）：
瞭解了 HashMap 中的成員變數，再來看一下 HashMap 中定義的常量：
// 預設的初始容量，必須是2的冪。 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //最大容量（必須是 2 的冪且小於 2 的 30 次方，傳入容量過大將被這個值替換） static final int MAXIMUM_CAPACITY = 1 << 30; // 裝載因子static final float DEFAULT_LOAD_FACTOR = 0.75f; // JDK1.8特有 // 當 hash 值相同的記錄超過 TREEIFY_THRESHOLD，會動態的使用一個專門的紅黑樹實現來代替連結串列結構，使得查詢時間複雜度從 O(n) 變為 O(logn) static final int TREEIFY_THRESHOLD = 8; // JDK1.8特有 // 也是閾值，同上一個相反，當桶(bucket)上的連結串列數小於 UNTREEIFY_THRESHOLD 時紅黑樹轉連結串列 static final int UNTREEIFY_THRESHOLD = 6; // JDK1.8特有 // 樹的最小的容量，至少是 4 x TREEIFY_THRESHOLD = 32 然後為了避免(resizing 和 treeification thresholds) 設定成64 static final int MIN_TREEIFY_CAPACITY = 64;現在，我們關心的是 table 陣列中 Node 元素的實現，原始碼如下：
// 靜態內部類、操縱了 Map 介面中的 Entry<K,V> 介面static class Node<K,V> implements Map.Entry<K,V> { // key 所產生的 hash 值 （不變） final int hash; // key （不變） final K key; // value V value; // 指向下一個 Node 節點、（鏈地址法解決衝突） 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; } // 這些方法都不可被重寫 public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } // 計算 key 所產生的 hash 碼 public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } // 設定新值，返回舊值 public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } // 比較兩個物件是否相等 public final boolean equals(Object o) { if (o == this) return true; // 是否都操作 Map.Entry 介面 if (o instanceof Map.Entry) { // 屬於同一個類之後再對物件的屬性進行比較 Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; }}在這裡我們需要注意：
Node 的實現是一個靜態內部類，有關內部類與靜態內部類的理解，請檢視我的知乎回答：為什麼Java內部類要設計成靜態和非靜態兩種？hash 值與 key 的不變性：即使在 HashMap 中對 key 及 hash 做了final 關鍵字的約束，但是我們還是需要注意，最好使用不變物件作為 key。首先我們來了解一下 final 關鍵字在基本型別與引用型別的使用上有什麼不同？
當 final 修飾基本變數型別時，不能對基本型別變數重新賦值，因此基本型別變數不能被改變。當 final 修飾引用型別變數時，final 只保證這個引用型別變數所引用的地址不會改變，即一直引用同一個物件，但是這個物件(物件的非 final 成員變數的值可以改變)完全可以發生改變。再來討論，我們在使用 HashMap 時，為什麼最好選用不可變物件作為 key。
來看一下選用可變物件作為 HashMap 的 key 有可能會造成什麼影響？
import java.util.HashMap;import java.util.Map; public class MutableDemo1 { public static void main(String[] args) { Map<MutableKey, String> map = new HashMap<>(); MutableKey key = new MutableKey(10, 20); map.put(key, "Robin"); System.out.println(map.get(key)); key.setI(30); System.out.println(map.get(key)); }}輸出：
Robinnull為什麼最好不要使用可變物件作為 HashMap 的 key，結論：
如果 key 物件是可變的，那麼 key 的雜湊值就可能改變。在 HashMap 中可變物件作為 key 會造成資料丟失。
怎麼解決？
在 HashMap 中，儘量使用 String、Integer 等不可變型別用作 key。重寫自定義類的 hashcode 方法，保證在成員變數改變的同時該物件的雜湊值不變即可。（具體實現參見：HashMap 的 key 可以是可變的物件嗎？）3 HashMap中的put方法3.1 Hash值的計算我們對 HashMap 的基本組成結構已經有了完整的認識，接下來我們分析 HashMap 中最常用的方法之一：put()。
直接上原始碼：
public V put(K key, V value) { return putVal(hash(key), key, value, false, true);}在分析 putVal 的原始碼之前，我們先來看看 hash(key)：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}key 的 hash 值就是這樣得到的，key.hashCode()是一個本地方法，具體實現在原始碼中並沒有給出，但這並不是重點，我們需要注意的是在計算出 hash 值後，它又與本身的高 16 位進行了異或。（hash 值本身是 32 位）
為什麼這樣做？這樣做的好處是什麼呢？
主要是從速度、功效、質量來考慮的，這麼做可以在陣列 table 的 length 比較小的時候，也能保證考慮到高低 Bit 都參與到 Hash 的計算中，同時不會有太大的開銷。在混合了原始 hashCode 值的高位和低位後，加大了低位的隨機性，而且混合後的低位摻雜了高位的部分特徵，這樣高位的資訊也被變相保留下來，這就使得 hash 方法返回的值，具有更高的隨機性，減少了衝突。
下面舉例說明，n 為 table 的長度（假設為 16）。
3.2 put方法的解析在分析 put 方法的原始碼之前，我們先來看一張有關 put 方法執行過程的圖解：
根據圖片我們再對 put 方法的執行流程做一個總結，方便等下閱讀原始碼：
判斷鍵值對陣列 table 是否為空或為 null，否則執行 resize() 進行擴容；根據鍵值 key 計算 hash 值得到插入的陣列索引 i，如果 table[i] == null，直接新建節點新增，轉向 6，如果 table[i] 不為空，轉向 3；判斷 table[i] 的首個元素是否和 key 一樣，如果相同直接覆蓋 value，否則轉向 4，這裡的相同指的是 hashCode 以及 equals；判斷 table[i] 是否為 treeNode，即 table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，否則轉向 5；遍歷 table[i]，判斷連結串列長度是否大於 8，大於 8 的話把連結串列轉換為紅黑樹，在紅黑樹中執行插入操作，否則進行連結串列的插入操作；遍歷過程中若發現 key 已經存在直接覆蓋 value 即可；插入成功後，判斷實際存在的鍵值對數量 size 是否超過了負載 threshold，如果超過，進行擴容。putVal 方法原始碼：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 雜湊表為null || 雜湊表的長度為 0（resize 也是一個經典的方法） if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // (n - 1) & hash 計算出 key 在雜湊表中應該儲存的位置（除留餘數法，使用 & 運算 比 % 運算更快） if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; // 插入的 key 在 HashMap 中已經存在（之後進行 value 的直接覆蓋） if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 產生衝突，當前節點為紅黑樹節點 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 普通節點，使用鏈地址法進行處理 else { // 遍歷連結串列（插入新節點之後，判斷連結串列長度） for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 當處理衝突的鏈節點數大於等於 8 的時候，轉換紅黑樹 if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } // 插入的 key 在 HashMap 中已經存在 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // key 已經存在，直接覆蓋舊值 if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 記錄 HashMap 內部結構發生變化的次數，用於快速失敗機制 if (++size > threshold) resize(); // 擴容 afterNodeInsertion(evict); // 作用不明確 return null;}put 方法分析到這裡基本上就結束了，但是同樣有兩個值得思考的問題：
雜湊表索引定位：(n - 1) & hash；擴容機制：resize()。關於紅黑樹與快速失敗機制，不在這篇部落格中進行講述。
3.3 索引定位你不覺得以(n - 1) & hash這種方式定位元素在雜湊表中的位置很有趣嗎？
本質上，它還是“除留餘數法”，只不過由於位運算的緣故，會比取模運算要高效許多。
但是使用這種方法有一個前提，就是雜湊表 table 的長度 n 必須滿足 2 冪次方，因為 n-1 對應的二進位制就是前面全是 0，後面全是 1，相與後，只留下 hash 的後幾位，正好在長度為 n 的陣列下標範圍內。
舉個例子，假設 hash 值為 3，陣列長度 n 為 16，那麼我們使用取模運算得到：3 % 16 = 3，使用 & 運算：0011 & (16 - 1) 即 0011 & 1111 = 0011 得到的還是 3。
而在 HashMap 中，雜湊表 table 的預設初始值也為 16（原始碼如下）：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;我們不談紅黑樹，但必須探究包含在 put 方法中的 resize（擴容）機制。瞭解過 resize 方法之後，你會感嘆其設計之巧妙！
首先，對擴容機制做一個簡單的介紹：
擴容(resize)就是重新計算容量，向 HashMap 物件裡不停的新增元素，而 HashMap 物件內部的陣列無法裝載更多的元素時，物件就需要擴大陣列的長度，以便能裝入更多的元素。如果 HashMap 的實際大小 > 負載，則 HashMap 中的 table 的容量擴充為當前的一倍。容量翻倍後，重新計算每個 Node 的 index，將有限的元素對映到更大的陣列中，減少 hash 衝突的機率。
我將擴容機制分為了兩部分：1. 建立新的 table 陣列；2. 對元素進行 rehash。
建立新的 table 陣列，過程還是比較簡單的：
原 table 陣列的大小已經最大，無法擴容，則修改 threshold 的大小為 Integer.MAX_VALUE。產生的效果就是隨你碰撞，不再擴容；原 table 陣列正常擴容，更新 newCap（新陣列的大小） 與 newThr（新陣列的負載）；原 table 陣列為 null || length 為 0，則擴容使用預設值；原 table 陣列的大小在擴容後超出範圍，將 threshold 的大小更改為 Integer.MAX_VALUE。我們先擷取第一部分（建立新陣列）的原始碼進行研究：
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { // 超過最大值就不再擴充，隨你去碰撞（將 threshold 設定為 Integer.MAX_VALUE，則不會產生擴容） if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 擴容成功，更新 newCap 與 newThr 的大小（2 倍擴充套件） else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; } // ！！！對應的哪種情況？ else if (oldThr > 0) newCap = oldThr; // oldCap == 0 || oldTab == null else { newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 擴容失敗（擴容後 newCap >= MAXIMUM_CAPACITY） if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } // 更新負載的值 threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; // rehash 的過程 ... ... return newTab;}直接閱讀 JDK 1.8 中的 rehash 過程讓人有點頭大，為了便於理解，我們先來看看 JDK 1.7 中的 rehash，總體來說，兩個版本差別不大：
void transfer(Entry[] newTable) { Entry[] src = table; // src 引用了舊的 Entry 陣列 int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { // 遍歷舊的 Entry 陣列 Entry<K,V> e = src[j]; // 取得舊 Entry 陣列的每個元素 if (e != null) { src[j] = null; // 釋放舊 Entry 陣列的物件引用（for 迴圈後，舊的 Entry 陣列不再引用任何物件） do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); // 重新計算每個元素在陣列中的位置 e.next = newTable[i]; // 頭插法 newTable[i] = e; // 將元素放在陣列上 e = next; // 訪問下一個 Entry 鏈上的元素 } while (e != null); } }}為了方便理解，下面舉個例子說明下擴容過程：
注：JDK 1.7 中的 put 方法使用的是頭插法進行新節點的插入，在 JDK 1.8 中，則使用的是尾插法（見上述原始碼）。對 JDK 1.7 put 方法感興趣的同學可自行查閱有關資料。
假設我們的 hash 演算法就是簡單的用 key mod 一下表的大小。其中的雜湊桶陣列 table 的 size = 2，key = 3、7、5，put 順序依次為 5、7、3（JDK 1.7 頭插法）。在 mod 2 以後都衝突在 table[1] 這裡了。這裡假設負載因子 loadFactor=1，即當鍵值對的實際大小 size 大於 table 的負載（threshold）時進行擴容。接下來的步驟是雜湊桶陣列 resize 成 4，然後所有的 Node 重新 rehash 的過程。
3.4.2 JDK 1.8中的rehashJDK 1.8 中的 rehash 過程與 JDK 1.7 大同小異，相比 JDK 1.7，它主要對重新定位元素在雜湊表中的位置做了最佳化：
經過觀測可以發現，我們使用的是 2 次冪的擴充套件(指長度擴為原來 2 倍)，所以，元素的位置要麼是在原位置，要麼是在原位置再移動 2 次冪的位置。看下圖可以明白這句話的意思，n 為 table 的長度，圖（a）表示擴容前的 key1 和 key2 兩種 key 確定索引位置的示例，圖（b）表示擴容後 key1 和 key2 兩種 key 確定索引位置的示例，其中 hash1 是 key1 對應的雜湊與高位運算結果。
table 在擴容之後，因為 n 變為 2 倍，那麼 n-1 的 mask 範圍在高位多 1bit(紅色)，因此新的 index 就會發生這樣的變化：
因此，我們在擴充 HashMap 的時候，不需要像 JDK1.7 那樣重新計算 hash，只需要看看原來的 hash 值新增的那個 bit 是 1 還是 0 就好了，是 0 的話索引沒變，是 1 的話索引變成“原索引 + oldCap”。
瞭解了 JDK 1.8 相比 JDK 1.7 所做的最佳化之後，我們再看一下 JDK 1.8 中的 rehash 過程：
final Node<K,V>[] resize() { ... ... // rehash 的過程 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { // 釋放舊 Node 陣列的物件引用（for迴圈後，舊的 Node 陣列不再引用任何物件） oldTab[j] = null; // oldTab[j] 只有一個元素，直接進行 rehash if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // 原索引（頭指標與尾指標） Node<K,V> loHead = null, loTail = null; // 原索引 + oldCap（頭指標與尾指標） Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; // 對元素進行 rehash 的過程 do { next = e.next; // 原索引（尾插法） if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } // 原索引 + oldCap（尾插法） else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 將建立的連結串列放到新 table 數組合適的位置上 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab;}在多執行緒使用場景中，應該儘量避免使用執行緒不安全的 HashMap，而使用執行緒安全的 ConcurrentHashMap。那麼為什麼說 HashMap 是執行緒不安全的，下面舉例子說明在併發的多執行緒使用場景中使用 HashMap 可能造成死迴圈。程式碼例子如下(便於理解，仍然使用 JDK1.7 的環境)：
public class HashMapInfiniteLoop { private static HashMap<Integer,String> map = new HashMap<Integer,String>(2，0.75f); public static void main(String[] args) { map.put(5， "C"); new Thread("Thread1") { public void run() { map.put(7, "B"); System.out.println(map); }; }.start(); new Thread("Thread2") { public void run() { map.put(3, "A); System.out.println(map); }; }.start(); } }其中，map 初始化為一個長度為 2 的陣列，loadFactor = 0.75，threshold = 2 * 0.75 = 1，也就是說當 put 第二個 key 的時候，map 就需要進行 resize。
透過設定斷點讓執行緒 1 和執行緒 2 同時 debug 到 transfer 方法的首行。注意此時兩個執行緒已經成功新增資料。放開 thread1 的斷點至 transfer 方法的Entry next = e.next 這一行；然後放開執行緒 2 的斷點，讓執行緒 2 進行 resize。結果如下圖。
newTable 是區域性變數，所以兩個執行緒都有自己擴容後開闢的新的 table 陣列。（對應圖中橙色與紫色方塊）
注意，由於 Thread1 執行到了Entry next = e.next這一行，因此 e 指向了 key(3)，而 next 指向了 key(7)，其線上程二 rehash 後，指向了執行緒二重組後的連結串列（rehash 之後，會將 newtable 賦值給 HashMap 的成員變數 table）。
接著下一部分：
執行緒一被排程回來執行，先是執行 newTalbe[i] = e（對應圖中 thread1 的索引 3 處指向了 thread2 中 索引 3 處的 key = 3 的節點（thread2 中的 table 此時已經是成員變量了，因此共享））， 然後是 e = next，導致了 e 指向了 key(7)，而下一次迴圈的 next = e.next 導致了 next 指向了 key(3)。
當 next 指向 key(3) 的時候，e 為 key(7)，又經過一次迴圈後，結果如下圖：
虛線也表示有引用指向 key(7)，只不過是想將 thread1 所擁有的 table 與 成員變數 table 區分開。
此時再更新 e 與 next 的值，e 為 key(3)，next 為 null，因此下一次迴圈就是最後一次迴圈。經過下一次迴圈之後，由於 e.next = newTable[i] 導致 key(3).next 指向了 key(7)，而此時的 key(7).next 已經指向了 key(3)，環形連結串列就此形成。結果如下圖：
於是，當我們用執行緒一呼叫 map.get(11) 時，悲劇就出現了——無限迴圈。
4 總結明白靜態內部類 Node 的相關實現，清楚 HashMap 的底層實現是有關 Node 的 table 陣列（雜湊表）。注意使用 HashMap 時最好使用不變的物件作為 key。注意 HashMap 計算 key 的 hash 值時，使用了低位與高位異或的方式，返回最終的 hashcode。瞭解 HashMap 中的定位方式：(n - 1) & hash。在 HashMap 中使用鏈地址法解決衝突，並且當連結串列的節點個數大於 8 的時候，會轉換為紅黑樹。（JDK 1.8 新特性）JDK 1.8 中使用尾插法進行 put 與 resize，JDK 1.7 中使用頭插法進行 put 與 resize。JDK 1.8 中的 rehash 過程不用重新計算元素的雜湊值，因為元素的位置只有兩種情況：原位置 與 原位置 + 原本雜湊表的長度。清楚多執行緒環境下使用 HashMap 可能會造成的一種錯誤---形成環形連結串列。作者：_dhengyi連結：https://juejin.cn/post/6934332114280120327