加入收藏 | 设为首页 | 会员中心 | 我要投稿 开发网_开封站长网 (http://www.0378zz.com/)- 科技、AI行业应用、媒体智能、低代码、办公协同!
当前位置: 首页 > 教程 > 正文

JDK1.7 ConcurrentHashMap 源码畅聊

发布时间:2021-11-18 12:07:09 所属栏目:教程 来源:互联网
导读:概述 ConcurrentHashMap是HashMap的线程安全版本,使用了分段加锁的方案,在高并发时有比较好的性能。 本文分析JDK1.7中ConcurrentHashMap的实现。 正文 ConcurrentHashMap概述 HashMap不是线程安全的,要实现线程安全除非加锁,但这样性能很低。ConcurrentH

概述
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。

(编辑:开发网_开封站长网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    热点阅读