1.一篇文章讀懂HashMap（存儲、擴容、初始化過程）

參考文章鏈接：https://liyuanxin.blog.csdn.net/article/details/134867511?spm=1001.2014.3001.5502

HashMap 是 Java 中最常用的數據結構之一，它提供了快速的查找、插入和刪除操作，可以滿足大多數情況下的需求。然而，要深入理解 HashMap 的內部實現和工作原理并不是一件容易的事情。本篇文章旨將圍繞HashMap的特點、通過源碼解讀HashMap的存儲過程、擴容過程、初始化，來深入解讀 HashMap，包括其內部結構、工作原理、常見的使用場景以及性能優化等方面。

1.1HashMap簡介

1.1.1特點

1. 鍵值對存儲：HashMap 是基于鍵值對（Key-Value）存儲的數據結構，每個元素都是由鍵和值組成的一對數據。這種結構使得 HashMap 能夠通過鍵快速查找對應的值，因此在查找和插入操作上具有高效性。
2. 無序：HashMap 中的元素是無序排列的，即元素的存儲順序和插入順序無關。因此，在遍歷 HashMap 時無法保證元素的順序，如果需要有序性，可以考慮使用 LinkedHashMap。
3. 哈希表實現：HashMap 內部通常采用哈希表來實現。哈希表通過哈希函數將鍵映射到存儲桶中，從而實現了快速的查找、插入和刪除操作。在理想情況下，哈希表可以提供常量時間復雜度的性能，使得 HashMap 在大多數情況下具有高效的操作速度。
   • JDK1.8之前的數據結構是：鏈表+數組，JDK 1.8后是鏈表+數組+紅黑樹
   • 當鏈表長度大于8時，才會將鏈表轉化為紅黑樹，變為紅黑樹的目的是為了高效的查詢
   • 當鏈表的長度等于大于8，但是數組的長度小于64的時候，此時會選擇對數組進行擴容而不是將鏈表轉化為紅黑樹，這是因為在數據量比較小的情況下，使用紅黑樹反而會降低查詢效率。
4. 允許存儲 null 鍵和 null 值：HashMap 允許存儲 null 鍵和 null 值，因此在某些情況下可以簡化代碼邏輯。但是需要注意的是，由于鍵的唯一性，如果同時存儲了多個 null 鍵，則只會保留一個。
5. 非線程安全：HashMap 是非線程安全的，如果在多線程環境下使用，需要額外的同步措施來確保線程安全性，或者考慮使用 ConcurrentHashMap。

1.1.2優點

1. 快速的查找操作：由于 HashMap 內部采用哈希表實現，可以在接近常量時間復雜度內進行查找操作，使得查找元素非常高效。
2. 高效的插入和刪除操作：HashMap 也能夠在接近常量時間復雜度內執行插入和刪除操作，這使得對數據的動態修改非常高效。
3. 靈活性：HashMap 允許存儲不同類型的數據作為鍵和值，提供了靈活的數據存儲和檢索方式。
4. 允許存儲 null 鍵和 null 值：HashMap 允許存儲 null 鍵和 null 值，簡化了部分情況下的編程邏輯。

1.1.3缺點

1. 不保證順序：HashMap 中的元素是無序排列的，無法保證元素的插入順序或訪問順序，這在某些場景下可能會造成不便。
2. 空間開銷較大：由于哈希表需要維護一定數量的桶和哈希沖突處理機制，因此在存儲大量元素時可能會占用較多的內存空間。
3. 線程不安全：HashMap 是非線程安全的，如果在多線程環境下使用，需要額外的同步措施來確保線程安全，或者考慮使用 ConcurrentHashMap。
4. 哈希沖突：即使哈希函數設計良好，仍然可能發生哈希沖突，需要額外的處理機制來解決沖突，影響了部分操作的效率。

1.2深入解讀HashMap

1.2.1常用常量和變量

（1）常用常量

