ConcurrentHashMap源码剖析

如果有任何人想研究和学习ConcurrentHashMap的源码,强烈建议先把HashMap的源码研究透。因为本质上都是HashMap。如果把HashMap源码搞清楚以后,再学习ConcurerntHashMap的时候,会发现有很多相同的地方。

其实说到为什么会有ConcurrentHashMap,看其名字,是用于并发的。那么用HashMap就不行?我们知道HashMap是非线程安全的。借助一些外部的手段也不是不行,比如在是用put方法时候,在调用的方法上加上synchronized关键字。问题是这样做会锁住HashMap里的hash table,跟直接用HashTable类没有太大的区别。而ConcurrentHashMap使用锁分段,允许多个修改动作并发进行。具体点,使用多个锁控制对hash表的不同部分进行修改。内部使用Segment来表示这些不同的部分,每个Segment其实就是一个小的hash table,它们有各自的锁,只要修改操作发生在不同的Segment上,就可以并发进行。描述了这么多,看看ConcurrentHashMap的结构是什么样子。

结构和类图:

concurrentHashMapConcurrentHashMap class

初始化ConcurrentHashMap都做了什么?

对比HashMap,ConcurrentHashMap多了一个Segment的概念。即使在没开始研究其源码,也可能会想到的一点是,Segment是怎么设计的,怎么控制各自的hash table?如果了解HashMap的构造函数,知道有两个参数初始容量(initialCapacity)和负载因子(loadFactor),那么对ConcurrentHashMap来说,除了这两个参数,多了一个参数CurrencyLevel。而这个参数用来计算出Segments数组的长度。
ConcurrentHashMap构造方法里几个重要的变量,一个是ssize,可以看出是Segments数组的长度。如果在构造ConcurrentHashMap的时候没有指定CurrencyLevel,则默认值是16.那么根据下面的代码,ssize计算出来就是16.这个计算跟在HashMap里计算hash table的capacity是一样的,总是2的n次方。

static final int DEFAULT_CONCURRENCY_LEVEL = 16;
static final int MAX_SEGMENTS = 1 << 16;
int ssize = 1;
while (ssize < concurrencyLevel) {
 ++sshift;
 ssize <<= 1;
}

其实Segment数组有多少个元素,我们可以理解成有多少把锁。既然锁的个数计算出来,那么每个锁会管理的hash table的capacity有多大呢?看下面代码:

static final int DEFAULT_INITIAL_CAPACITY = 16;
 int c = initialCapacity / ssize;
 if (c * ssize < initialCapacity)
   ++c;
 int cap = 1;
 while (cap < c)
   cap <<= 1;

上面代码是计算每个Segment对应的hash table的capacity。举个例子加深理解。假设Segments数组长度是16,也就是ssize是16. initialCapacity在构造ConcurrentHashMap时指定为31. 变量c首先计算为1(initialCapacity / ssize),经过if判断之后,c会变为2. 之所以要有这一步的原因是在上一步计算c的时候,因为c是int型,所以小数点位都会被舍弃掉。而如果不经过if这一步,有可能会造成总的容量不够。while循环之后,cap也是2. 因为有16个Segment,所以总的容量就是32.
在知道Segment数组长度,每个Segment管理的Hash Table的容量后,剩下就比较容易,直接通过循环把Segment数组构造出来:

for (int i = 0; i < this.segments.length; ++i)
  this.segments[i] = new Segment<K,V>(cap, loadFactor);

put操作

public V put(K key, V value) {
   if (value == null)
     throw new NullPointerException();
   int hash = hash(key.hashCode());
   return segmentFor(hash).put(key, hash, value, false);
 }
final Segment<K,V> segmentFor(int hash) {
    return segments[(hash >>> segmentShift) & segmentMask];
}

put方法对比HashMap多了一个首先找segment的步骤。找到segment以后,调用其put方法将元素插入。这里如果读者研究过HashMap的源码,可能会有一个疑问,为什么在put的时候,key和value不能是空的。关于这个问题,ConcurrentHashMap的作者Doug Lea在回答一个网友的问题的时候给出了解释,详细看这里,大概的意思是说,如果这样做,可能会引起歧义。主要的问题是如果map.get(key)返回null,你不能确定这个key本来就是null还是这个key在map里本身是不存在的而没有找到。在一个非并发(non-concurrent)的map,可以通过map.containsKey(key)来检查,但是在一个并发的map,这个map可能在这两次call中已经改变。
看看Segment里的put方法:

