JUC1.8-ConcurrentHashMap源碼學習-為什麼每次擴容是原來兩倍？

前言

這個問題是擴容裡面的一個遺留問題，前因後果大家可以去查閱上篇部落格JUC1.8-ConcurrentHashMap源碼學習-擴容方法解析transfer() ，在講擴容機制時，篇幅過長，是以單獨拿出來說明；

大家看過源碼或者是讀過筆者擴容那篇部落格，就知道在每次擴容時，均在原容器的基礎上，擴大2倍，貼下transfer（）源碼裡面的位置：

if (nextTab == null) {            // 開始初始化
        try {
            //n << 1 相當于2 * n 也就是2倍的n
            @SuppressWarnings("unchecked")
            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
            nextTab = nt;
        } catch (Throwable ex) {      // 防止記憶體不夠,出現OOM
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        //将生産好的2倍node數組,更新到成員變量
        nextTable = nextTab;
        //更新轉移下标, n 就是老桶的長度
        transferIndex = n;
    }
           

Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1]; 在代碼也注釋了，n代表原長度 左移1位，相當于2 * n， 不明白的可以查閱JUC1.8-ConcurrentHashMap源碼學習-準備中的Java位運算部分。 so這篇我們就好好分析分析。

當筆者在遇到這種 莫名的關系時，我都會采用具體數字代入的方式，先找到有木有啥有規律的規則，然後 在關聯該方法上下文進行分析，那麼我就先帶着大家用資料代入的方式看下：

總所周知的:在往容器put資料時，都得根據目前key值得hashcode取餘n，然後找到對應的tab的下标位置，那麼也可能發生hash碰撞後，就通過連結清單，或者紅黑樹将新的key放到舊的key後面。 例如：

現有key： “name”,“age”,“email”,“phone”，目前的哈希表容量是8

1. 通過java的hashCode() 函數可以計算出哈希碼
    
    2. 計算對應tab的下标 ， （n-1） & hash 
     “name”字元串的哈希碼是3373707（十進制），1100110111101010001011（二進制） & 00000111 = 0011，下标：3
     
     “phone”字元串的哈希碼是194811（十進制），101111100011110011（二進制）& 00000111 = 0011，下标：3

     “age”字元串的哈希碼是96511（十進制），       10111100011111111（二進制）& 00000111 = 0111，下标：7
     
     “email”字元串的哈希碼是96619420（十進制），101110000100100101110011100（二進制）& 00000111 = 0100，下标：4

    
     

是以目前對應的結構是：
           

1	2	3	4	5	6	7
name	email	age
phone

3.此時來擴容，n << 1 新tab 長度就是16，
重新再來計算新的下标，這裡就拿name和phone為例：

    “name”字元串的哈希碼是3373707（十進制），1100110111101010001011 & 00001111 = 1011，下标：11
     
    “phone”字元串的哈希碼是194811（十進制），101111100011110011 & 00001111 = 0011，下标：3
           

從這就可以看出來，

name的與7運算結果 是 0011 ，與15運算結果是1011 發現首位高一位，是以離開原有的節點， 那麼新的位置 正好就是 原下标 + 原tab長度 = 3 + 8 = 11；

phone的與7運算結果 是 0011 ，與15運算結果是0011 發現首位沒有變化，so所有并沒變化下标值。

這就是擴大一倍的好處：

當初容量是8，8-1=7，7的二進制是111；

現在容量是16，16-1=15，15的二進制是1111

因為他們都是全為1的形态，而擴大一倍後隻是高位加了一個1，是以會留有大概一半的key在原來的空格，而有一半的key到相同的别的空格中，比如都是從3号位置到了11号位置中，這樣也便于複制。通過位運算，代替了模運算！

總結

總結下：擴大2倍 = n<<1 也就相當于原長度的左移一位，也就是高位加了1， 那麼在去做與運算時，在同一個連結清單的下面的key，如果高位也加1了，說明這個節點的對應的tab的下标也得跟着加上擴長的長度，俗稱高位桶， 反正還是為0說明高位沒有變化，俗稱低位桶，放在原位置不動即可。 是以在擴容的時候，int runBit = fh & n; 用于來得到屬于高位還是低位， 如果是低位下标不變，否者下标直接加就好了，就不用在重新計算新容器的取餘計算了。