JUC1.8-ConcurrentHashMapソースコード学習-なぜ拡張するたびに2倍になるのですか?

前言

この问题は拡容の中の1つの残した问题で、前因と后果はみんなが前のブログJUC 1を调べることができます.8-ConcurrentHashMapソース学習-拡張方法解析transfer()は、拡張メカニズムを話すときに、編幅が長すぎるため、単独で説明する.
ソースコードを読んだり、筆者が拡張したブログを読んだりすると、拡張するたびに元の容器の2倍に拡大し、transfer()ソースコードの中の位置を貼っていることがわかります.

if (nextTab == null) {            //  
        try {
            //n << 1  2 * n  2 n
            @SuppressWarnings("unchecked")
            Node[] nt = (Node[])new Node,?>[n << 1];
            nextTab = nt;
        } catch (Throwable ex) {      //  , OOM
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        // 2 node , 
        nextTable = nextTab;
        // , n  
        transferIndex = n;
    }

Node[] nt = (Node[])new Node,?>[n << 1]; コードにも注記したが、nは元の長さを表す左に1ビットシフトし、2*nに相当し、分からない場合はJUC 1を調べることができる.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

    
     

 ：

0
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でトップが1位高いことが分かったので,元のノードを離れると,新しい位置はちょうど元の下付き+元tab長=3+8=11である.
phoneの和7演算結果は0011,15演算結果は0011でトップは変化せず,soはすべて下付き値を変化させなかった.
これが2倍のメリットです.
当初容量は8,8−1=7,7のバイナリは111であった.現在の容量は16,16−1=15,15のバイナリは1111である
彼らはすべて1の形態なので、倍に拡大すると高位に1を加えただけなので、約半分のkeyが元のスペースに残り、半分のkeyが同じ別のスペースに、例えば3番の位置から11番の位置にあるので、コピーしやすいです.ビット演算により、モード演算の代わりに!

まとめ

まとめてみると、2倍拡大=n<<1は元の長さの左シフト1位、すなわち高位プラス1に相当するので、演算を行う際には、同じチェーンテーブルの下のkeyにも高位プラス1が加えられていれば、このノードの対応するtabの下標にも延長の長さを加えなければならないことを説明し、通称高位バケツと呼ばれ、いずれにしても0は高位に変化がないことを説明し、通称低位バケツと呼ばれ、元の位置に置いて動かなければならない.だから拡張する時、int runBit=fh&n;高位に属するか低位に属するかを得るために用いられ、低位下標が変わらなければ、否定者下標が直接加えればよいので、新しい容器の取余計算を再計算する必要はない.