探究ConcurrentHashMap中鍵值對在Segment[]的下標如何確定

內容

 　　本文對JDK1.7下使用segmentShift和segmentMask求解ConcurrentHashMap鍵值對在Segment[]中的下標值進行了探究和論證。

適合人群

 ​　　Java進階

說明

 　　轉載請註明出處，尊重筆者的勞動成果。

 推薦閱讀

 　　探究HashMap線性不安全（二）——鏈表成環的詳細過程

 正文

 　　下麵先查看ConcurrentHashMap源碼中的put操作，找到segment[]的下標j的計算公式。

 1 @SuppressWarnings("unchecked")
 2 public V put(K key, V value) {
 3     Segment<K,V> s;
 4     if (value == null)
 5         throw new NullPointerException();
 6     int hash = hash(key);
 7     //key對應的segment[]的下標j的計算公式
 8     int j = (hash >>> segmentShift) & segmentMask;
 9     if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
10          (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
11         s = ensureSegment(j);
12     return s.put(key, hash, value, false);
13 }

　　由上面的ConcurrentHashMap源碼可知，一個鍵值對在Segment數組中下標j的計算公式為：

j = (hash >>> segmentShift) & segmentMask

　　公式雖然不長，但是它包含了2個“晦澀難懂”的參數：segmentShift和segmentMask ，讓人費解。下麵筆者用一種通俗簡單的方式來解釋該公式的含義。

　　首先，閱讀ConcurrentHashMap的構造方法，重點查看註釋區域，其中包含了segmentShift和segmentMask的定義：

segmentShift = 32 - sshift;segmentMask = ssize - 1;

　　以及segment數組長度ssize與sshift的關係：

2^sshif=ssize

　　ConcurrentHashMap的構造方法

 1 public ConcurrentHashMap(int initialCapacity,
 2                                float loadFactor, int concurrencyLevel) {
 3           if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
 4               throw new IllegalArgumentException();
 5           if (concurrencyLevel > MAX_SEGMENTS)
 6               concurrencyLevel = MAX_SEGMENTS;
 7          int sshift = 0;
 8          int ssize = 1;
 9      //2^sshif=ssize，例:sshift=4,ssize=16;
10    //根據concurrentLevel計算得出ssize為segments數組長度
11          while (ssize < concurrencyLevel) {
12              ++sshift;
13              ssize <<= 1;
14          }
15          //segmentShift和segmentMask的定義
16          this.segmentShift = 32 - sshift;
17          this.segmentMask = ssize - 1;
18          if (initialCapacity > MAXIMUM_CAPACITY)
19              initialCapacity = MAXIMUM_CAPACITY;
20          //計算cap的大小，即Segment中HashEntry的數組長度，cap也一定為2的n次方.
21          int c = initialCapacity / ssize;
22          if (c * ssize < initialCapacity)
23              ++c;
24          int cap = MIN_SEGMENT_TABLE_CAPACITY;
25          while (cap < c)
26              cap <<= 1;
27          //創建segments數組並初始化第一個Segment，其餘的Segment延遲初始化
28          Segment<K,V> s0 =
29              new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
30                              (HashEntry<K,V>[])new HashEntry[cap]);
31          Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
32          UNSAFE.putOrderedObject(ss, SBASE, s0); 
33          this.segments = ss;
34      }

 　　由此可知，求key散列到長度為ssize的Segment數組的下標j，必定有下標j的值域為[0，ssize-1]。由於ssize=2^sshif，那麼小標j可以用1個sshift位的二進位數字表示。假如：ssize為16，那麼sshift=4，j的值域為[0,15]，而[0000b,1111b]就是j的值域；則求key在Segment[]的下標j，就是求key對應的一個散列的4位二進位數值。而ConcurrentHashMap的源碼求下標j的方式非常簡單，就是取key的hash值的高4位。因此，求key散列到長度為ssize的Segment數組的下標j，就是求key的hash值的高sshift位。

　　故有，j=(key.hash>>>(32-sshift))&(ssize-1)。而由源碼可知，segmentShift = 32 - sshift，segmentMask = ssize - 1。即：

j=(key.hash>>>(32-sshift))&(ssize-1)=(key.hash>>>segmentShift )&segmentMask。（其中>>>表示無符號右移，空位補0）

　　以ssize為16為例，演示計算過程：