//1.序列化版本號常量：
private static final long serialVersionUID = 362498820763181265L;//2.集合的初始化容量（必須是2的n次冪）：16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//3.負載因子常量：0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;//注意：當HashMap中元素數超過 容量*加載因子時，HashMap會進行擴容//4.鏈表轉紅黑樹時最小鏈表長度常量：
static final int TREEIFY_THRESHOLD = 8;//5.鏈表轉紅黑樹時最小數組長度常量：
static final int MIN_TREEIFY_CAPACITY = 64;//6.紅黑樹轉為鏈表的最小數組長度常量
static final int UNTREEIFY_THRESHOLD = 6;//7.數組閾值（調整下一次擴容的容量值）（容量 * 負載因子）
int threshold;

（2）常用變量

//8.負載因子變量：
final float loadFactor;//9.存儲元素的數組：
transient Node<K,V>[] table;//10.存放具體元素的集合：
transient Set<Map.Entry<K,V>> entrySet;//11.實際存儲元素的個數：
transient int size;//12. 記錄HashMap的修改次數：
transient int modCount;

1.2.2存儲過程

在 *JDK1.8* 之前，HashMap由 *數組+鏈表* 數據結構組成。

在 *JDK1.8* 以后，HashMap由 *數組+鏈表+紅黑樹* 數據結構組成。

而本文我們只講講解基于 *數組+鏈表+紅黑樹* 的HashMap。我們接下來用一個實例來講解HashMap的存儲過程。

public class Demo01 {public static void main(String[] args) {HashMap hashMap = new HashMap<String, Integer>();hashMap.put("a", 1);hashMap.put("b", 2);hashMap.put("c", 3);System.out.println(hashMap);}
}

當我們執行存儲操作的時候，會發生如下操作：

1. 計算哈希值：當調用put方法時，HashMap會將傳入的key通過哈希函數（hash function）轉換為一個整數，這個整數被稱為哈希值。
2. 計算數組索引：HashMap使用哈希值對數組的長度進行取模運算，得到一個數組索引（即數組的位置），用于確定鍵值對在數組中的存儲位置。
3. 存儲鏈表或紅黑樹：如果該位置上已經有其他鍵值對存在，那么新的鍵值對將會以鏈表或紅黑樹的形式插入到該位置的末尾或中間。如果該位置還沒有任何鍵值對，那么直接將鍵值對存儲到該位置。

需要注意的是：

在JDK8之前，HashMap的構造方法就會幫我們創建一個 *長度為16*的*Entry[] table* 用來存儲鍵值數據。

在JDK8以后就不是在HashMap的構造方法底層來創建數組了，而是在第一次調用put方法的時候創建一個 *Node[] table* 來存儲鍵值對數據。

（1）過程

下面將通過源碼解讀HashMap的插入過程：

	//進入put方法public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}

• hash方法：計算key的hash值，相對于直接使用hashCode()方法的好處在于，可以減少哈希沖突的概率

  將鍵的哈希值右移16位，并與原哈希值進行異或運算，以增加哈希值高位的隨機性

  通過將二進制位的高位和低位都參與到哈希值的計算中，可以更好地保持哈希值的隨機性和分布性，從而減少不同鍵的哈希沖突，提高HashMap的性能。

• 并且通過這個方法我們也可以看出：HashMap的Key是可以為null的。當Key為null的時候，將位置0作為鍵值對的插入位置。

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• 計算hash值后，進入putVal方法

  //進入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;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);else {Node<K,V> e; K k;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);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;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;
  }
  

（2）哈希表為空

		if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;

• 首先，代碼將table賦值給變量tab，并進行判空操作。如果table為空，則說明哈希表尚未初始化，此時將n設為0。
• 如果table不為空，則 將table的長度賦值給變量n。
• 接下來，通過條件運算符判斷n是否為0，如果是0，則表明哈希表的長度為0，需要進行擴容操作。在這種情況下，代碼會調用resize()方法進行哈希表的擴容，并將擴容后的哈希表賦值給tab，并將擴容后的哈希表的長度賦值給n。
• 最后，返回 n作為哈希表的長度。

