HashMap 是 Java 中最常見數據結構之一，它能夠在 O(1) 時間復雜度存儲鍵值對和根據鍵值讀取值操作。本文將分析其內部實現原理（基于 jdk1.8.0_231）。

數據結構

HashMap 是基于哈希值的一種映射，所謂映射，即可以根據 key 獲取到相應的 value。例如：數組是一種的映射，根據下標能夠取到值。不過相對于數組，HashMap 占用的存儲空間更小，復雜度卻同樣為 O(1)。

HashMap 內部定義了一排“桶”，用一個叫 table 的 Node 數組表示；key-value 存放到 HashMap 中時，根據 key 計算的哈希值決定存放的桶。當多個鍵值對計算出來的哈希值相等時，就產生了哈希碰撞，此時多個元素會放到同一個桶中。

transient Node<K,V>[] table; // 桶數組transient int size; // 統計 HashMap 實例中有多少個元素，不等于 table.length

桶的實例有兩種，一種是 Node 的實例，是鏈表；另一種是 TreeNode 的實例，是紅黑樹。Node 是 HashMap 中的一個靜態內部類，TreeNode 繼承了 Node。當桶中的元素較少時，桶的結構為單鏈表；當桶中的元素較多時，桶的結構會被轉化為紅黑樹。

static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next;}static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red;}

下圖表示的是一個 HashMap 內部存儲結構。第 1 行表示的是 table 數組，數組中的元素可能為 Node 實例，TreeNode 實例，或者 null。table 數組的長度至少為 64 才能存放 TreeNode。

需要注意的是，單鏈表的長度和紅黑樹元素數量取決于 TREEIFY_THRESHOLD（值為 8）, UNTREEIFY_THRESHOLD（值為 6），MIN_TREEIFY_CAPACITY（值為 64） 三者。

下面幾個結論不是很準確：

❌ 單鏈表長度最多為 8，超過了 8 就會被樹化。

✅ 單鏈表樹化不僅要滿足單鏈表長度超過 8，而且要滿足 table 數組的長度達到 MIN_TREEIFY_CAPACITY，只不過每次嘗試樹化而實際沒有樹化的話，都會將 table 的長度增加 1 倍。所以單鏈表的長度有可能超過 8。

❌ 紅黑樹中元素的數量總是超過 8

✅ table 在擴容的過程中可能會觸發樹的拆分，即一個桶中的元素在 table 擴容之后可能分配到兩個不同的桶里，一棵紅黑樹可能被拆分成兩棵。若拆分后紅黑樹元素的數量小于等于 UNTREEIFY_THRESHOLD ，樹會被轉化為單鏈表。意味著拆分之后紅黑樹元素的數量可能為 7 或者 8。

為什么單鏈表元素較多的時候要轉化為紅黑樹？

單鏈表桶轉化為紅黑樹桶的過程稱為桶的樹化，在 HashMap 源碼中對應 treeifyBin(table, hash) 函數。如果使用單鏈表作為桶的數據結構，存在大量哈希碰撞時，鏈表會變得很長，進行一次操作的時間復雜度將變成 O(K)，其中 K 為所操作的桶中元素的個數。而紅黑樹能夠保證時間復雜度為 O(log(K))，所以桶中元素過多時，使用樹效果會更好，也可以在一定程度上防范利用哈希碰撞進行的黑客攻擊。是一種時間上的優化。

不過相對于鏈表節點 Node，紅黑樹節點 TreeNode 需要多維護 4 個引用和 1 個紅黑標志，存儲空間相對更大。而 HashMap 中的大部分桶都是存儲很少量元素的（如果大多數桶都存儲很多，鍵的哈希函數設計可能不太不合理），所以在一般情況下，也就是桶中元素很少時使用鏈表進行存儲。是一種空間上的優化。

另外，桶的數據結構之所以不使用二叉排序樹，是因為二叉排序樹在特殊情況下會退化成單鏈表。例如：不斷往同一個桶中從小到大順序放入元素，會導致所有的節點都只有右孩子。而紅黑樹能夠確保從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。

構造器

HashMap 提供了 4 個構造器，其中帶有參數 initialCapacity 和 loadFactor 這兩個參數的構造器最為關鍵。其源碼如下。