V put(K key, int hash, V value, boolean onlyIfAbsent) {
    lock();
    try {
        int c = count;
        if (c++ > threshold) // ensure capacity
            rehash();
        HashEntry<K,V>[] tab = table;
        int index = hash & (tab.length - 1);
        HashEntry<K,V> first = tab[index];
        HashEntry<K,V> e = first;
        while (e != null && (e.hash != hash || !key.equals(e.key)))
            e = e.next;
        V oldValue;
        if (e != null) {
            oldValue = e.value;
            if (!onlyIfAbsent)
                e.value = value;
        }
        else {
            oldValue = null;
            ++modCount;
            tab[index] = new HashEntry<K,V>(key, hash, first, value);
            count = c; // write-volatile
        }
        return oldValue;
    } finally {
        unlock();
    }
}

首先需要知道的是Segment继承了ReentrantLock,所以在上面put方法开始的时候,先获取锁,最后在finally里解锁,这个其实是ReentrantLock典型的使用方法。这也从另外一个方面说明ConcurrentHashMap不是没有锁,只是锁分离而已。其它的代码如果在熟悉HashMap的基础上就很好理解了。无非是如果key已经存在,则直接把旧值替换成新值,并把旧值返回。如果key在map里不存在,则根据key和value生成一个新的HashEntry,放到hash table里。注意,新插入的元素总是在链表的顶部。问题来了,如果可能的话,是否可以在中间或者尾部插入呢,答案是否定的,因为链表里的每一个元素都有一个next指针,指向下一个元素,在HashEntry的设计里,next被设计成final。一旦链表形成,你想中间插入一个元素,必须改变插入位置的前一个元素的next指针,让它指向自己,这个在当前的设计是做不到。也许有人会想到另外一个问题,对put来说,可以一直把新加入的元素放在链表的顶部,那么如果要移除链表中间的一个元素,那不是也会有这个问题?针对这个问题,会在分析remove方法给出答案。

static final class HashEntry<K,V> {
 final K key;
 final int hash;
 volatile V value;
 final HashEntry<K,V> next;

remove操作
从map移除一个元素的过程跟put操作大同小异,无非是先根据key的hash值经过一个hash方法算出一个新的hash值,再根据这个新的hash值计算出这个元素属于某个segment,最后调用Segment的remove方法从hash table里移除这个元素,当然,也存在没有这个key的可能。整个操作过程,也put方法一样,需要有加解锁的操作。
在上面分析put方法时,我们还留下一个问题,因为HashEntry的next指针使用final关键子修饰,那么如果在链表的中间一个位置移除一个元素,剩下的元素怎么重新形成一个新的链表?没有办法的办法,实现起来也简单,那就是把这个链表上的每一个元素重新clone出一个新的对象,组成一个全新的链表。这中做法从设计上讲不是很好,因为如果删除的元素较多,而且链表很长的话,性能上总是有损耗。注意这个是JDK 6的设计,JDK 7已经做了改进,比如修饰HashEntry的next指针的final关键字被去掉。

V remove(Object key, int hash, Object value) {
    lock();
    try {
                //限于篇幅考虑,略掉一些源码
                ++modCount;
                HashEntry<K,V> newFirst = e.next;
                for (HashEntry<K,V> p = first; p != e; p = p.next)
                    newFirst = new HashEntry<K,V>(p.key, p.hash,
                                                  newFirst, p.value);
                tab[index] = newFirst;
                count = c; // write-volatile
            }
        }
        return oldValue;
    } finally {
        unlock();
    }
}

get操作

V readValueUnderLock(HashEntry<K,V> e) {
    lock();
    try {
        return e.value;
    } finally {
        unlock();
    }
}
V get(Object key, int hash) {
    if (count != 0) { // read-volatile
        HashEntry<K,V> e = getFirst(hash);
        while (e != null) {
            if (e.hash == hash && key.equals(e.key)) {
                V v = e.value;
                if (v != null)
                    return v;
                return readValueUnderLock(e); // recheck
            }
            e = e.next;
        }
    }
    return null;
}