總的來說，*這段代碼的作用是獲取哈希表的長度，并在哈希表為null或者為空的時候，執行擴容操作。* 通過檢查哈希表的長度是否為0，可以判斷哈希表是否需要進行初始化或者擴容，從而保證HashMap的正常使用和性能優化。

（3）找到數組位置

		if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);

• 注意：在n為2的n次方的前提條件下，hash%n等價于(n-1)&hash，后者是是位運算，相對于符號運算，效率更高
• 步驟：
  • 首先，代碼計算出要插入的位置i，通過對hash值進行(n-1) & hash的位與運算得到。這里的n是哈希表的長度，通常是2的冪，通過這個位與運算可以將hash值限定在0到n-1之間，確保落在哈希表范圍內。
  • 然后，代碼判斷tab[i]位置是否為空，即當前位置是否已經存在節點。如果為空，則將新節點插入到這個位置。
  • 如果tab[i]位置不為空，則說明當前位置已經存在節點。這里可能會涉及到鏈表或者紅黑樹等數據結構，用于處理哈希沖突的情況，但在這段代碼中沒有展現出來。

總的來說，這段代碼的作用是 根據hash值找到對應的位置，然后判斷該位置是否已經存在節點，如果不存在則直接插入新節點，如果存在則根據具體的情況進行相應的處理，以保證HashMap中的鍵值對能夠正確存儲和檢索。

（4）數組該位置不為空處理情況：判斷key是否相同、判斷是否為紅黑樹、按照鏈表插入

• 首先，代碼定義了一個Node和一個K類型的變量k。然后通過一系列的條件判斷來確定如何處理哈希沖突:
  • 首先，判斷當前節點p的哈希值和鍵與要插入的哈希值和鍵是否相等，如果相等，則將當前節點p賦值給e。（即說明鍵是相同的，更新值即可，這里直接覆蓋節點）
  • 如果不相等，且當前節點p是TreeNode類型，則調用TreeNode的putTreeVal方法來處理插入。
  • 如果以上兩個條件都不滿足，則通過遍歷鏈表的方式找到合適的位置插入新節點，同時處理可能出現的樹化操作。

總的來說，****這段代碼的作用是處理哈希沖突的情況，具體處理方式取決于當前節點的類型以及與要插入節點的哈希值和鍵的比較結果。****通過合適的處理方式，保證HashMap在處理哈希沖突時能夠正確地插入新節點，并維護數據結構的完整性。

（5）key已存在，更新值

• 首先，將已存在節點e的值賦給oldValue，以便在后面返回舊的值。

• 然后會根據onlyIfAbsent的取值來判斷是否需要覆蓋已存在節點e的值：

  • 如果onlyIfAbsent為false，或者oldValue為null（即允許替換已有的空值），則將新值value賦給節點e的值e.value。

• 接著調用afterNodeAccess(e)方法來進行相關操作，比如LinkedHashMap中重寫的方法會將節點移動到鏈表末尾，以實現LRU策略。

• 最后返回舊的值oldValue，表示已存在鍵對應的舊值。

• 總的來說，這段代碼的作用是在HashMap中處理鍵已存在的情況，根據需要更新節點的值，并在操作后返回舊的值。

（6）判斷是否需要擴容

++modCount;
if (++size > threshold)resize();
afterNodeInsertion(evict);
return null;

• 首先，對modCount進行自增操作，用于在并發情況下對HashMap的修改進行控制。
• 然后對size進行自增操作，表示當前HashMap中鍵值對的數量增加了1。接著會檢查size是否超過了閾值threshold，如果超過了則需要進行哈希表的擴容操作。
• 如果size超過了threshold，就調用resize方法對哈希表進行擴容。哈希表的擴容會重新計算每個鍵值對的位置，以降低哈希沖突的概率。
• 接著調用afterNodeInsertion(evict)方法來進行相關操作，其中evict參數表示是否需要進行LRU策略的節點移除操作。
• 最后返回null，表示插入操作完成并且不需要返回任何值。