public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException('Illegal initial capacity: ' +initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException('Illegal load factor: ' +loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }

initialCapacity 表示的為期望的 table 的長度，JDK 源碼中的大多數 capacity 指的都是底層存儲數組的長度；loadFactor （負載因子）是一個在區間 (0,1) 的小數，它決定了何時應該對 table 進行擴容。

table 數組的長度發生改變時，將根據 loadFactor 計算 threshold 的值，公式為 threshold = table.length * loadFactor。當 HashMap 中元素的數量 size 大于閾值 threshod 時，將觸發 table 擴容。

構造器將傳入的 loadFactor 直接賦值給了成員變量 this.loadFactor，然后調用了 tableSizeFor(capacity) 函數計算了 this.threshold 的初始值。在這里 thershold 的意義是臨時存儲 table 的初始長度，只有往 HashMap 中放入元素時，才構造 table 數組，這是一種延遲初始化策略。

tableSizeFor(capacity) 函數將計算出一個恰好大于等于 capacity 的2的n次方整數，作為 table 數組的長度，也就是說 table 數組的長度總是 2 的 n 次方。看這個算法時，將關注點放在 cap 的二進制最高位 1 比較容易理解。

static final int tableSizeFor(int cap) { int n = cap - 1; // 處理特殊情況：cap 恰好為 2 的 n 次方，即最高二進制位 1 右邊全部為 0 的情況 n |= n >>> 1; // 最二進制位1右邊1位填充 1 個 1 n |= n >>> 2; // 繼續填充2個 1 n |= n >>> 4; // 填充 4 個 1 n |= n >>> 8; // 填充 8 個 1 n |= n >>> 16; //填充 16 個 1。 執行完這句之后，已經確保最高位右邊部分全部填充成了 1，例如：cap = 101_0101b 時，n = 111_1111b return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; // n+1 進位，返回 1000_0000b }

剩下的 3 個構造器如下。

// 傳入 initialCapacity，負載因子使用的是默認值 0.75 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } // capacity 和 loadFactor 均使用默認值 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } // 傳入一個 map，傳入的元素會逐個放入到新構造的 HashMap 實例中 public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }put(k, v) 過程

put(key, v) 是先調用了 hash(key) 方法計算了一下鍵的哈希值，然后調用的是 putVal() 方法將節點放到 HashMap 中。

public V put(K key, V value) { return putVal(hash(key), key, value, false, true);}哈希值計算

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);} 若 key 為 null，則直接返回 0 作為哈希值； 若 key 不為 null，則對 key.hashCode() 的結果的高 16 位和低 16 位進行異或操作再返回

