ConcurrentHashMap 解读（一）

一、核心思想

 1、锁分离技术：

ConcurrentHashMap首先将数据分成一段一段（segment）的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

 2、 final 关键字保证HashEntery 对象的不变性，来降低执行读操作的线程在遍历链表期间对加锁的需求：

ConcurrentHashMap完全允许多个读操作并发进行，读操作并不需要加锁。HashEntry 中的 key，hash，next 都声明为 final 型。这意味着，不能把节点添加到链接的中间和尾部，也不能在链接的中间和尾部删除节点。这个特性可以保证：在访问某个节点时，这个节点之后的链接不会被改变。这个特性可以大大降低处理链表时的复杂性。

同时，HashEntry 类的 value 域被声明为 Volatile 型， 保证其内存可见性。在 ConcurrentHashMap 中，不允许用 unll 作为键和值，当读线程读到某个 HashEntry 的 value 域的值为 null 时，便知道产生了冲突——发生了重排序现象，需要加锁后重新读入这个 value 值。这些特性互相配合，使得读线程即使在不加锁状态下，也能正确访问 ConcurrentHashMap。

 3、 Volatile 保证内存可见性：

由于内存可见性问题，未正确同步的情况下，写线程写入的值可能并不为后续的读线程可见，通过Volatile 变量可以保证其内存可见性问题。

 

二、类图

说明：

1、ConcurrentHashMap是由Segment数组结构组成。

 2、Segment是由HashEntry数组结构组成，并且Segment本身继承了可重入锁ReentrantLock，在ConcurrentHashMap里扮演锁的角色。

3、HashEntry是真正用于存储键值对数据的地方，HashEntry是一个链表结构。

三、 内部结构图：

 

 

 

说明：

一个ConcurrentHashMap里包含一个Segment数组，每一个Segment的结构和HashMap类似，是一种数组和链表结构， 一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素， 每个Segment守护者一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁。

 

ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作，第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部，因此，这一种结构的带来的副作用是Hash的过程要比普通的HashMap要长，但是带来的好处是写操作的时候可以只对元素所在的Segment进行加锁即可，不会影响到其他的Segment，这样，在最理想的情况下，ConcurrentHashMap可以最高同时支持Segment数量大小的写操作（刚好这些写操作都非常平均地分布在所有的Segment上），所以，通过这一种结构，ConcurrentHashMap的并发能力可以大大的提高。

四、核心代码解读

从上面的类图可以看到整个ConcurrentHashMap提供了非常丰富的方法，下面将对核心的方法进行解读，其他的未涉及的代码，均只是核心代码的变体而已。

1、初始化：

先看一下ConcurrentHashMap中提供的常量，这些常量部分是默认值，可通过初始化的参数覆盖，剩下部分是真正意义上的常量

 

	// 默认初始容量
    static final int DEFAULT_INITIAL_CAPACITY = 16;
 	// 默认增长因子，当 table 中包含元素的个数超过了 table 数组的长度与装载因子的乘积时，将进行一次扩容。
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
	// 默认的并发等级，即是并发数量。
    static final int DEFAULT_CONCURRENCY_LEVEL = 16;
	// 允许的最大容量，由于要求该值必须是2的指数，并且是int类型，所以1<<30是其能用的最大值。
    static final int MAXIMUM_CAPACITY = 1 << 30;
	// 默认每一个segment 的容量，必须是2的指数，至少为2， 否则分段锁失效。
    static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
	// 最大的 segment  数量，必须小于2的24次方，
    static final int MAX_SEGMENTS = 1 << 16; 
	// 在加锁前重试的次数
    static final int RETRIES_BEFORE_LOCK = 2;

 