總的來說，*這段代碼的作用是在HashMap中處理插入新節點后更新相關計數器、進行哈希表的擴容操作，并在操作后進行相關處理。*

（7）小結

其實整個put操作的代碼邏輯鏈其實是比較清晰的，我們可以用圖表示為：

1.2.3擴容過程

（1）條件

• 滿足以下兩個條件，其中一種就可以

1. 當前存儲的數量大于等于閾值
2. 當某個鏈表長度>=8，但是數組存儲的結點數size() < 64時

（2）特點

先插后判斷是否需要擴容（擴容時是尾插法）

（3）缺點

缺點：多線程下，1.8會有數據覆蓋

舉例：

• 線程A：往index插，index此時為空，可以插入，但是此時線程A被掛起
• 線程B：此時，對index寫入數據，A恢復后，就把B數據覆蓋了

（4）擴容之后對table的調整

table容量變為2倍，但是不需要像之前一樣計算下標，只需要將hash值和舊數組長度相與即可確定位置。

1. 如果 Node 桶的數據結構是鏈表會生成 low 和 high 兩條鏈表，是紅黑樹則生成 low 和 high 兩顆紅黑樹

2. 依靠 (hash & oldCap) == 0 判斷 Node 中的每個結點歸屬于 low 還是 high。（若為零，則屬于low，若不為零，則屬于high）

   							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;}
   

3. 把 low 插入到 新數組中 當前數組下標的位置，把 high 鏈表插入到 新數組中 [當前數組下標 + 舊數組長度] 的位置

4. 如果生成的 low，high 樹中元素個數小于等于6退化成鏈表再插入到新數組的相應下標的位置

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) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_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;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)newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);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;}

（5）數組下標位置的確定原因

• 通過e.hash&oldCap確定該結點是屬于low還是high

							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;}

• 若為low，則插入到數組原來的位置；若為high，則插入到（數組原來的位置+原來數組的容量）的位置上

						if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}

• 通過（hash&oldCap）即可算出擴容后元素在數組下標的位置的原因，請看以下照片舉例：（ps，純用筆手寫，后拍照掃描，太久沒拿筆了，字體見諒hhhhhhhh）

總結：*也就是說實際上擴容后，從二進制來看，數組的下標位置只有最高位發生了變化，如果元素的二進制最高位為0，那么就是原位置，如果二進制最高是1，那么就會變為1，也就是原位置+舊容量*；這種方法可以極大提高運行效率

1.2.4HashMap的初始化

我們不講HashMap的自動初始化，源碼比較簡單，大家可以自己看一看。而在這里要著重講一下HashMap的手動擴容過程：

*我們都知道：HashMap的擴容過程是一個比較浪費時間的過程。因此我們如果想要提高代碼運行的效率，就要手動設置初始大小，避免自動擴容。但有的人會在這里陷入一個誤區，我們通過一個實際問題來引出：*

當我們要存放七個元素的時候，我們應該手動初始化大小為多少呢？

很多同學肯定下意識的回答 8 。 但 其實是錯誤 的！讓我們來思考一下：

如果設置為8 的話， 負載系數默認是0.75。那么 8 * 0.75 =6，也就是說數組中 實際元素達到6個就要擴容，我們如果存放七個元素，手動設置大小為8 的話，還是避免不了擴容。

因此：我們應該 手動設置為 （需要存儲的元素個數/負載因子）+1。這是計算手動設置容量 的通用方法。

注意：不可以修改負載系數，0.75是官方大量數據統計出來的一個比較均衡的負載因子，我們基本不會對其做修改！

1.3常見面試題

1.為什么集合的初始化容量必須是2的n次冪？

