擴容方法 resize( )
擴容機制：
- 什么時候才需要擴容
當HashMap中的元素個數(shù)超過數(shù)組大小(數(shù)組長度)*loadFactor(負載因子)時，就會進行數(shù)組擴容，loadFactor的默認值是 0.75 - HashMap 的擴容是什么
進行擴容，會伴隨著一次重· hash分配，并且會遍歷 hash 表中所有的元素，是非常耗時的。在編寫程序中，要盡量避免resize
設(shè)計計算hash值時，要避免出現(xiàn)hash沖突。也就是說不能讓它出現(xiàn)鏈表，更不應(yīng)該出現(xiàn)紅黑樹，這樣性能很差，如果出現(xiàn)了，證明hash算法，設(shè)計的太差。為了避免hash沖突，一，hash算法，二，加載因子
HashMap在進行擴容時，使用的rehash(偽哈希) 方式非常巧妙，因為每次擴容都是翻倍，與原來計算的(n - 1) & hash的結(jié)果相比，只是多了一個bit位，所以結(jié)點要么就在原來的位置，要么就被分配到 “原位置 + 舊容量” 這個位置
源數(shù)組長度: 16 n = 16 n-1=15
(n-1) & hash
0000 0000 0000 0000 0000 0000 0001 0000 16
0000 0000 0000 0000 0000 0000 0000 1111 15 n-1
假設(shè)一個hash1(key1): 1111 1111 1111 1111 0000 1111 0000 0101
-----------------------------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 索引 5
0000 0000 0000 0000 0000 0000 0000 1111 15 n-1
假設(shè)一個hash2(key2): 1111 1111 1111 1111 0000 1111 0001 0101
-----------------------------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 索引 5
=======================================================================================
此時數(shù)組擴容--> 16 * 2 = 32 n = 32 n-1=31
(n-1) & hash
0000 0000 0000 0000 0000 0000 0010 0000 32
0000 0000 0000 0000 0000 0000 0001 1111 31 n-1
假設(shè)一個hash1(key1): 1111 1111 1111 1111 0000 1111 0000 0101
-----------------------------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 索引 5
0000 0000 0000 0000 0000 0000 0001 1111 31 n-1
假設(shè)一個hash2(key2): 1111 1111 1111 1111 0000 1111 0001 0101
-----------------------------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0001 0101 索引 5 + 16
擴容之后的索引位置要么是原來索引,要么是原來索引 + 舊數(shù)組容量
舉例:
5 或者 5 + 16
因此元素在重新計算hash之后，因為n變?yōu)?2 倍，那么 n - 1 的標記范圍在高位多 1bit(紅色)，因此新的index就會發(fā)生這樣的變化
5 是假設(shè)計算出來的原來的索引。這樣就驗證了上述所描述的：擴容之后所以節(jié)點要么就在原來的位置，要么就被分配到 “原位置 + 舊容量” 這個位置
因此，我們在擴充
HashMap的時候，不需要重新計算 hash，只需要看看原來的hash 值新增的那個 bit 是 1 還是 0 就可以了，是 0 的話索引沒變，是 1 的話索引變成 “原位置 + 舊容量” ?？梢钥纯聪聢D為 16 擴充為 32 的resize示意圖：
正是因為這樣巧妙的 rehash(偽哈希) 方式，既省去了重新計算hash值的時間，而且同時，由于新增的1bit 是 0 還是 1 可以認為是隨機的，在 resize的過程中保證了rehash(偽哈希)之后每個桶上的結(jié)點數(shù)一定小于等于原來桶上的結(jié)點數(shù)，保證了 rehash(偽哈希) 之后不會出現(xiàn)更嚴重的 hash沖突，均勻的把之前的沖突的結(jié)點分散到新的桶中了
源碼 resize 方法的解讀
final Node<K,V>[] resize() {
// 得到當前數(shù)組
Node<K,V>[] oldTab = table;
// 如果當前數(shù)組等于null長度返回0，否則返回當前數(shù)組的長度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//當前閥值點 默認是12(16*0.75)
int oldThr = threshold;
int newCap, newThr = 0;
// 如果老的數(shù)組長度大于0
// 開始計算擴容后的大小
if (oldCap > 0) {
// 超過最大值就不再擴充了，就只好隨你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
// 修改閾值為int的最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
/*
沒超過最大值，就擴充為原來的2倍
1) (newCap = oldCap << 1) < MAXIMUM_CAPACITY 擴大到2倍之后容量要小于最大容量
2）oldCap >= DEFAULT_INITIAL_CAPACITY 原數(shù)組長度大于等于數(shù)組初始化長度16
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 閾值擴大一倍
newThr = oldThr << 1; // double threshold
}
// 老閾值點大于0 直接賦值
else if (oldThr > 0) // 老閾值賦值給新的數(shù)組長度
newCap = oldThr;
else { // 直接使用默認值
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計算新的resize最大上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 新的閥值 默認原來是12 乘以2之后變?yōu)?4
threshold = newThr;
// 創(chuàng)建新的哈希表
@SuppressWarnings({"rawtypes","unchecked"})
//newCap是新的數(shù)組長度--》32
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 判斷舊數(shù)組是否等于空
if (oldTab != null) {
// 把每個bucket都移動到新的buckets中
// 遍歷舊的哈希表的每個桶，重新計算桶里元素的新位置
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 原來的數(shù)據(jù)賦值為null 便于GC回收
oldTab[j] = null;
// 判斷數(shù)組是否有下一個引用
if (e.next == null)
// 沒有下一個引用，說明不是鏈表，當前桶上只有一個鍵值對，直接插入
newTab[e.hash & (newCap - 1)] = e;
//判斷是否是紅黑樹
else if (e instanceof TreeNode)
// 說明是紅黑樹來處理沖突的，則調(diào)用相關(guān)方法把樹分開
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 采用鏈表處理沖突
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 通過上述講解的原理來計算結(jié)點的新位置
do {
// 原索引
next = e.next;
// 這里來判斷如果等于true e這個結(jié)點在resize之后不需要移動位置
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