接下去是真正需要初始化的变量，其中前三个是初始化的对象，会根据参数或者上面定义的常量来初始化，剩下三个其实是冗余的变量。都可以通过segment 数组得到。

 

	// segments的掩码值，也就是用来选择segments的key的hash值的高位
    final int segmentMask;
	// segments的偏移量
    final int segmentShift;
	// segments 数组
    final Segment<K,V>[] segments;

    transient Set<K> keySet;
    transient Set<Map.Entry<K,V>> entrySet;
    transient Collection<V> values;

 

  接下去就是初始化的代码了。。

    public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel) {
        if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        if (concurrencyLevel > MAX_SEGMENTS)
            concurrencyLevel = MAX_SEGMENTS;
        // Find power-of-two sizes best matching arguments
        int sshift = 0;
        int ssize = 1;
        while (ssize < concurrencyLevel) {
            ++sshift;
            ssize <<= 1;
        }
        this.segmentShift = 32 - sshift;
        this.segmentMask = ssize - 1;
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        int c = initialCapacity / ssize;
        if (c * ssize < initialCapacity)
            ++c;
        int cap = MIN_SEGMENT_TABLE_CAPACITY;
        while (cap < c)
            cap <<= 1;
        // create segments and segments[0]
        Segment<K,V> s0 =
            new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
                             (HashEntry<K,V>[])new HashEntry[cap]);
        Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
        UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
        this.segments = ss;
    }

 

可以看初始化方法是通过initialCapacity，loadFactor, concurrencyLevel三个参数来初始化segments数组，segment偏移量segmentShift，segment掩码segmentMask和每个segment里的HashEntry数组，当然这是哪个参数都有对应的默认值，所以可以缺少任意一个。

 

• ssize：也就是segments数组的大小，取值为大于或等于concurrencyLevel的最小的2的N次方值。为了保证并发数量为concurrencyLevel，所以必须大于等于concurrencyLevel，为什么必须2的N次方在后面解释。注意concurrencyLevel的最大值是1<<16，意味着ssize最大为1<<16。
• segmentShift：segmentShift变量在定位segment时的哈希算法里需要使用，取值为32-（ssize从1向左移位的次数）。

• segmentMask：segmentMask变量在定位segment时的哈希算法里需要使用，是哈希运算的掩码，取值为ssize-1。

接下去先解释一下这三个数据的关系，也回答上面ssize为什么必须是2的N次方问题：这个要结合怎么去定位segment来说。先看定位segment代码，其中h表示key的hash值，为int类型，最大32位。

 

((h >>> segmentShift) & segmentMask)

 

假设ssize=2的k次方。那么segmentShift=32-k,segmentMask=（2的k次方-1）;它们有什么关系呢？

h>>> segmentShift,就表示保留h的高k位的值。segmentMask=（2的k次方-1) 就意味segmentMask是由k位1组成的数，两者做&运算，结果便是segment数组的下标。当h的高K位全部为1的时候，运算结果最大=segmentMask=2的k次方-1。而segment数组的最大长度，为ssize=2的k次方，那么下标的最大值为2的k次方-1。是完全可以对应起来的。。到这里初始化了Segment的数组。接下去是初始化第一个Segment。

 

• cap ：表示一个Segment中HashEntry数组的大小。取值为大于或等于将最大容量平均到每一个Segment里面时，单个Segment最小需要包含值数量的最小的2的N次方值。
• ConcurrentLevel一经指定，不可改变，后续如果ConcurrentHashMap的元素数量增加导致ConrruentHashMap需要扩容，ConcurrentHashMap不会增加Segment的数量，而只会增加Segment中链表数组的容量大小，这样的好处是扩容过程不需要对整个ConcurrentHashMap做rehash，而只需要对Segment里面的元素做一次rehash就可以了。

未完待续。。

 

 

 

 

参考文献

http://www.infoq.com/cn/articles/ConcurrentHashMap

http://www.ibm.com/developerworks/cn/java/java-lo-concurrenthashmap/index.html?ca=drs-

http://www.goldendoc.org/2011/06/juc_concurrenthashmap/

 

 

本站支持 pay for your wishes