這里對哈希值二進制的高 16 位和低 16 位取余的原因是為了讓這兩部分的二進制位都對桶的選擇結果產生影響，減小哈希碰撞的概率。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { // tab 代表 table 數組；p 表示節點；n 表示桶的數量；i 指向應該放入的桶的下標 Node<K,V>[] tab; Node<K,V> p; int n, i; // table 沒有初始化，調用 resize() 構造 table 數組 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 如果桶中沒有元素，則 table 數組的元素作為節點 if ((p = tab[i = (n - 1) & hash]) == null) // 因為 n=2^x，所以 (n-1)&hash 等價于 hash % n tab[i] = newNode(hash, key, value, null); else { // 桶中有元素 Node<K,V> e; K k; // e 表示要存放值的 Node ， k 表示對應的鍵，如果鍵不存在 e 的值為空，如果鍵存在，讓 e 指向該節點 if (p.hash == hash && // p 此時指向 table 中的元素，也就是鏈表或者樹的根 ((k = p.key) == key || (key != null && key.equals(k)))) // 如果 p.key 恰好與 key 相等，存在著一個節點，讓 e 指向它 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); // 這一句很魔幻，有人說鏈表中達到了 7 個元素就會被樹化，也有說是 8 個的， // 實際上往桶里放入第 9 個元素時才會樹化，不信可以看一下這個實驗：https://github.com/Robothy/java-experiments/blob/main/HashMap/TreeifyThreshold/TreeifyThresholdTest.java if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break;}if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) // 在鏈表中找到了相同的 key break;p = e; } } // 如果 key 已經存在了，HashMap 不會取構造新的 Node，而是直接修改 Node 中的 value 屬性 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null)e.value = value; afterNodeAccess(e); // 這句在這里什么也沒干，留給 LinkedHashMap 的 return oldValue; } } ++modCount; // 操作數統計，用來檢查是否有多個線程同時修改 HashMap，JDK中很多非線程安全的容器中都用了這些操作 if (++size > threshold) // size 超過了 threshold，進行擴容操作 resize(); afterNodeInsertion(evict); return null;}

上面代碼中，需要注意以下幾點：

根據哈希值選擇桶的算法是 (n-1)&hash，由于 n 為 2 的冪次方，所以 (n-1)&hash 等價于 hash%n 。之所以采用位運算而不使用取余運算，是因為對于計算機來說，取余的計算開銷遠大于位運算。能夠這樣進行等價的前提是 n 為 2 的冪次方。這是哈希桶的數量總保持為 2 的冪次方的重要原因。可以在這里驗證一下這個算法。 桶中如果只有少量元素，桶的結構為單鏈表，某個桶中的元素超過了 TREEFIED_THRESHOLD，值為 8（必要非充分條件，前面有介紹，還需要滿足桶的數量達到 MIN_TREEIFY_CAPACITY，值為 64 ），該桶的結構將會轉化為紅黑樹； 當 HashMap 中元素的數量超過了閾值 threshold 時（threshold = 桶數量 * loadFactor），將觸發哈希表的擴容。

整個 put(k, v) 大致流程：

resize() / rehash

上述流程中，還有兩個重要的過程。首先是紅黑樹的操作，它能夠在 log(K) 的時間復雜度內完成增刪查改，K 為紅黑樹中元素的數量。

另一個操作時 resize()，它的目的是初始化哈希表 table 或者增加哈希桶的數量，減小哈希碰撞的概率。具體操作是讓成員變量 table 指向一個 Node 數組。

上面流程圖中可以看到，有兩個地方可能會觸發 resize()。一是 table 未初始化時，需要初始化 table。此時 table 初始長度可能為：1）threshold，指定了 initialCapaclity 的情況下，構造器中會根據 initialCapacity 計算出一個 capcacity 并賦值給 threshold；2）DEFAULT_INITIAL_CAPACITY（值為 16），沒有指定 initialCapacity 的情況下。

二是 HashMap 中元素的數量超過了閾值（即：size > threshold），需要對 table 進行擴容。此時 table 的長度為變為原來的 2 倍，HashMap 的內部結構也會發生改變，同一個桶中的元素可能被分配到不同的桶中。這個過程也叫 rehash。

resize() 源代碼比較長，這里分為兩部分來看，一部分是構造新的 Node 數組，更新 threshold；另一部分是將舊的 table 中的元素放到新 table 中的過程。先看前一部分：

final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; // oldTab 指向舊的 table int oldCap = (oldTab == null) ? 0 : oldTab.length; // 舊table的長度，如果 table 為空，則長度為 0 int oldThr = threshold; // 舊的閾值，如果 table 沒有初始化，threshold 臨時存儲的是構造方法中根據 initialCapacity 計算的初始 capacity int newCap, newThr = 0; if (oldCap > 0) { // 這句的含義是 table 已經初始化了，現在要對它擴容 if (oldCap >= MAXIMUM_CAPACITY) { // 值已經達到了 2^31，不能再擴容了，因為 int 范圍內不能再進行乘以 2 操作了，否則會導致整數溢出 threshold = Integer.MAX_VALUE; // 直接將 threshold 的值提高到 int 范圍內的最大值，讓后續的 put 操作不再觸發 resize() return oldTab; // 直接返回，不擴容了 } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // 新的 threshold 變為原來的兩倍，因為新的 capacity 也是原來的兩倍，而 threshod = capacity * loadFactor } else if (oldThr > 0) // 舊的 threshold 大于 0；含義是 table 需要初始化，不過在構造 HashMap 時指定了 initialCapacity，table 的初始長度已經定下來了，臨時存放在 this.threshold 中，等于 oldThr newCap = oldThr; // 那么新的 table 的長度直接設置為 oldThr 即可 else { // 含義是 table 需要初始化，但是構造器中沒有指定初始化的相關參數，則直接使用默認參數計算即可 newCap = DEFAULT_INITIAL_CAPACITY; // 值為 16 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 值為 16 * 0.75 = 12 } if (newThr == 0) { // table 需要初始化，且構造器中指定了初始化參數 float ft = (float)newCap * loadFactor; // 使用構造器指定的參數計算閾值，臨時放在 ft 中。新閾值 = 新數組長度 * 負載因子 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); // 檢查 ft 有沒有超出范圍，畢竟是用戶輸入的參數，需要進行檢查 } threshold = newThr; // 將前面步驟中計算得到的 newThr 賦值給 this.threshold @SuppressWarnings({'rawtypes','unchecked'}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 實例化新的 Node 數組 table = newTab; // 讓 table 指向新的 Node 數組 if (oldTab != null) { // 舊的 table 不為空，則需要將舊 table 中的元素放到新的 table 中 // 省略將舊的 table 中的元素放到新的 table 中的代碼 } return newTab;}

resize() 前半部分代碼計算了新的閾值 threshold，創建了空的哈希表。接下來的代碼是將舊的哈希表中的元素放到新的哈希表中。

代碼算法的大致流程為：遍歷每一個桶，若桶為單鏈表，則拆成兩個鏈表作為2個新的桶；若桶為紅黑樹，則拆成2棵紅黑樹作為新的桶，若新的紅黑樹中元素的數量小于等于 UNTREEIFY_THRESHOLD，值為 6，則將紅黑樹轉化為單鏈表。

舊的桶之所以能夠恰好拆分成兩個新的桶，是因為新的桶的總數 newCap 為舊桶總數 oldCap 的 2 倍，即 newCap = 2 * oldCap，若 hash % oldCap == j，則 hash % (2*oldCap) 的值為 j 或 oldCap + j。也就是說下標為 j 的桶會可能被拆分成下標為 j 和 oldCap+j 的兩個桶。

if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { // 逐個遍歷桶 Node<K,V> e; if ((e = oldTab[j]) != null) { // 桶中有元素 oldTab[j] = null; if (e.next == null) // 桶中只有1個元素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; // 子鏈表（新桶），存放哈希值 % newCap == j 的元素Node<K,V> hiHead = null, hiTail = null; // 子鏈表（新桶），存放哈希值 % newCap == j + oldCap 的元素。Node<K,V> next;do { // 遍歷鏈表 next = e.next; if ((e.hash & oldCap) == 0) { // 算法比較巧妙，通過臨界的 1 位二進制位即可判斷該哈希值余上 newCap 所屬桶 if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.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;} } } }}get(k) 過程

get(k) 方法顯得比較簡單，它調用了 getNode() 方法。算法的時間復雜度約等于 O(1)

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; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // hash%table.length 定位到桶 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 直接取 table 中的元素 if ((e = first.next) != null) { if (first instanceof TreeNode) // 紅黑樹查找return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { // 單鏈表遍歷查找if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null;}remove(k) 與 remove(k, v)

這兩個重載方法均調用了 removeNode 方法。remove(k) 只要找到對應的 key 匹配即移除，remove(k, v) 需要 key 和 value 均匹配才移除。

public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;}public boolean remove(Object key, Object value) { return removeNode(hash(key), key, value, true, true) != null;}

removeNode() 方法中流程大致為：根據 key 和 hash 找到對應 Node，然后根據各種條件判斷是否執行移除。HashMap 的數據結構決定了此操作的時間復雜度仍然大致為 O(1)。

final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K,V> node = null, e; K k; V v; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // key 為桶中的第 1 個元素 node = p; // 直接取 table[(n-1)&hash] else if ((e = p.next) != null) { // 桶中超過 1 個元素 if (p instanceof TreeNode) // 桶為紅黑樹node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { // 桶為單鏈表do { // 單鏈表搜索 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e;} while ((e = e.next) != null); } }// 若找到了 key，對應的節點由 node 指向 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { // 檢查 key 和 value 是否均符合要求 if (node instanceof TreeNode) // node 為紅黑樹節點((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); // 執行紅黑樹移除操作 else if (node == p) // 查找到的 node 為桶中的第 1 個元素tab[index] = node.next; elsep.next = node.next; // 執行單鏈表移除 ++modCount; --size; afterNodeRemoval(node); return node; } } return null;}迭代

HashMap 沒有直接或間接實現 Iterable 接口，因此不能直接使用 for-each 語法結構去遍歷一個 HashMap。不過可以通過 entrySet() 方法獲取一個 EntrySet，然后對 EntrySet 進行遍歷來達到訪問每一個 key-value 的目的。

方法 entrySet() 采用了延遲加載和緩存的機制，只有調用 entrySet() 方法時才創建 EntrySet 對象，并賦值給成員變量 this.entrySet 緩存起來。重復調用 entrySet() 并不會產生多個 EntrySet 對象。

public Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es; return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;}

