媒介

以前写过先容HashMap的文章，文中提到过HashMap在put的时候，插入的元素高出了容量（由负载因子抉择）的范畴就会触发扩容操纵，就是rehash，这个会从头将原数组的内容从头hash到新的扩容数组中，在多线程的情况下，存在同时其他的元素也在举办put操纵，假如hash值沟通，大概呈现同时在同一数组下用链表暗示，造成闭环，导致在get时会呈现死轮回，所以HashMap是线程不安详的。

我们来相识另一个键值存储荟萃HashTable，它是线程安详的，它在所有涉及到多线程操纵的都加上了synchronized要害字来锁住整个table，这就意味着所有的线程都在竞争一把锁，在多线程的情况下，它是安详的，可是无疑是效率低下的。

其实HashTable有许多的优化空间，锁住整个table这么粗暴的要领可以变相的柔和点，好比在多线程的情况下，对差异的数据集举办操纵时其实基础就不需要去竞争一个锁，因为他们差异hash值，不会因为rehash造成线程不安详，所以互不影响，这就是锁疏散技能，将锁的粒度低落，操作多个锁来节制多个小的table，这就是这篇文章的主角ConcurrentHashMap JDK1.7版本的焦点思想。

ConcurrentHashMap

JDK1.7的实现

在JDK1.7版本中，ConcurrentHashMap的数据布局是由一个Segment数组和多个HashEntry构成，如下图所示：

Segment数组的意义就是将一个大的table支解成多个小的table来举办加锁，也就是上面的提到的锁疏散技能，而每一个Segment元素存储的是HashEntry数组+链表，这个和HashMap的数据存储布局一样

初始化

ConcurrentHashMap的初始化是会通过位与运算来初始化Segment的巨细，用ssize来暗示，如下所示

int sshift = 0;
int ssize = 1;
while (ssize < concurrencyLevel) {
    ++sshift;
    ssize <<= 1;
}

如上所示，因为ssize用位于运算来计较（ssize <<=1），所以Segment的巨细取值都是以2的N次方，无关concurrencyLevel的取值，虽然concurrencyLevel最大只能用16位的二进制来暗示，即65536，换句话说，Segment的巨细最多65536个，没有指定concurrencyLevel元素初始化，Segment的巨细ssize默认为16

每一个Segment元素下的HashEntry的初始化也是凭据位于运算来计较，用cap来暗示，如下所示

int cap = 1;
while (cap < c)
    cap <<= 1;

如上所示，HashEntry巨细的计较也是2的N次方（cap <<=1）， cap的初始值为1，所以HashEntry最小的容量为2

put操纵

对付ConcurrentHashMap的数据插入，这里要举办两次Hash去定位数据的存储位置

static class Segment<K,V> extends ReentrantLock implements Serializable {

从上Segment的担任体系可以看出，Segment实现了ReentrantLock,也就带有锁的成果，当执行put操纵时，会举办第一次key的hash来定位Segment的位置，假如该Segment还没有初始化，即通过CAS操纵举办赋值，然后举办第二次hash操纵，找到相应的HashEntry的位置，这里会操作担任过来的锁的特性，在将数据插入指定的HashEntry位置时（链表的尾端），会通过担任ReentrantLock的tryLock（）要领实验去获取锁，假如获取乐成绩直接插入相应的位置，假如已经有线程获取该Segment的锁，那当前线程会以自旋的方法去继承的挪用tryLock（）要领去获取锁，高出指定次数就挂起，期待叫醒。

get操纵

ConcurrentHashMap的get操纵跟HashMap雷同，只是ConcurrentHashMap第一次需要颠末一次hash定位到Segment的位置，然后再hash定位到指定的HashEntry，遍历该HashEntry下的链表举办比拟，乐成绩返回，不乐成绩返回null。

size操纵

计较ConcurrentHashMap的元素巨细是一个有趣的问题，因为他是并发操纵的，就是在你计较size的时候，他还在并发的插入数据，大概会导致你计较出来的size和你实际的size有相差（在你return size的时候，插入了多个数据），要办理这个问题，JDK1.7版本用两种方案。

try {
    for (;;) {
        if (retries++ == RETRIES_BEFORE_LOCK) {
            for (int j = 0; j < segments.length; ++j) ensureSegment(j).lock(); // force creation
        }
        sum = 0L;
        size = 0;
        overflow = false;
        for (int j = 0; j < segments.length; ++j) {
            Segment<K,V> seg = segmentAt(segments, j);
            if (seg != null) { sum += seg.modCount; int c = seg.count; if (c < 0 || (size += c) < 0)
               overflow = true;
            } }
        if (sum == last) break;
        last = sum; } }
finally {
    if (retries > RETRIES_BEFORE_LOCK) {
        for (int j = 0; j < segments.length; ++j)
            segmentAt(segments, j).unlock();
    }
}

1. 第一种方案他会利用不加锁的模式去实验多次计较ConcurrentHashMap的size，最多三次，较量前后两次计较的功效，功效一致就认为当前没有元素插手，计较的功效是精确的；
2. 第二种方案是假如第一种方案不切合，他就会给每个Segment加上锁，然后计较ConcurrentHashMap的size返回。

JDK1.8的实现