内容
本文对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的关系：
- 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为例，演示计算过程：
经验首页