假設有一個 1G 大的 HashMap，此時用戶請求過來剛好觸發它的擴容，會怎樣？
簡要回答
如果剛好觸發擴容，那么當前用戶請求會被阻塞，因為 HashMap的底層是基于數組+鏈表(紅黑樹)來實現的，一旦它發生擴容，就需要新增一個比之前大2倍的數組，然后將元素copy到新的數組上。
而 1G 的 HashMap 夠大，所以擴容需要一定的時間，而擴容使用的又是當前的線程，所以用戶此時會被阻塞，等待擴容完畢。
源碼詳解、擴展追問
HashMap put方法源碼
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}先計算key的hash值，再對其put
static final int hash(Object key) {
int h;
//為什么要右移16位？ 默認長度為2^5=16，與hash值&操作，容易獲得相同的值。
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}這里分為了三步：
- h=key.hashCode() //第一步 取hashCode值
- h^(h>>>16) //第二步 高位參與運算，減少沖突，hash計算到這里
- return h&(length-1); //第三步 取模運算，計算數據在桶中的位置，這里看后面的源碼
第3步(n-1)&hash原理：
- 實際上(n-1) & hash等于 hash%n都可以得到元素在桶中的位置，但是(n-1)&hash操作更快。
- 取余操作如果除數是 2 的整數次冪可以優化為移位操作。這也是為什么擴容時必須是必須是2的n次方
位運算(&)效率要比代替取模運算(%)高很多，主要原因是位運算直接對內存數據進行操作，不需要轉成十進制，因此處理速度非常快。
而計算hash是通過同時使用hashCode()的高16位異和低16位實現的(h >>> 16)：這么做可以在數組比較小的時候，也能保證考慮到高低位都參與到Hash的計算中，可以減少沖突，同時不會有太大的開銷。
hash值其實是一個int類型，二進制位為32位，而HashMap的table數組初始化size為16，取余操作為hashCode & 15 ==> hashCode & 1111 。這將會存在一個巨大的問題，1111只會與hashCode的低四位進行與操作，也就是hashCode的高位其實并沒有參與運算，會導很多hash值不同而高位有區別的數，最后算出來的索引都是一樣的。 舉個例子，假設hashCode為1111110001，那么1111110001 & 1111 = 0001，如果有些key的hash值低位與前者相同，但高位發生了變化，如1011110001 & 1111 = 0001，1001110001 & 1111 = 0001，顯然在高位發生變化后，最后算出來的索引還是一樣，這樣就會導致很多數據都被放到一個數組里面了，造成性能退化。 為了避免這種情況，HashMap將高16位與低16位進行異或，這樣可以保證高位的數據也參與到與運算中來，以增大索引的散列程度，讓數據分布得更為均勻（個人認為是為了分布均勻）
put流程如下：
圖片
// 第四個參數 onlyIfAbsent 如果是 true，那么只有在不存在該 key 時才會進行 put 操作
// 第五個參數 evict 我們這里不關心
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)//初始判斷，初始數組為空時
// resize()初始數組，需要進行擴容操作
n = (tab = resize()).length;
//這里就是上面的第三步，根據key的hash值找到數據在table中的位置
if ((p = tab[i = (n - 1) & hash]) == null)
//通過hash找到的數組下標，里面沒有內容就直接賦值
tab[i] = newNode(hash, key, value, null);
else {//如果里面已經有內容了
Node<K,V> e; K k;
if (p.hash == hash &&
//hash相同，key也相同，那就直接修改value值
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
//key不相同，且節點為紅黑樹，那就把節點放到紅黑樹里
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 1st
//如果滿足鏈表轉紅黑樹的條件，則轉紅黑樹
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//傳入的K元素已經存在，直接覆蓋value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)//檢查元素個數是否大于閾值，大于就擴容
resize();
afterNodeInsertion(evict);
return null;
}final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//檢查是否滿足轉換成紅黑樹的條件，如果數組大小還小于64，則先擴容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}總結put方法流程：
- 如果table沒有初始化就先進行初始化過程
- 使用hash算法計算key的索引判斷索引處有沒有存在元素，沒有就直接插入
- 如果索引處存在元素，則遍歷插入，有兩種情況：
- 一種是鏈表形式就直接遍歷到尾端插入
- 一種是紅黑樹就按照紅黑樹結構
- 插入鏈表的數量大于閾值8，且數組大小已經大等于64，就要轉換成紅黑樹的結構
- 添加成功后會檢查是否需要擴容
數組擴容源碼
//table數組的擴容操作
final Node<K,V>[] resize() {
//引用擴容前的node數組
Node<K,V>[] oldTab = table;
//舊的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//舊的閾值
int oldThr = threshold;
//新的容量、閾值初始化為0
int newCap, newThr = 0;
//計算新容量
if (oldCap > 0) {
//如果舊容量已經超過最大容量，讓閾值也等于最大容量，以后不再擴容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//沒超過最大值，就令newcap為原來容量的兩倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果舊容量翻倍沒有超過最大值，且舊容量不小于初始化容量16，則翻倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
//舊容量oldCap = 0時，但是舊的閾值大于0，令初始化容量設置為閾值
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//兩個值都為0的時候使用默認值初始化
newCap = 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;
//如果e沒有next節點，證明這個節點上沒有hash沖突，則直接把e的引用給到新的數組位置上
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 order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//從這條鏈表上第一個元素開始輪詢，如果當前元素新增的bit是0，則放在當前這條鏈表上
//如果是1，則放在"j+oldcap"這個位置上，生成“低位”和“高位”兩個鏈表
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
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);
//低位鏈表放到j這個索引的位置上
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//高位鏈表放到(j+oldCap)這個索引的位置上
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}顯然，HashMap的擴容機制，就是當達到擴容條件時會進行擴容。擴容條件就是當HashMap中的元素個數超過臨界值時就會自動擴容（threshold = loadFactor * capacity）。如果是初始化擴容，只執行resize的前半部分代碼，但如果是隨著元素的增加而擴容，HashMap需要重新計算oldTab中每個值的位置，即重建hash表，隨著元素的不斷增加，HashMap會發生多次擴容，這樣就會非常影響性能。所以一般建議創建HashMap的時候指定初始化容量
但是當使用HashMap(int initialCapacity)來初始化容量的時候，HashMap并不會使用傳進來的initialCapacity直接作為初始容量。JDK會默認計算一個相對合理的值當做初始容量。所謂合理值，其實是找到第一個比用戶傳入的值大的2的冪。也就是說，當new HashMap(7)創建HashMap的時候，JDK會通過計算，創建一個容量為8的Map；當new HashMap(9)創建HashMap的時候，JDK會通過計算，創建一個容量為16的Map。當然了，當創建一個HashMap時，表的大小并不會立即分配，而是在第一次put元素時進行分配，并且分配的大小會是大于或等于初始容量的最小的2的冪。
一般來說，initialCapacity = (需要存儲的元素個數 / 負載因子) + 1。注意負載因子（即 loaderfactor）默認為 0.75，如果暫時無法確定初始值大小，請設置為 16（即默認值）。HashMap 需要放置 1024 個元素，由于沒有設置容量初始大小，隨著元素增加而被迫不斷擴容，resize() 方法總共會調用 8 次，反復重建哈希表和數據遷移。當放置的集合元素個數達千萬級時會影響程序性能。
//初始化容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
//保證initialCapacity在合理范圍內，大于0小于最大容量
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);
}
static final int tableSizeFor(int cap) {
int n = cap - 1;
//|=計算方式：兩個二進制對應位都為0時,結果等于0,否則結果等于1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}/**
* 紅黑樹分裂方法
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
//當前這個節點的引用，即這個索引上的樹的根節點
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
//高位低位的初始樹節點個數都設成0
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
//bit=oldcap,這里判斷新bit位是0還是1，如果是0就放在低位樹上，如果是1就放在高位樹上，這里先是一個雙向鏈表
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
//！！！如果低位的鏈表長度小于閾值6，則把樹變成鏈表，并放到新數組中j索引位置
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
//高位不為空，進行紅黑樹轉換
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}/**
* 將樹轉變為單向鏈表
*/
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}/**
* 鏈表轉換為紅黑樹，會根據紅黑樹特性進行顏色轉換、左旋、右旋等
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//進行左旋、右旋調整
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}總結HashMap的實現：
- HashMap的內部存儲結構其實是 數組+ 鏈表+ 紅黑樹 的結合。當實例化一個HashMap時，會初始化initialCapacity和loadFactor，此時還不會創建數組
- 在put第一對映射關系時，系統會創建一個長度為initialCapacity（默認為16）的Node數組，這個長度在哈希表中被稱為容量(Capacity)，在這個數組中可以存放元素的位置我們稱之為“桶”(bucket)，每個bucket都有自己的索引，系統可以根據索引快速的查找bucket中的元素。
- 每個bucket中存儲一個元素，即一個Node對象，但每一個Node對象可以帶一個引用變量next，用于指向下一個元素，因此，在一個桶中，就有可能生成一個Node鏈。也可能是一個一個TreeNode對象，每一個TreeNode對象可以有兩個葉子結點left和right，因此，在一個桶中，就有可能生成一個TreeNode樹。而新添加的元素作為鏈表的last，或樹的葉子結點
總結HashMap的擴容和樹形化：
- 當HashMap中的元素個數超過數組大小(數組總大小length,不是數組中個數size)*loadFactor 時，就會進行數 組擴容，loadFactor的默認值(DEFAULT_LOAD_FACTOR)為0.75，這是一個折中的取值。也就是說，默認情況下，數組大小(DEFAULT_INITIAL_CAPACITY)為16，那么當HashMap中元素個數超過16*0.75=12（這個值就是代碼中的threshold值，也叫做臨界值）的時候，就把數組的大小擴展為 2*16=32，即擴大一倍，然后重新計算每個元素在數組中的位置，而這是一個非常消耗性能的操作，所以如果我們已經預知HashMap中元素的個數，那么預設元素的個數能夠有效的提高HashMap的性能
- 當HashMap中的其中一個鏈的對象個數如果達到了8個，此時如果capacity沒有達到64，那么HashMap會先擴容解決，如果已經達到了64，那么這個鏈會變成樹，結點類型由Node變成TreeNode類型。當然，如果當映射關系被移除后，下次resize方法時判斷樹的結點個數低于6個，也會把樹再轉為鏈表。
即當數組的某一個索引位置上的元素以鏈表形式存在的數據個數>8且當前數組的長度>64時，此時此索引位置上的所有數據改為使用紅黑樹存儲
HashMap擴容過程是怎樣的？（簡要版）
1.8擴容機制：當元素個數大于threshold時，會進行擴容，使用2倍容量的數組代替原有數組。采用尾插入的方式將原數組元素拷貝到新數組。1.8擴容之后鏈表元素相對位置沒有變化，而1.7擴容之后鏈表元素會倒置。
1.7鏈表新節點采用的是頭插法，這樣在線程一擴容遷移元素時，會將元素順序改變，導致兩個線程中出現元素的相互指向而形成循環鏈表，1.8采用了尾插法，避免了這種情況的發生。
原數組的元素在重新計算hash之后，因為數組容量n變為2倍，那么n-1的mask范圍在高位多1bit。在元素拷貝過程不需要重新計算元素在數組中的位置，只需要看看原來的hash值新增的那個bit是1還是0，是0的話索引沒變，是1的話索引變成“原索引+oldCap”（根據e.hash & oldCap == 0判斷） 。這樣可以省去重新計算hash值的時間，而且由于新增的1bit是0還是1可以認為是隨機的，因此resize的過程會均勻的把之前的沖突的節點分散到新的bucket。
HashMap 擴容機制的性能影響
擴容觸發條件：當 HashMap 中的元素數量超過 容量x負載因子 時，會觸發擴容。擴容會將容量擴展為當前容量的兩倍，并將所有鍵值對重新分配到新的桶(bucket)中。
性能影響：擴容是一個耗時的操作，因為它需要重新計算每個鍵的哈希值，并將鍵值對重新分配到新的桶中。因此，頻繁的擴容會顯著影響性能，特別是在存儲大量數據時。
為什么 HashMap 在擴容時采用2的n次方倍?
Hashmap 采用2的n次方倍作為容量，主要是為了提高哈希值的分布均勻性和哈希計算的效率
HasMap通過(n - 1)&hash來計算元素存儲的索引位置，這種位運算只有在數組容量是2的n次方時才能確保案引均勻分布，位運算的效率高于取模運算(hash%n)，提高了哈希計算的讀度
且當 hashMap擴容時，通過容量為2的n次方，擴容時只需通過簡單的位運算判斷是否需要遷移，這減少了重新計算哈希值的開銷，提升了 rehash 的效率。
為什么建議設置HashMap的容量？
HashMap有擴容機制，就是當達到擴容條件時會進行擴容。擴容條件就是當HashMap中的元素個數超過臨界值時就會自動擴容（threshold = loadFactor * capacity）。
如果沒有設置初始容量大小，隨著元素的不斷增加，HashMap會發生多次擴容。而HashMap每次擴容都需要重建hash表，非常影響性能。所以建議開發者在創建HashMap的時候指定初始化容量。
HashMap默認加載因子是多少？為什么是 0.75？
先看下HashMap的默認構造函數：
int threshold; // 容納鍵值對的最大值
final float loadFactor; // 負載因子
int modCount;
int size;Node[] table的初始化長度length為16，默認的loadFactor是0.7。
為什么默認負載因子是 0.75？官方答案如下：
As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.
上面的意思，簡單來說是默認負載因子為 0.75，是因為它提供了空間和時間復雜度之間的良好平衡。 負載因子太低會導致大量的空桶浪費空間，負載因子太高會導致大量的碰撞，降低性能。0.75 的負載因子在這兩個因素之間取得了良好的平衡。也就是說官方并未對負載因子為 0.75 做過的的解釋，只是大概的說了一下，0.75 是空間和時間復雜度的平衡，但更多的細節是未做說明的，Stack Overflow 進行了負載因子的科學推測，感興趣的可以學習學習
也就是說所，0.75是對空間和時間效率的一個平衡選擇，根據泊松分布，loadFactor 取0.75碰撞最小。一般不會修改，除非在時間和空間比較特殊的情況下 ：
- 如果內存空間很多而又對時間效率要求很高，可以降低負載因子Load factor的值 。
- 如果內存空間緊張而對時間效率要求不高，可以增加負載因子loadFactor的值，這個值可以大于1。
