探究ConcurrentHashMap中键值对在Segment[]的下标如何确定
本文对jdk1.7下使用segmentshift和segmentmask求解concurrenthashmap键值对在segment[]中的下标值进行了探究和论证。
适合人群
java进阶
说明
推荐阅读
正文
下面先查看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为例,演示计算过程: