1. 導讀

上期分享了HashMap的key定位以及數據節點的設計, 本期就下面三個問題來分享下個人對於HashMap擴容的理解:

.1 HashMap為什麼要擴容? 何時擴容?

.2 負載因子為什麼是0.75?

.3 HashMap如何擴容;

2. HashMap為什麼要擴容

經過上期分享, 我們都知道HashMap在構建初始是可以指定table(hash槽)的長度的, 假設我們設定了2, 這時候有10萬數據要插入, 最好的情況就是兩邊各是5萬, 最差的情況就是一邊是10萬, 顯然這個時候hash衝突已經很嚴重了, 為了解決衝突, 我們就需要對table進行擴容, 所以HashMap的擴容就是加長table的長度, 來減少hash衝突的概率;

3. HashMap何時擴容

HashMap是如何來判定何時該擴容的呢?

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
...
if (++size > threshold)
resize();
...
}

上面代碼是HashMap::put的核心實現, 我將與本問題無關的代碼都省略了, HashMap會在兩個地方進行resize(擴容):

.1 HashMap實行了懶載入, 新建HashMap時不會對table進行賦值, 而是到第一次插入時, 進行resize時構建table;

.2 當HashMap.size 大於 threshold時, 會進行resize;threshold的值我們在上一次分享中提到過: 當第一次構建時, 如果沒有指定HashMap.table的初始長度, 就用默認值16, 否則就是指定的值; 然後不管是第一次構建還是後續擴容, threshold = table.length * loadFactor;

3. 為什麼是0.75

HashMap的擴容時取決於threshold, 而threshold取決於loadFactor, loadFactor(負載因子)HashMap的默認值是0.75(3/4), 那麼為什麼當HashMap的容量超過3/4時就需要擴容了呢? 為什麼不是1/2擴容 或者 等於table.length時擴容呢?

答案就在HashMap的注釋中:

/**
* Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
*
*/

根據統計學的結果, hash衝突是符合泊松分布的, 而衝突概率最小的是在7-8之間, 都小於百萬分之一了; 所以HashMap.loadFactor選取只要在7-8之間的任意值即可, 但是為什麼就選了3/4這個值, 我們看了HashMap的擴容機制也就知道了;

4. HashMap如何擴容

因為擴容的代碼比較長, 我用文字來敘述下HashMap擴容的過程:

.1 如果table == null, 則為HashMap的初始化, 生成空table返回即可;

.2 如果table不為空, 需要重新計算table的長度, newLength = oldLength << 1(注, 如果原oldLength已經到了上限, 則newLength = oldLength);

.3 遍歷oldTable:

.3.2 首節點為空, 本次循環結束;

.3.1 無後續節點, 重新計算hash位, 本次循環結束;

.3.2 當前是紅黑樹, 走紅黑樹的重定位;

.3.3 當前是鏈表, JAVA7時還需要重新計算hash位, 但是JAVA8做了優化, 通過(e.hash & oldCap) == 0來判斷是否需要移位; 如果為真則在原位不動, 否則則需要移動到當前hash槽位 + oldCap的位置;

HashMap::resize的核心就是上圖, 鏈表與紅黑樹的resize過程大同小異: 紅黑樹是把構建新鏈表的過程變為構建兩顆新的紅黑樹, 定位table中的index都是用的 e.hash & oldCap == 0 來判斷;

再來看下 e.hash & oldCap == 0為什麼可以判斷當前節點是否需要移位, 而不是再次計算hash;

仍然是原始長度為16舉例:

old:
10: 0000 1010
15: 0000 1111
&: 0000 1010

new:
10: 0000 1010
31: 0001 1111
&: 0001 1010

從上面的示例可以很輕易的看出, 兩次indexFor()的差別只是第二次參與位於比第一次左邊有一位從0變為1, 而這個變化的1剛好是oldCap, 那麼只需要判斷原key的hash這個位上是否為1: 若是1, 則需要移動至oldCap + i的槽位, 若為0, 則不需要移動;

這也是HashMap的長度必須保證是2的倍數的原因, 正因為這種環環相扣的設計, HashMap.loadFactor的選值是3/4就能理解了, table.length * 3/4可以被優化為(table.length >> 2) << 2) - (table.length >> 2) == table.length - (table.lenght >> 2), JAVA的位運算比乘除的效率更高, 所以取3/4在保證hash衝突小的情況下兼顧了效率;

5. JDK8對JDK7的優化

void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}

上面的代碼是JAVA7中對於HashMap節點重新定位的代碼, 我們都知道HashMap是非線程安全的, 最主要的原因是他在resize的時候會形成環形鏈表, 然後導致get時死循環;

resize前的HashMap如下圖所示:

這時候有兩個線程需要插入第四個節點, 這個時候HashMap就需要做resize了,我們先假設線程已經resize完成, 而線程二必須等線程一完成再resize:

經過線程一resize後, 可以發現a b節點的順序被反轉了, 這時候我們來看線程二:

.1 線程二的開始點是只獲取到A節點, 還沒獲取他的next;

.2 這時候線程一resize完成, a.next = null; b.next = a; newTable[i] = b;

.3 線程二開始執行, 獲取A節點的next節點, a.next = null;

.4 接著執行 a.next = newTable[i]; 因為這時候newTable[i]已經是B節點了, 並且b.next = a; 那麼我們把newTablei賦值給a.next後, 就會線程a-b-a這樣的環形鏈表了, 也就是上圖的結果;

.5 因為第三步的a.next已經是null, 所以C節點就丟失了;

.6 那這時候來查位於1節點的數據D(其實不存在), 因為 d != a, 會接著查a.next, 也就是b; 但是b != d, 所以接著查b.next, 但是b.next還是a; 這就悲劇了, 在循環里出不去了;

這就是JDK7resize最大的缺陷, 會形成死循環;

那麼JDK8做了優化以後, 死循環的問題解除了嗎?

通過上圖我們發現JDK8的resize是讓節點的順序發生改變的, 也就是沒有倒排問題了;也是假設有兩個線程, 線程一已執行完成, 這時候線程二來執行:

.1 因為順序沒變, 所以node1.next還是node2, 只是node2.next從node3變成了null;

.2 而且JDK8是在遍歷完所有節點之後, 才對形成的兩個鏈表進行關聯table的, 所以不會像JAVA7一般形成A-B-A問題了;

.3 但是如果並發了, JAVA的HashMap還是沒有解決丟數據的問題, 但是不和JAVA7一般有數據倒排以及死循環的問題了;

HashMap設計時就是沒有保證線程安全的, 所以在多線程環境請使用ConcurrentHashMap;

以上就是本期分享的全部內容了, 如果對於HashMap::resize還有其他問題, 歡迎留言交流;

如果我的分享對你有幫助, 煩請點贊轉發, 感謝;

推薦閱讀：

相关文章