Concurrenthashmap

发表于 | 分类于 | 阅读次数

大家都知道Java集合框架中，hashmap是非线程安全的，在并发环境下会出现错误情况，具体的原因分析参考：Hashmap线程安全性。Java也提供了相应的线程安全类，如Hashtable、ConcurrentHashMap等。下面介绍一下ConcurrentHashmap（JDK1.7为例）。

首先Hashtable也是线程安全的，通过分析源码发现hashtable是通过synchronized同步了整个hash表，只允许一个线程对hashtable进行读写，所以并发时造成多个线程等待效率较低。而ConcurrentHashMap允许多个线程并发操作，其关键在于使用了锁分离技术，它使用了多个锁来控制对hash表的不同部分进行的修改。ConcurrentHashMap内部使用段(Segment)来表示这些不同的部分，每个段其实就是一个小的hashtable，它们有自己的锁。只要多个修改操作发生在不同的段上，它们就可以并发进行。对于有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。

结构

JDK1.7版本中ConcurrentHashmap的结构如下：
img
由上图可以看出，ConcurrentHashmap是整个hash表，它由多个（默认16个）segment组成，相当于一个hashtable，hashentry是链表一个节点。下面看一下主要的源代码：

1
2
3
4
5
public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>  implements ConcurrentMap<K, V>, Serializable {
    final int segmentMask;
    final int segmentShift;
    final Segment<K,V>[] segments;
}

这表明ConcurrentHashmap的segment是不可变的，扩容只能增加segment的大小，其数量不会发生变化。segment的源码如下：

1
2
3
4
5
6
7
8
static final class Segment<K,V> extends ReentrantLock implements Serializable {
    private static final long serialVersionUID = 2249069246763182397L;
    transient volatile int count;
    transient int modCount;
    transient int threshold;
    transient volatile HashEntry<K,V>[] table;
    final float loadFactor;
}

HashEntry是volatile，则其修改对于其他线程是可见的，hashentry源码如下：

1
2
3
4
5
6
static final class HashEntry<K,V>{
	final K key;
	final int hash;
	volatile V value; 
	final HashEntry<K,V> next;
}

除了value不是final的，其它值都是final的，所以不能从hash链的中间或尾部添加或删除节点，为了确保读操作能够看到最新的值，将value设置成volatile，这避免了加锁。
ConcurrentHashmap这种设计，保证读取操作能够读取到几乎最新的修改，所以读操作大多数情况了不需要加锁。

Remove

下面首先看一下remove操作：

1
2
3
4
5
public V remove(Object key) {
    hash = hash(key.hashCode());
    return segmentFor(hash).remove(key, hash, null);
}

整个操作是先定位到段，然后委托给段的remove操作。当多个删除操作并发进行时，只要它们所在的段不相同，它们就可以同时进行。下面是Segment的remove方法实现：
img
整个操作是在持有segment锁的情况下执行的，先定为代需要删除的节点e，然后将e前面的节点都复制一遍，因为entry是不可变的，所以必须要复制前面的节点，这种不可变性使得不需要同步从而节省了时间。例如删除前的数据为：1、2、3、4，删除3后链表变为：2、1、4。 整个remove实现并不复杂，但是需要注意如下几点。第一，当要删除的结点存在时，删除的最后一步操作要将count的值减一。这必须是最后一步操作，否则读取操作可能看不到之前对段所做的结构性修改。第二，remove执行的开始就将table赋给一个局部变量tab，这是因为table是 volatile变量，读写volatile变量的开销很大。编译器也不能对volatile变量的读写做任何优化，直接多次访问非volatile实例变量没有多大影响，编译器会做相应优化。

Put

接下来看一下put操作：
img
修改数据是不能并发进行的，所以该方法也是在持有segment锁的情况下执行，然后判断是否超限确保容量不足时能够rehash。接着是找是否存在同样一个key的结点，如果存在就直接替换这个结点的值。否则创建一个新的结点并添加到hash链的头部，这时一定要修改modCount和count的值，同样修改count的值一定要放在最后一步。put方法调用了rehash方法，reash方法实现得也很精巧，主要利用了table的大小为2^n。

Get

然后看一下get操作：
img
get操作不需要锁。第一步是访问count变量，这是一个volatile变量，由于所有的修改操作在进行结构修改时都会在最后一步写count 变量，通过这种机制保证get操作能够得到几乎最新的结构更新。对于非结构更新，也就是结点值的改变，由于HashEntry的value变量是 volatile的，也能保证读取到最新的值。接下来就是根据hash和key对hash链进行遍历找到要获取的结点，对hash链进行遍历不需要加锁的原因在于链指针next是final的。但是头指针却不是final的，这是通过getFirst(hash)方法返回，也就是存在 table数组中的值。这使得getFirst(hash)可能返回过时的头结点，例如，当执行get方法时，刚执行完getFirst(hash)之后，另一个线程执行了删除操作并更新头结点，这就导致get方法中返回的头结点不是最新的。这是可以允许，通过对count变量的协调机制，get能读取到几乎最新的数据，虽然可能不是最新的。要得到最新的数据，只有采用完全的同步。
最后，如果找到了所求的结点，判断它的值如果非空就直接返回，否则在有锁的状态下再读一次。因为put操作的语句：tab[index] = new HashEntry<K,V>(key, hash, first, value)，在这条语句中，HashEntry构造函数中对value的赋值以及对tab[index]的赋值可能被重新排序，这就可能导致结点的值为空，所以可能需要在加锁情况在在读一遍：
img
contains方法更简单了，他不需要读值，所以不需要加锁了。

Size

最后看一下size（）操作：
img
size方法主要思路是先在没有锁的情况下对所有段大小求和，如果不能成功（这是因为遍历过程中可能有其它线程正在对已经遍历过的段进行结构性更新），最多执行RETRIES_BEFORE_LOCK次，如果还不成功就在持有所有段锁的情况下再对所有段大小求和。在没有锁的情况下主要是利用Segment中的modCount进行检测，在遍历过程中保存每个Segment的modCount，遍历完成之后再检测每个Segment的modCount有没有改变，如果有改变表示有其它线程正在对Segment进行结构性并发更新，需要重新计算。

总结

ConcurrentHashmap主要的方法大概这么多，其同步的方法在于使用了分段锁、final、volatile等减少了同步的范围，并保证了可见行。它的实现也比较复杂，需要多多思考和理解。

谢谢大佬的打赏!