EntrySet 中的 iterator() 返回的是 EntryIterator 對象，迭代相關的部分代碼如下。

int index; // 指向當前的桶，初始值為 0final Node<K,V> nextNode() { Node<K,V>[] t; Node<K,V> e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); if ((next = (current = e).next) == null && (t = table) != null) { do {} while (index < t.length && (next = t[index++]) == null); // 不斷地跳過空的桶 } return e;}

迭代 HashMap 的順序是逐個遍歷哈希桶，桶中有元素，則遍歷單鏈表或紅黑樹。因此，遍歷 HashMap 時的順序與放入順序無任何關系。HashMap 內部也沒有維護任何與插入順序有關的信息。

小結

以上內容就是 HashMap 的實現原理以及核心 API，這里直接總結一些關于 HashMap 的結論性的東西。

1）HashMap 的 Key 和 Value 都可以為 null，當 key 為 null 時，計算的哈希值為 0；

2）HashMap 默認的加載因子 loadFactor 是 0.75，它與 table.length 一同決定了擴容閾值 threshold，計算公式為：threshold = table.length * loadFactor；

3）HashMap 各項操作的效率很高，在哈希碰撞不嚴重的情況下時間復雜度為 O(1)

4）HashMap 中的元素是無序的，它沒有維護任何與順序有關的內容；

5）單個哈希桶中的元素過多時，桶的結構會由單鏈表轉化為紅黑樹；

6）HashMap 中哈希表 table 的長度（桶的數量）總是 2 的冪次方，這保證了能夠通過高效的位運算將 key 映射到對應的桶。

以上就是詳解 Java HashMap 實現原理的詳細內容，更多關于Java HashMap 實現原理的資料請關注好吧啦網其它相關文章！