课程咨询 :0871-63112636      qq:2066486918

昆明Java培训 > 达内新闻 > JDK1.7 ConcurrentHashMap源码浅析
  • JDK1.7 ConcurrentHashMap源码浅析

    发布:昆明Java培训      来源:达内新闻      时间:2016-12-30

  • 昆明Java培训班的老师这一期给大家分享JDK1.7 ConcurrentHashMap源码浅析。

    概述

    ConcurrentHashMap是HashMap的线程安全版本,使用了分段加锁的方案,在高并发时有比较好的性能。

    本文分析JDK1.7中ConcurrentHashMap的实现。

    正文

    ConcurrentHashMap概述

    HashMap不是线程安全的,要实现线程安全除非加锁,但这样性能很低。ConcurrentHashMap把整个HashMap数组分成了若干个Segment,每个Segment里有一个数组。添加一个Key时,需要先根据hash值计算出其所在Segment,然后再根据hash值计算出在该Segment中的位置。Segment继承自ReentrantLock,每个Segment就是一个锁。在多线程的情况下,就减少了锁竞争,提升了性能。

    ConcurrentHashMap存储结构如下图所示:

    image

    下面我们来分析源码,看数据是怎么存储的。

    构造函数

    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;

    //concurrencyLevel为并发级别,这一步就是计算出大于concurrencyLevel的最小的2的N次方

    //为什么不用HashMap中的Integer.highestOneBit((number - 1) << 1)来计算这个值

    //我的理解是concurrencyLevel一般都比较小(默认为16),采用这种计算方法效率更高。

    while (ssize < concurrencyLevel) {

    ++sshift;

    ssize <<= 1;

    }

    //后面根据hash计算segment位置时需要用到

    this.segmentShift = 32 - sshift;

    this.segmentMask = ssize - 1;

    if (initialCapacity > MAXIMUM_CAPACITY)

    initialCapacity = MAXIMUM_CAPACITY;

    //计算每一个segment中table的length

    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;

    }

    和HashMap最大的不同就是多了Segment的初始化。

    Segment的Size也初始化为2的N次方,这为后面的Map整体resize以及确定一个hash值所在Segment都提供简便方法。

    每个Segment中的table同HashMap中table一样,接着来看PUT时怎么计算Segment的位置。

    PUT

    public V put(K key, V value) {

    Segment<K,V> s;

    if (value == null)

    throw new NullPointerException();

    int hash = hash(key);

    //取得Key的Segment位置

    int j = (hash >>> segmentShift) & segmentMask;

    if ((s = (Segment<K,V>)UNSAFE.getObject         // nonvolatile; recheck

    (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment

    s = ensureSegment(j);

    return s.put(key, hash, value, false);

    }

    segmentShift:在构造函数中计算出来的,假设concurrencyLevel为16,segmentShift=28(32-4)

    segmentMask:15(16-1)

    可见求Key所在Segment的算法和HashMap中求Key所在table中的位置一样,都是hash & (length-1)。

    所以这里Segment的length也必须是2的N次方。

    hash >>> segmentShift是为了使用hash的高位进行与运算。

    s.put方法,就是把Key放到Segment中table的响应位置,它的算法和HashMap中类似,只是加入了锁。

    线程安全

    HashMap -非线程安全

    Put一个Key时有下面这段代码:

    void createEntry(int hash, K key, V value, int bucketIndex) {

    //1.取得链表

    Entry<K,V> e = table[bucketIndex];

    //2.将新Key设置为链表的第一个

    table[bucketIndex] = new Entry<>(hash, key, value, e);

    size++;

    }

    假设有两个线程A、B,同时进行第1步,它们获取到的e是同一个,如:x,y,z

    然后线程A运行到第2步,为e添加了一个新元素a,并赋值给table[bucketIndex],此时table[bucketIndex]为:a,x,y,z

    而后线程B运行到第2步,为e添加了一个新元素b,并赋值给table[bucketIndex],此时table[bucketIndex]为:b,x,y,z

    所以这种情况下就会有问题,这只是其中的一个例子,所以HashMap是非线程安全的。

    ConcurrentHashMap -线程安全

    Put一个Key到Table时,使用如下代码:

    final V put(K key, int hash, V value, boolean onlyIfAbsent) {

    HashEntry<K,V> node = tryLock() ? null :

    scanAndLockForPut(key, hash, value);

    V oldValue;

    try {

    ......

    } finally {

    unlock();

    }

    return oldValue;

    }

    可以看到put时,加入了Lock,这就保证了线程的安全性。

    查看ConcurrentHashMap源代码可以发现,ConcurrentHashMap的remove、replace等有可能引起线程安全问题的地方都加了Lock。

    ConcurrentHashMap的Get方法并不是完全线程安全,因为Get时没有加锁,但JDK用了很多volatile类型变量来保证在大多数情况下的线程安全。

    具体怎么线程不安全,参考:深入剖析ConcurrentHashMap

    总结:

    ConcurrentHashMap在绝大多数情况下是线程安全的,在多线程情况下请使用ConcurrentHashMap。

    推荐文章

上一篇:为什么用接口的实现类

下一篇:spring mvc和spring security配置web.xml设置

最新开班日期  |  更多

Java--零基础全日制班

Java--零基础全日制班

开班日期:02/28

Java--零基础业余班

Java--零基础业余班

开班日期:02/28

Java--周末提升班

Java--周末提升班

开班日期:02/28

Java--零基础周末班

Java--零基础周末班

开班日期:02/28

  • 网址:http://km .java.tedu.cn      地址:昆明市官渡区春城路62号证券大厦附楼6楼
  • 课程培训电话:0871-63112636      qq:2066486918    全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内时代科技集团有限公司 版权所有 京ICP证8000853号-56