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

數(shù)據(jù)結(jié)構(gòu)

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

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

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

桶的實例有兩種，一種是 Node 的實例，是鏈表；另一種是 TreeNode 的實例，是紅黑樹。Node 是 HashMap 中的一個靜態(tài)內(nèi)部類，TreeNode 繼承了 Node。當(dāng)桶中的元素較少時，桶的結(jié)構(gòu)為單鏈表；當(dāng)桶中的元素較多時，桶的結(jié)構(gòu)會被轉(zhuǎn)化為紅黑樹。

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 內(nèi)部存儲結(jié)構(gòu)。第 1 行表示的是 table 數(shù)組，數(shù)組中的元素可能為 Node 實例，TreeNode 實例，或者 null。table 數(shù)組的長度至少為 64 才能存放 TreeNode。

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

下面幾個結(jié)論不是很準確：

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

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

❌ 紅黑樹中元素的數(shù)量總是超過 8

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

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

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

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

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

構(gòu)造器

HashMap 提供了 4 個構(gòu)造器，其中帶有參數(shù) initialCapacity 和 loadFactor 這兩個參數(shù)的構(gòu)造器最為關(guān)鍵。其源碼如下。

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 源碼中的大多數(shù) capacity 指的都是底層存儲數(shù)組的長度；loadFactor （負載因子）是一個在區(qū)間 (0,1) 的小數(shù)，它決定了何時應(yīng)該對 table 進行擴容。

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

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

tableSizeFor(capacity) 函數(shù)將計算出一個恰好大于等于 capacity 的2的n次方整數(shù)，作為 table 數(shù)組的長度，也就是說 table 數(shù)組的長度總是 2 的 n 次方。看這個算法時，將關(guā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; // 繼續(xù)填充2個 1 n |= n >>> 4; // 填充 4 個 1 n |= n >>> 8; // 填充 8 個 1 n |= n >>> 16; //填充 16 個 1。 執(zhí)行完這句之后，已經(jīng)確保最高位右邊部分全部填充成了 1，例如：cap = 101_0101b 時，n = 111_1111b return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; // n+1 進位，返回 1000_0000b }

剩下的 3 個構(gòu)造器如下。

// 傳入 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，傳入的元素會逐個放入到新構(gòu)造的 HashMap 實例中 public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }put(k, v) 過程

put(key, v) 是先調(diào)用了 hash(key) 方法計算了一下鍵的哈希值，然后調(diào)用的是 putVal() 方法將節(jié)點放到 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() 的結(jié)果的高 16 位和低 16 位進行異或操作再返回

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { // tab 代表 table 數(shù)組；p 表示節(jié)點；n 表示桶的數(shù)量；i 指向應(yīng)該放入的桶的下標 Node<K,V>[] tab; Node<K,V> p; int n, i; // table 沒有初始化，調(diào)用 resize() 構(gòu)造 table 數(shù)組 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 如果桶中沒有元素，則 table 數(shù)組的元素作為節(jié)點 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 表示對應(yīng)的鍵，如果鍵不存在 e 的值為空，如果鍵存在，讓 e 指向該節(jié)點 if (p.hash == hash && // p 此時指向 table 中的元素，也就是鏈表或者樹的根 ((k = p.key) == key || (key != null && key.equals(k)))) // 如果 p.key 恰好與 key 相等，存在著一個節(jié)點，讓 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 已經(jīng)存在了，HashMap 不會取構(gòu)造新的 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; // 操作數(shù)統(tǒng)計，用來檢查是否有多個線程同時修改 HashMap，JDK中很多非線程安全的容器中都用了這些操作 if (++size > threshold) // size 超過了 threshold，進行擴容操作 resize(); afterNodeInsertion(evict); return null;}

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

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

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

resize() / rehash

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

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

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

二是 HashMap 中元素的數(shù)量超過了閾值（即：size > threshold），需要對 table 進行擴容。此時 table 的長度為變?yōu)樵瓉淼?2 倍，HashMap 的內(nèi)部結(jié)構(gòu)也會發(fā)生改變，同一個桶中的元素可能被分配到不同的桶中。這個過程也叫 rehash。

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

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

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

舊的桶之所以能夠恰好拆分成兩個新的桶，是因為新的桶的總數(shù) newCap 為舊桶總數(shù) 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) { // 余數(shù)較小的桶有元素 loTail.next = null; newTab[j] = loHead;}if (hiTail != null) { // 余數(shù)較大的桶有元素 hiTail.next = null; newTab[j + oldCap] = hiHead;} } } }}get(k) 過程

get(k) 方法顯得比較簡單，它調(diào)用了 getNode() 方法。算法的時間復(fù)雜度約等于 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)

這兩個重載方法均調(diào)用了 removeNode 方法。remove(k) 只要找到對應(yīng)的 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() 方法中流程大致為：根據(jù) key 和 hash 找到對應(yīng) Node，然后根據(jù)各種條件判斷是否執(zhí)行移除。HashMap 的數(shù)據(jù)結(jié)構(gòu)決定了此操作的時間復(fù)雜度仍然大致為 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，對應(yīng)的節(jié)點由 node 指向 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { // 檢查 key 和 value 是否均符合要求 if (node instanceof TreeNode) // node 為紅黑樹節(jié)點((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); // 執(zhí)行紅黑樹移除操作 else if (node == p) // 查找到的 node 為桶中的第 1 個元素tab[index] = node.next; elsep.next = node.next; // 執(zhí)行單鏈表移除 ++modCount; --size; afterNodeRemoval(node); return node; } } return null;}迭代

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

方法 entrySet() 采用了延遲加載和緩存的機制，只有調(diào)用 entrySet() 方法時才創(chuàng)建 EntrySet 對象，并賦值給成員變量 this.entrySet 緩存起來。重復(fù)調(diào)用 entrySet() 并不會產(chǎn)生多個 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 對象，迭代相關(guān)的部分代碼如下。

int index; // 指向當(dāng)前的桶，初始值為 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 時的順序與放入順序無任何關(guān)系。HashMap 內(nèi)部也沒有維護任何與插入順序有關(guān)的信息。

小結(jié)

以上內(nèi)容就是 HashMap 的實現(xiàn)原理以及核心 API，這里直接總結(jié)一些關(guān)于 HashMap 的結(jié)論性的東西。

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

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

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

4）HashMap 中的元素是無序的，它沒有維護任何與順序有關(guān)的內(nèi)容；

5）單個哈希桶中的元素過多時，桶的結(jié)構(gòu)會由單鏈表轉(zhuǎn)化為紅黑樹；

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

以上就是詳解 Java HashMap 實現(xiàn)原理的詳細內(nèi)容，更多關(guān)于Java HashMap 實現(xiàn)原理的資料請關(guān)注好吧啦網(wǎng)其它相關(guān)文章！