首先，當我們嘗試向HashMap中添加一個元素的時候，需要根據Key的hash值得到數組中的具體位置。而我們 不可以直接使用Key的hash值。這是因為Key的hash值不一定就在數組下標范圍內，因此我們要對Key的hash值再次進行操作，使其滿足值的范圍在數組下標范圍內。

這里的第一個思路就是取余。我們讓hash%n(數組長度)，這樣就可以控制得到的值始終在數組下標范圍內。

但是這里又有一個問題：如果是取余的話，效率是很低的，不如使用位運算。而我們的代碼在實際中也是用位運算來代替取余操作。

而我們在實際中也是這么做的，但是 hash % n 和 （n - 1）& hash 的值相等的前提是 n 是2 的 x 次冪

而除此之外，返回到使用這個方法的最外層，我們的目的還是為了讓數據能夠均勻分布，減少Hash沖突。

如果創建HashMap的時候，輸入的數組長度不是2的冪，那么HashMap就會通過位運算得到一個比我們輸入的數組長度大的，離我們輸入數組長度最近的一個2的冪。

2.hash方法為什么要右移16位異或？（(h = key.hashCode()) ^ (h >>> 16)）

其中 h = key.hashCode() ^ (h >>> 16) 的目的是為了 增加哈希值的隨機性，使得節點在哈希表中分布更均勻，減少哈希沖突，提高查找效率。

具體來說：

• 首先，通過 key.hashCode() 獲取鍵的哈希碼。
• 接著，通過 h >>> 16 將 h 右移16位，然后將結果與 h 進行異或操作 ^。這樣做是為了讓高位的信息參與到低位的計算中，增加低位的隨機性。

通過這樣的運算，可以讓原始的哈希值的高位和低位進行混合，并且引入了一定程度的隨機性，使得最終的哈希值分布更加均勻，減少了哈希沖突的概率。這種處理方式有助于提高HashMap的性能，特別是在處理大量數據時，能夠更有效地分散數據，減少鏈表長度，提高查找效率。

如果當哈希值的高位變化很大，低位變化很小，這樣就很容易造成哈希沖突了，所以這里把高低位都利用起來，從而解決了這個問題。

3.HashMap將鏈表轉化為紅黑樹的鏈表邊界長度為什么是8

這個問題其實在HashMap的源碼中就給了解釋：

簡要的意思就是：由于樹節點的大小是鏈表節點的兩倍，因此我們輕易不會將鏈表轉化為紅黑樹，這會對內存造成浪費。而在大量的實際數據插入的情況下，我們統計發現：箱子中的節點的頻率服從泊松分布。

當連續插到鏈表的第八個節點的時候，實際上概率已經很小了，已經達到了0.00000006。也就是說我們將鏈表的長度設置為8，就已經可以應對大多數的HashMap的Hash碰撞了 。當節點大于8的時候，我們再考慮查詢的效率問題，將其轉化為紅黑樹。

總結來講，將鏈表轉換紅黑樹的鏈表長度邊界設置為8，是綜合時間和空間的結果。

4.紅黑樹退化成鏈表的條件？

1. 擴容 resize( ) 時，紅黑樹拆分成的 樹的結點數小于等于臨界值6個，則退化成鏈表。
2. 刪除元素 remove( ) 時，在 removeTreeNode( ) 方法會檢查紅黑樹是否滿足退化條件，與結點數無關。如果紅黑樹根 root 為空，或者 root 的左子樹/右子樹為空，root.left.left 根的左子樹的左子樹為空，都會發生紅黑樹退化成鏈表。

5.HashMap是怎么解決哈希沖突的？

1. 使用 鏈地址法（使用散列表）來鏈接擁有相同下標的數據；
2. 使用 2次擾動函數（hash函數）來降低哈希沖突的概率，使得數據分布更平均；
3. 引入 紅黑樹 進一步降低遍歷的時間復雜度，使得遍歷更快；