欢迎访问昆山宝鼎软件有限公司网站! 设为首页 | 网站地图 | XML | RSS订阅 | 宝鼎邮箱 | 后台管理


新闻资讯

MENU

软件开发知识

深入并发包 昆山软件定制开发 ConcurrentHashMap

点击: 次  来源:宝鼎软件 时间:2017-08-01

原文出处: pettyandydog

媒介

以前写过先容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构成,如下图所示:

深入并发包 昆山软件定制开拓  ConcurrentHashMap

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的实现