JDK1.8關于HashMap擴容時的resize()方法中(e.hash & oldCap) == 0算法講解

為了弄懂"(e.hash & oldCap) == 0"這個判斷條件，看了好多部落客的講解，可能是說的太專業了，又是二進制又是位移的，搞得我一頭霧水，經過一晚的沉澱，早上突然醒悟！其實非常簡單，其實就是一個國小三年級的等式問題！

簡單看一下源碼

省略...
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;
}
           

首先要了解的是計算數組下标的算法

(n - 1) & hash
           

n代表數組的長度，hash代表hash(key) 你懂得…

衆所周知，HashMap每次擴容原長度的二倍

也就是"newCap = 2*oldCap"

重點來了！！！！！！！！

一、為什麼擴容時要有"(e.hash & oldCap) == 0"這個判斷條件呢？

HashMap在擴容時，需要先建立一個新數組,然後再将舊數組中的資料轉移到新數組上來

此時，舊數組上的資料就會根據(e.hash & oldCap) 是否等于0這個算法,被很巧妙地分為2類:

① 等于0時，則将該頭節點放到新數組時的索引位置等于其在舊數組時的索引位置

② 不等于0時,則将該頭節點放到新數組時的索引位置等于其在舊數組時的索引位置再加上舊數組長度

二、為什麼是"(e.hash & oldCap) == 0"這個判斷條件呢？

為了滿足該節點的資料在新舊數組中的下标相同

三、如何滿足的呢？

套入公式=》   (oldCap - 1) * e.hash = (2 * oldCap - 1) * e.hash;
分解因式=》    oldCap * e.hash - e.hash = 2 * oldCap * e.hash - e.hash;
化簡=》       oldCap * e.hash = 2 * oldCap * e.hash;
結果=》       oldCap * e.hash = 0;
           

這不就出來了！！！！！！！

僅供參考，職場小白，不喜勿噴。

如果對你有幫助記得點贊哦！！！！！！！！！