Hashmap 的數據結構基礎是基于一維數組實現的，向其添加元素時通過計算key的hash值來確定具體存儲位置。添加元素過程中若出現hash沖突，也就是N個元素key的hash值相等，處理方式為：將元素轉為鏈表結構存儲，若鏈表節點數超過閾值8（TREEIFY_THRESHOLD = 8;），會將鏈表結構轉為紅黑樹，此轉化過程史稱 Hashmap 樹化

本文將對 HashMap 的構造HashMap()、數據存儲put()、擴容resize()、樹化等過程中所涉及 JDK 源碼做行級解釋。若有異議或建議歡迎您在文末留言討論，本小弟先做拋磚引玉！

---

HashMap 構造方法

HashMap 共提供了 4 種 構造方法，滿足各種常見場景下對容量的需求

// 第1種：創建一個 HashMap 并指定 容量(initialCapacity) 和裝載因子(loadFactor)public HashMap(int initialCapacity, float loadFactor) {// 指定容量不可小于0，但可設置為 0 。之后通過put()添加元素時，會resize()if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);// 如果指定的容量超過了最大值，則自動置為最大值，也就是 1 << 30（也就是2的30次方）if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;// 裝載因子不可小于等于 0 或 非數字（NaN）if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);// 初始化裝載因子this.loadFactor = loadFactor;// 初始化下次需要調整到的容量（容量*裝載因子）。this.threshold = tableSizeFor(initialCapacity);}// 第2種：創建一個指定容量的 HashMap，裝載因子使用默認的 0.75public HashMap(int initialCapacity) {// 調用上個構造方法初始化this(initialCapacity, DEFAULT_LOAD_FACTOR);}// 第3種：創建一個默認初始值的 HashMap ，容量為16，裝載因子為0.75public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}// 第4種：創建一個 Hashmap 并將 m 內包含的所有元素存入public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}

HashMap tableSizeFor()

獲取一個既大于 cap 又最接近 cap 的 2 的整數次冪數值

// 假設 cap = 128static final int tableSizeFor(int cap) {int n = cap - 1; // 則 n = 127 = 01111111n |= n >>> 1; // n = 01111111 ， n >>> 1 = 00111111 ， 按位或后 n = 01111111n |= n >>> 2; // n = 01111111 ， n >>> 1 = 00011111， 按位或后 n = 01111111n |= n >>> 4; // n = 01111111 ， n >>> 1 = 00000111， 按位或后 n = 01111111n |= n >>> 8; // n = 01111111 ， n >>> 1 = 00000000， 按位或后 n = 01111111n |= n >>> 16; // n = 01111111 ， n >>> 1 = 00000000， 按位或后 n = 01111111// 如果 n 小于 0 則返回 1，否則判斷 n 是否大于等于最大容量，是的話返回最大容量，不是就返回 n+1（也就是128）return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}

單單看代碼及注釋有點暈？來，上圖！一粒就見效！

---

Hashmap 數據存儲

HashMap.put()

通過源碼可獲悉， put() 會判斷當前元素插入位置的數據結構是 鏈表、紅黑樹還是普通元素，根據不同情況做不同插入處理

若當前數組未初始化，則對其進行初始化，若已初始化并完成了插入操作，將檢查是否需要擴容，根據結果做相應處理

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {// 定義新tab數組及node對象Node<K,V>[] tab; Node<K,V> p; int n, i;// 如果原table是空的或者未存儲任何元素則需要先初始化進行tab的初始化，初始化通過 resize() 進行if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 當數組中對應位置為null時，將新元素放入數組中if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);// 若對應位置不為空時處理哈希沖突else {Node<K,V> e; K k;// 1 - 普通元素判斷： 更新數組中對應位置數據if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 2 - 紅黑樹判斷：當p為樹的節點時，向樹內插入節點else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 3 - 鏈表判斷：插入節點else {for (int binCount = 0; ; ++binCount) {// 找到尾結點并插入if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 判斷鏈表長度是否達到樹化閾值，達到就對鏈表進行樹化if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 更新鏈表中對應位置數據if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 如果存在這個映射就覆蓋if (e != null) { // existing mapping for keyV oldValue = e.value;// 判斷是否允許覆蓋，并且value是否為空if (!onlyIfAbsent || oldValue == null)e.value = value;// 回調以允許LinkedHashMap后置操作afterNodeAccess(e); return oldValue;}}// 更新修改次數++modCount;// 檢查數組是否需要進行擴容，擴容同樣也通過 resize() 進行if (++size > threshold)resize();// 回調以允許LinkedHashMap后置操作afterNodeInsertion(evict);return null;}

具體的鍵值對存儲位置計算方法為：

if ((p = tab[i = (n - 1) & hash]) == null)// 向數組賦值新元素tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;// 如果新插入的結點和table中p結點的hash值，key值相同的話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) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;// 及時更新pp = e;}}// 如果存在這個映射就覆蓋if (e != null) { // existing mapping for keyV oldValue = e.value;// 判斷是否允許覆蓋，并且value是否為空if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e); // 回調以允許LinkedHashMap后置操作return oldValue;}}

HashMap.get()

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;}final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;// 將table賦值給變量tab并判斷非空 && tab 的廠部大于0 && 通過位運算得到求模結果確定鏈表的首節點賦值并判斷非空if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 判斷首節點hash值 && 判斷key的hash值（地址相同 || equals相等）均為true則表示first即為目標節點直接返回if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;// 若首節點非目標節點，且還有后續節點時，則繼續向后尋找if ((e = first.next) != null) {// 1 - 樹：判斷此節點是否為樹的節點，是的話遍歷樹結構查找節點，查找結果可能為nullif (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);// 2 - 鏈表：若此節點非樹節點，說明它是鏈表，遍歷鏈表查找節點，查找結果可能為nulldo {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;}

