探究ConcurrentHashMap中键值对在Segment[]的下标如何确定-白红宇

探究ConcurrentHashMap中键值对在Segment[]的下标如何确定

阅读量：7092 次

发布时间：2019-06-28

本文共 3248 字，大约阅读时间需要 10 分钟。

内容

　　本文对JDK1.7下使用segmentShift和segmentMask求解ConcurrentHashMap键值对在Segment[]中的下标值进行了探究和论证。

适合人群

　　Java进阶

说明

推荐阅读

正文

　　下面先查看ConcurrentHashMap源码中的put操作，找到segment[]的下标j的计算公式。

1 @SuppressWarnings("unchecked") 2 public V put(K key, V value) { 3     Segment
     
       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
      
       )UNSAFE.getObject          // nonvolatile; recheck10          (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment11         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
     
       s0 =29              new Segment
      
       (loadFactor, (int)(cap * loadFactor),30                              (HashEntry
       
        [])new HashEntry[cap]);31          Segment
        
         [] ss = (Segment
         
          [])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为例，演示计算过程：

转载于:https://www.cnblogs.com/lonelyJay/p/9736027.html

你可能感兴趣的文章