目錄
HashMap底層原理
JDK1.8及以后底層結構為：數組+鏈表+紅黑樹
默認參數
擴容機制
數組
鏈表
紅黑樹
HashMap為什么用紅黑樹不用B樹
HashMap什么時候擴容
HashMap的長度為什么是 2的 N 次方
HashMap底層原理
JDK1.8及以后底層結構為：數組+鏈表+紅黑樹
HashMap是Java集合框架中一種基于哈希表實現的Map接口，它存儲鍵值對，鍵是唯一的，而值可以重復。它的底層結構是一個數組結構，在實際情況中，這個數組被分為多個“桶（bucket）”，每個桶內存儲的是鏈表或紅黑樹（JDK1.8中引入），具體使用哪種取決于鏈表的長度和當前Map的大小
-
默認參數
-
默認負載因子（load factor）：0.75。負載因子是衡量HashMap滿的程度的一個標準。當HashMap中的元素數量達到容量與負載因子的乘積時，就會進行擴容。
-
默認容量（capacity）：16，必須是2的冪。
-
-
擴容機制
-
當HashMap中的元素數量達到threshold時，即當前容量乘以負載因子，HashMap會進行擴容操作。
-
擴容操作會創建一個新的數組，其大小為原數組大小的兩倍，并重新計算每個鍵的哈希值和在新數組中的位置。
-
這個過程涉及到重新計算每個鍵的哈希值，并將所有的鍵值對重新插入到新的數組中，因此擴容是一個比較耗費性能的操作。
-
-
數組
-
作用：數組是HashMap存儲元素的主要結構，每個數組元素是一個桶（bucket），可以存儲一個或多個鍵值對（Entry）。
-
默認大小：默認初始容量為16（必須是2的冪）。
-
擴容機制：當HashMap中的元素數量達到容量與負載因子乘積時，即size >= threshold（threshold = capacity * load factor），數組會進行擴容操作，擴容為原來的兩倍大小。
-
對于默認的容量和負載因子，threshold 的默認值是： threshold = 16 * 0.75 = 12 這意味著當 HashMap 中的元素數量達到 12 時，HashMap 會進行擴容操作。擴容后的新容量是原容量的兩倍為36，同時 threshold 也會相應地更新為新的容量乘以負載因子。
-
鏈表
-
作用：當數組的同一個桶位置（即索引相同）發生哈希碰撞時，多個鍵值對會以鏈表的形式存儲。JDK 1.8之前，HashMap就是使用鏈表處理沖突；JDK 1.8之后，當鏈表長度大于一定閾值時，鏈表會轉換為紅黑樹。
-
默認閾值：鏈表轉紅黑樹的閾值為8（當鏈表長度大于8時，會轉換為紅黑樹）。
-
-
紅黑樹
-
作用：為了提高HashMap的性能，當鏈表長度過長時，鏈表會被轉換成紅黑樹。這樣可以減少搜索時間，從O(n)降低到O(log n)。
-
默認閾值：鏈表轉回鏈表的閾值為6（當紅黑樹中的節點數量小于6時，會轉換回鏈表）。
-
HashMap為什么用紅黑樹不用B樹
HashMap 使用紅黑樹（Red-Black Tree）而不是 B 樹的主要原因是效率和復雜度。
-
效率：紅黑樹相對于 B 樹，在插入、刪除和查找操作上具有更好的平均性能。紅黑樹的平衡性質可以保證樹的高度相對較小，從而減少了搜索的路徑長度，提高了操作的效率。
-
復雜度：B 樹是一種多路搜索樹，節點可以包含多個關鍵字和指針，適合用于磁盤存儲等場景，可優化磁盤 IO 操作。然而，在內存中的數據結構中，紅黑樹的實現更為簡單，代碼的復雜度較低。同時，紅黑樹的性能在典型的 HashMap 使用場景中通常表現出良好的性能。
另外，HashMap 維護了一個哈希表和一個鏈表或紅黑樹的混合結構（JDK8 之后），當發生哈希沖突時，會使用鏈表或紅黑樹來處理沖突。鏈表適合處理沖突較少的情況，而紅黑樹則適合處理沖突較多的情況。紅黑樹相對于鏈表具有更高的查找效率，因此在沖突較多的情況下能夠提供更好的性能。
總之，HashMap 使用紅黑樹而不是 B 樹主要是出于對效率和復雜度的考慮。紅黑樹在內存中的實現更簡單，對于典型的 HashMap 使用場景能夠提供良好的性能，且適用于處理沖突較多的情況。
最簡回答：HashMap使用紅黑樹而不是B樹，是因為紅黑樹相對于B樹在插入、刪除和查找等操作上的平衡性能更好，且紅黑樹的節點比B樹的節點更小，占用的內存更少，適合存儲在內存中的數據結構。
HashMap什么時候擴容
-
在JDK1.7中，當HashMap中元素數量超過當前容量與負載因子（默認為0.75）的乘積時，會觸發擴容操作，擴容后的容量為當前容量的兩倍。例如，初始容量為16，當元素數量達到12時會觸發擴容，擴容后的容量為32。
-
在JDK 1.8中，HashMap的擴容和紅黑樹轉換是兩個獨立的操作，且順序是先擴容，然后再進行紅黑樹的轉換。當HashMap中的元素數量超過負載因子（默認為0.75）與數組容量的乘積時，會觸發擴容操作。擴容會重新調整數組的大小，并將原來數組中的元素重新分配到新的數組位置上。擴容操作會導致原本哈希沖突較多的鏈表長度變長，因此當鏈表長度超過閾值（默認為8）時，會將鏈表轉化為紅黑樹。綜上所述，在JDK 1.8中，HashMap的操作順序是先擴容，然后再進行紅黑樹的轉換。擴容是為了減少哈希沖突，提高HashMap的性能和效率，而鏈表轉紅黑樹的操作則是為了在特定情況下提供更好的查找、插入和刪除元素的性能。
HashMap的長度為什么是 2的 N 次方
為了能讓 HashMap 存數據和取數據的效率高，盡可能地減少 hash 值的碰撞，也就是說盡量把數
據能均勻的分配，每個鏈表或者紅黑樹長度盡量相等。我們首先可能會想到 % 取模的操作來實現。
下面是回答的重點喲：
取余（%）操作中如果除數是 2 的冪次，則等價于與其除數減一的與（&）操作（也就是說hash % length == hash &(length - 1) 的前提是 length 是 2 的 n 次方）。并且，采用二進制位操作 & ，相對于 % 能夠提高運算效率。
這就是為什么 HashMap 的長度需要 2 的 N 次方了
最簡回答：HashMap的長度選擇為2的N次方是為了提高散列算法的效率和分布均勻性，通過使用2的冪次方作為長度，可以確保哈希碼的高位和低位可以均勻參與到散列計算中，減少哈希沖突的發生，并提高散列算法的效率和性能。
)