代码本身没有什么好过多分析的。还是提几个问题,第一为什么整个读的过程不需要加锁,第二,读到空值,会加锁重读。但是为什么会读到空值,既然put的时候已经做了限制,不允许空的key和value。
先看第一个问题。原因就是get操作使用的共享变量都被定义成volatile,比如用于统计当前segment里元素个数的count和HashEntry的value。定义成volatile用于在线程中保持可见性。能够被多线程同时读并且保证不会读到过期的值,在get操作里只需要读不需要写共享变量count和value,所以可以不用加锁。之所以不会读到过期的值,是根据java内存模型的happen before原则,对volatile字段的写入操作先于读操作,即使两个线程同时修改和获取volatile变量,get操作也能拿到最新的值,这是用volatile替换锁的经典应用场景。
对第二个问题,我个人觉得比较难以理解,估计很多人看到这里应该有同样的疑问。google了一下,果然有人问到这个问题,貌似Doug Lea也做了回复。具体看这里。下面贴出网友问的问题和Doug Lea的回复:
Q:
In the ConcurrentHashMap the get method does not require “readValueUnderLock” because a racing remove does not make the value null. The value never becomes null on the from the removing thread. this means it is possible for get to return a value for key even if the removing thread (on the same key) has progressed till the point of cloning the preceding parts of the list. This is fine so long as it is the desired effect.

But this means “readValueUnderLock” is not required for NEW memory model.

However for the OLD memory model a put may see the value null due to reordering(Rare but possible).

Is my understanding correct.

A:

Not quite. You are right that it should never be called. However, the JLS/JMM can be read as not absolutely forbidding it from being called because of weaknesses in required ordering relationships among finals vs volatiles set in constructors (key is final, value is volatile), wrt the reads by threads using the entry objects. (In JMM-ese, ordering constraints for finals fall outside of the synchronizes-with relation.) That’s the issue the doc comment (pasted below) refers to. No one has ever thought of any practical loophole that a processor/compiler might find to produce a null value read, and it may be provable that none exist (and perhaps someday a JLS/JMM revision will fill in gaps to clarify this), but Bill Pugh once suggested we put this in anyway just for the sake of being conservatively pedantically correct. In retrospect, I’m not so sure this was a good idea, since it leads people to come up with exotic theories.

为不愿意看英文的同学简单解释一下上面这两段话。上面一个网友的问题里提到,使用锁去读取value是不需要的,因为一个竞争的remove操作不会使value为空。对新的内存模型来说,readValueUnderLock是不需要的,但是对于旧的内存模型,因为重排,put也许会看到null值。Doug Lea不是完全赞同这个说法,所以就有了上面第二段话。具体跟JMM有关。各位同学可以自行理解,有一点需要说明的是Doug Lea也不确定null值的情况一定会发生,所以上面说到Bill Pugh曾经建议把readValueUnderLock放在这里,但是Doug Lea也不确定这个是不是一个好的主意。我个人觉得从研究源码的角度,没必要在这点上一直纠结下去,花一些时间在JMM(Java Memory Model)上对于理解并发编程有很大的帮助。

size操作

如果我们要统计整个ConcurrentHashMap里元素的大小,就必须统计所有Segment里元素的大小后求和。Segment里的全局变量count是一个volatile变量,那么在多线程场景下,我们是不是直接把所有Segment的count相加就可以得到整个ConcurrentHashMap大小了呢?不是的,虽然相加时可以获取每个Segment的count的最新值,但是拿到之后可能累加前使用的count发生了变化,那么统计结果就不准了。所以最安全的做法,是在统计size的时候把所有Segment的put,remove和clean方法全部锁住,但是这种做法显然非常低效。

因为在累加count操作过程中,之前累加过的count发生变化的几率非常小,所以ConcurrentHashMap的做法是先尝试2次通过不锁住Segment的方式来统计各个Segment大小,如果统计的过程中,容器的count发生了变化,则再采用加锁的方式来统计所有Segment的大小。

那么ConcurrentHashMap是如何判断在统计的时候容器是否发生了变化呢?使用modCount变量,在put , remove和clean方法里操作元素前都会将变量modCount进行加1,那么在统计size前后比较modCount是否发生变化,从而得知容器的大小是否发生变化。

后话

即使有HashMap源码研究的基础,ConcurrentHashMap的源码研究也着实不易,因为里面包含的知识点太多了,而且有的如果想了解,需要挖的很深。另外在研究ConcurrentHashMap之前,个人还纠结于JDK的版本,因为ConcurrentHashMap在JDK 7有了一些改进。正常情况下,总是应该以最新 版本的源码为研究目标,但是我个人觉得,如果能有个从低版本到高版本的视角,看看同一个类在不同JDK版本是如何改进的,改进后面的有着什么意义,可能会使源码分析研究的价值会增大。出于这个目的,本文是对JDK 6的ConcurrentHashMap做的分析。后续看看找个时间对比一下ConcurrentHashMap在JDK 6和JDK 7上的一些不同的实现及改进。

发表评论

电子邮件地址不会被公开。 必填项已用*标注