昆明java培训
达内昆明广州春城路

18487146383

热门课程

JDK1.7 ConcurrentHashMap源码浅析

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

昆明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设置

AI初创企谷歌跑在前面了!达内java培训

‘资产荒’为什么这么说?【达内培训】

java集合-Iterator迭代

阿里云澳门战略携手创“城市大脑”——达内编程培训

选择城市和中心
贵州省

广西省

海南省

台湾