探究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为例，演示计算过程：