你的位置:首页 > 软件开发 > Java > 【JDK源码系列】ConcurrentHashMap

【JDK源码系列】ConcurrentHashMap

发布时间:2015-09-15 23:00:15
并发永远是高性能的话题,而并发容器又是java中重要的并发工具,所以今天我们来分析一下Concurrent包中ConcurrentHashMap(以下简称Chashmap)。普通容器在某些并**况下的表现很差,假设这容器的体积很大,容器获得锁后进行了非常耗时的遍历操作,那么锁就会 ...

【JDK源码系列】ConcurrentHashMap

并发永远是高性能的话题,而并发容器又是java中重要的并发工具,所以今天我们来分析一下Concurrent包中ConcurrentHashMap(以下简称Chashmap)。普通容器在某些并**况下的表现很差,假设这容器的体积很大,容器获得锁后进行了非常耗时的遍历操作,那么锁就会被占用很长世间。事实上只有很小一部分元素被线程占用,其余的元素完全可以被读写。而(以下简称Chashmap就是实现了这一特性,使用该容器一部分区域的时候其他线程可以同时读写容器中的剩余区域,所以Chashmap的效率很高。

【JDK源码系列】ConcurrentHashMap

Chashmap的关键实现是一种分段锁机制,简单来讲就是将hash表分成一段段子表,分别加锁。这样线程需要占用哪一段就获取哪一段的锁,剩余的段不受影响。本质上Chashmap和hashMap没什么区别,元素都是Entry,一个节点加链表。发生冲突的时候采用链表法存储元素,所以源码里会有大量的通过key的hash值找到槽后进行遍历查询的操作。下面是子表的声明:

【JDK源码系列】ConcurrentHashMap

自定义了一个segment类,继承了可重入锁。可以看一下整体的结构:

【JDK源码系列】ConcurrentHashMap

其中比较关键的应该是put,rehash,scanandlock,remove,replace等方法。

我们先来看segment的put方法:

对map中的某个segment做put操作,加入我们来实现一般会考虑到几点:

需要加锁,因为要考虑到key相同的情况,如果不加锁,两个线程同时更新同一个key的value,会出错。

1)需要考虑锁已经被占的情况。

2)需要更新segment的元素个数。

3)需要考虑segment扩容的问题。

带着这些考虑,我们再来看源码可能就会更有针对性一些。

【JDK源码系列】ConcurrentHashMap

第一步果然是加锁,这里直接用了trylock,因为segment继承了可重入锁,其实这是个很垃圾的设计,按理来说应该优先使用组合而不是继承。我们可以看到,尝试获取锁失败后,调用了scanAndLockForPut方法,这个方**不断尝试获取锁,同时去匹配entry的key值,直到成功,重新回到put方法。Put方法里考虑到了扩容的问题:

【JDK源码系列】ConcurrentHashMap

假如元素个数大于阈值,会调用rehash方法。Rehash首先进行了数组的扩容:

【JDK源码系列】ConcurrentHashMap

同时对老的元素进行迁移的时候进行了rehash操作: idx = e.hash&sizeMask

【JDK源码系列】ConcurrentHashMap

最后put方**更新元素总数:

【JDK源码系列】ConcurrentHashMap

下面我们来看一下remove方法:

1)同样的我们首先来自己思考一下哪些点是需要考虑到的:

2)需要枷锁,同时考虑锁被抢占,同插入

3)更新元素个数

首先是尝试获取锁,如果锁被占了,那么等待获取。

【JDK源码系列】ConcurrentHashMap

查找的时候先获取Entry,然后遍历链表:

【JDK源码系列】ConcurrentHashMap

找到元素后进行普通的链表移除元素操作,并更新元素总数。

【JDK源码系列】ConcurrentHashMap

这里有点奇怪的地方,modeCount为什么加一了?这点后面解答。

Replace和remove操作几乎一致,这里不再赘述。

看完segment的主要方法我们再来仔细看一下Chashmap的方法,首先是put方法:

【JDK源码系列】ConcurrentHashMap

首先要获取对应的segment,然后委托给具体的segment。这里有个细节,对于value为null的情况抛出了异常。

对于remove方法同样也是委托执行:

【JDK源码系列】ConcurrentHashMap'

从上述代码可以看出put和remove方法都是委托给底层的segment执行,所以不复杂,倒是size这种需要统计的方法因为要考虑到并发更改元素的情况会比较复杂。Size方法需要考虑几点

统计过程中各个segment的元素个数可能会被动态改变的情况怎么检测,如何处理?

不断重试统计的标准是什么?即什么时候停止重试?

假设重试次数过多应该采取什么策略?

【JDK源码系列】ConcurrentHashMap

我们看到size的代码可以看出上述3个疑问的解答:

  1. 通过检测两次的modecount的和是否相等来检测统计期间是否有并发线程改变了segment的元素个数
  2. 重试次数达到一个阈值(2次)锁定所有的segment
  3. 分别读取各个segment的元素个数加和获得总的元素个数

对于其他类似的读取操作,比如contains操作,也会有在读取期间发生元素被添加/移除的情况。采取的策略也是一致的,读取两次并对比,如果不一致就加锁。

最后我们来看一下get方法:

public V get(Object key) {

Segment<K,V> s; // manually integrate access methods to reduce overhead

HashEntry<K,V>[] tab;

int h = hash(key);

long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;

if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&

(tab = s.table) != null) {

for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile

(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);

e != null; e = e.next) {

K k;

if ((k = e.key) == key || (e.hash == h && key.equals(k)))

return e.value;

}

}

return null;

}

 


原标题:【JDK源码系列】ConcurrentHashMap

关键词:jdk

jdk
*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。