---

Hashmap 擴容

HashMap.resize()

final Node<K,V>[] resize() {// 把當前底層數組賦值給oldTab，為數據遷移工作做準備Node<K,V>[] oldTab = table;// 獲取當前數組的大小，等于或小于0表示需要初始化數組，大于0表示需要擴容數組int oldCap = (oldTab == null) ? 0 : oldTab.length;// 獲取擴容的閾值（容量*負載系數）int oldThr = threshold;// 定義并初始化新數組長度和目標閾值int newCap, newThr = 0;// 判斷是初始化數組還是擴容，等于或小于0表示需要初始化數組，大于0表示需要擴容數組。若 if(oldCap > 0)=true 表示需擴容而非初始化if (oldCap > 0) {// 判斷數組長度是否已經是最大，MAXIMUM_CAPACITY =（2^30）if (oldCap >= MAXIMUM_CAPACITY) {// 閾值設置為最大threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY) // 目標閾值擴展2倍，數組長度擴展2倍newThr = oldThr << 1; // double threshold}// 表示需要初始化數組而不是擴容else if (oldThr > 0) // 說明調用的是HashMap的有參構造函數，因為無參構造函數并沒有對threshold進行初始化newCap = oldThr;// 表示需要初始化數組而不是擴容，零初始閾值表示使用默認值else { // 說明調用的是HashMap的無參構造函數newCap = DEFAULT_INITIAL_CAPACITY;// 計算目標閾值newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 當目標閾值為0時需重新計算，公式：容量（newCap）*負載系數（loadFactor）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;// -------------------------------------------------------------------------------------// 此時已完成初始化數組或擴容數組，但原數組內的數據并未遷移至新數組（擴容后的數組），之后的代碼則是完成原數組向新數組的數據遷移過程// -------------------------------------------------------------------------------------// 判斷原數組內是否有存儲數據，有的話開始遷移數據if (oldTab != null) {// 開始循環遷移數據for (int j = 0; j < oldCap; ++j) {Node<K,V> e;// 將數組內此下標中的數據賦值給Node類型的變量e，并判斷非空if ((e = oldTab[j]) != null) {oldTab[j] = null;// 1 - 普通元素判斷：判斷數組內此下標中是否只存儲了一個元素，是的話表示這是一個普通元素，并開始轉移if (e.next == null)newTab[e.hash & (newCap - 1)] = e;// 2 - 紅黑樹判斷：判斷此下標內是否是一顆紅黑樹，是的話進行數據遷移else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);// 3 - 鏈表判斷：若此下標內包含的數據既不是普通元素又不是紅黑樹，則它只能是一個鏈表，進行數據轉移else { // preserve orderNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}// 返回初始化完成或擴容完成的新數組return newTab;}

---

HashMap 樹化

鏈表的查找性能是O(n)，若節點數較小性能不回收太大影響，但數據較大時差距將逐漸顯現。樹的查找性能是O(log(n))，性能優勢瞬間體現

---

本篇將持續更新 HashMap 相關知識，一起查漏補缺學個痛快！歡迎點贊留香丨留言鼓勵丨指出不足！

---

總結

以上是生活随笔為你收集整理的深深的码丨Java HashMap 源码透析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。