ConcurrentHashMap 总结（上）

转自：

<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; clear:both; min-height:1em; color:rgb(62,62,62); font-family:'Helvetica Neue',Helvetica,'Hiragino Sans GB','Microsoft YaHei',Arial,sans-serif; font-size:16px; max-width:100%!important; word-wrap:break-word!important">
并发编程实践中，ConcurrentHashMap是一个经常被使用的数据结构，相比于Hashtable以及Collections.synchronizedMap()，ConcurrentHashMap在线程安全的基础上提供了更好的写并发能力，但同时降低了对读一致性的要求（这点好像CAP理论啊 O(∩_∩)O）。ConcurrentHashMap的设计与实现非常精巧，大量的利用了volatile，final，CAS等lock-free技术来减少锁竞争对于性能的影响，无论对于Java并发编程的学习还是Java内存模型的理解，ConcurrentHashMap的设计以及源码都值得非常仔细的阅读与揣摩。

<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; clear:both; min-height:1em; color:rgb(62,sans-serif; font-size:16px; max-width:100%!important; word-wrap:break-word!important">
这篇日志记录了自己对ConcurrentHashMap的一些总结，由于JDK6，7，8中实现都不同，需要分开阐述在不同版本中的ConcurrentHashMap。

<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; clear:both; min-height:1em; color:rgb(62,sans-serif; font-size:16px; max-width:100%!important; word-wrap:break-word!important">
之前已经在<a target="_blank" href="http://mp.weixin.qq.com/s?__biz=MjM5NzMyMjAwMA==&mid=206418539&idx=1&sn=988343c3d0580f8e0af2a65230e8ff34&scene=21#wechat_redirect" rel="nofollow" style="margin:0px; padding:0px; color:rgb(96,127,166); text-decoration:none; max-width:100%!important; word-wrap:break-word!important">ConcurrentHashMap原理分析中解释了ConcurrentHashMap的原理，主要是从代码的角度来阐述是源码是如何写的，本文仍然从源码出发，挑选个人觉得重要的点（会用红色标注）再次进行回顾，以及阐述ConcurrentHashMap的一些注意点。

<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; clear:both; min-height:1em; color:rgb(62,sans-serif; font-size:16px; max-width:100%!important; word-wrap:break-word!important">
1. JDK6与JDK7中的实现

<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; clear:both; min-height:1em; color:rgb(62,sans-serif; font-size:16px; max-width:100%!important; word-wrap:break-word!important">
1.1 设计思路

<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; clear:both; min-height:1em; color:rgb(62,sans-serif; font-size:16px; max-width:100%!important; word-wrap:break-word!important">
ConcurrentHashMap采用了分段锁的设计，只有在同一个分段内才存在竞态关系，不同的分段锁之间没有锁竞争。相比于对整个Map加锁的设计，分段锁大大的提高了高并发环境下的处理能力。但同时，由于不是对整个Map加锁，导致一些需要扫描整个Map的方法（如size(),containsValue()）需要使用特殊的实现，另外一些方法（如clear()）甚至放弃了对一致性的要求（ConcurrentHashMap是弱一致性的，具体请查看ConcurrentHashMap能完全替代HashTable吗？）。

<blockquote style="margin:0px; padding:0px 0px 0px 10px; border-left-width:3px; border-left-style:solid; border-left-color:rgb(219,219,219); color:rgb(62,sans-serif; font-size:16px; max-width:100%!important; word-wrap:break-word!important">

http://my.oschina.net/hosee/blog/675423

JDK7与JDK8中HashMap的实现）的结构，即内部拥有一个Entry数组，数组中的每个元素又是一个链表；同时又是一个ReentrantLock（Segment继承了ReentrantLock）。ConcurrentHashMap中的HashEntry相对于HashMap中的Entry有一定的差异性：HashEntry中的value以及next都被volatile修饰，这样在多线程读写过程中能够保持它们的可见性，代码如下：

{

next;

用户也可以在构造函数中设置并发度。当用户设置并发度时，ConcurrentHashMap会使用大于等于该值的最小2幂指数作为实际并发度（假如用户设置并发度为17，实际并发度则为32）。运行时通过将key的高n位（n = 32 – segmentShift）和并发度减1（segmentMask）做位与运算定位到所在的Segment。segmentShift与segmentMask都是在构造过程中根据concurrency level被相应的计算出来。

cpu cache命中率会下降，从而引起程序性能下降。（文档的说法是根据你并发的线程数量决定，太多会导性能降低）

调用ensureSegment()以确保对应的Segment被创建。

调用，但与想象中不同，ensureSegment并未使用锁来控制竞争，而是使用了Unsafe对象的getObjectVolatile()提供的原子读语义结合CAS来确保Segment创建的原子性。代码段如下：

)UNSAFE.getObjectVolatile(ss,u))

s = new Segment(lf,threshold,tab);

方法被代理到了对应的Segment（定位Segment的原理之前已经描述过）中。与JDK6不同的是，JDK7版本的ConcurrentHashMap在获得Segment锁的过程中，做了一定的优化 - 在真正申请锁之前，put方法会通过tryLock()方法尝试获得锁，在尝试获得锁的过程中会对对应hashcode的链表进行遍历，如果遍历完毕仍然找不到与key相同的HashEntry节点，则为后续的put操作提前创建一个HashEntry。当tryLock一定次数后仍无法获得锁，则通过lock申请锁。

删除，即使该变化因为是非原子写操作（删除节点后链接后续节点调用的是Unsafe.putOrderedObject()，该方法不提供原子写语义）可能导致当前线程无法观察到，但因为不影响遍历的正确性所以忽略不计。

获取锁的过程中对整个链表进行遍历，主要目的是希望遍历的链表被cpu cache所缓存，为后续实际put过程中的链表遍历操作提升性能。

调用rehash()方法对Segment进行扩容，最后将新建HashEntry写入到数组中。

方法中，链接新节点的下一个节点（HashEntry.setNext()）以及将链表写入到数组中（setEntryAt()）都是通过Unsafe的putOrderedObject()方法来实现，这里并未使用具有原子写语义的putObjectVolatile()的原因是：JMM会保证获得锁到释放锁之间所有对象的状态更新都会在锁被释放之后更新到主存，从而保证这些变更对其他线程是可见的。

方法中会定位第一个后续所有节点在扩容后index都保持不变的节点，然后将这个节点之前的所有节点重排即可。这部分代码如下：

node) {

[] oldTable = table;

[]) new HashEntry[newCapacity];

e = oldTable[i];

next = e.next;

lastRun = e;

last = next;

n = newTable[k];

(h,p.key,v,n);

方法几乎完全一致：他们都没有使用锁，而是通过Unsafe对象的getObjectVolatile()方法提供的原子读语义，来获得Segment以及对应的链表，然后对链表遍历判断是否存在key相同的节点以及获得该节点的value。但由于遍历过程中其他线程可能对链表结构做了调整，因此get和containsKey返回的可能是过时的数据，这一点是ConcurrentHashMap在弱一致性上的体现。如果要求强一致性，那么必须使用Collections.synchronizedMap()方法。

方法都是基于整个ConcurrentHashMap来进行操作的，他们的原理也基本类似：首先不加锁循环执行以下操作：循环所有的Segment（通过Unsafe的getObjectVolatile()以保证原子读语义），获得对应的值以及所有Segment的modcount之和。如果连续两次所有Segment的modcount和相等，则过程中没有发生其他线程修改ConcurrentHashMap的情况，返回获得的值。

次数超过预定义的值时，这时需要对所有的Segment依次进行加锁，获取返回值后再依次解锁。值得注意的是，加锁过程中要强制创建所有的Segment，否则容易出现其他线程创建Segment并进行put，remove等操作。代码如下：

方法。

方法中都会被修改。

方法来说，如果在循环过程中发现匹配value的HashEntry，则直接返回true。

方法的实现中就有一段对HashEntry.value == null的防御性判断。但Doug Lea也承认实际运行过程中，这种情况似乎不可能发生（参考：http://cs.oswego.edu/pipermail/concurrency-interest/2011-March/007799.html）。

实现方法。

增加了很多辅助的类，例如TreeBin，Traverser等对象内部类。

属性

属性，与HashMap相同的就不再介绍了，这里重点解释一下sizeCtl这个属性。可以说它是ConcurrentHashMap中出镜率很高的一个属性，因为它是一个控制标识符，在不同的地方有不同用途，而且它的取值不同，也代表不同的含义。

[] table;

属性设置了volatile同步锁(与JDK7的Segment相同)，它不允许调用setValue方法直接改变Node的value域，它增加了find方法辅助map.get()方法。

类，也就是说TreeNode带有next指针，这样做的目的是方便基于TreeBin的访问。

用户的key、value信息，而是包装的很多TreeNode节点。它代替了TreeNode的根节点，也就是说在实际的ConcurrentHashMap“数组”中，存放的是TreeBin对象，而不是TreeNode对象，这是与HashMap的区别。另外这个类还带有了读写锁。

方法。可以看到在构造TreeBin节点时，仅仅指定了它的hash值为TREEBIN常量，这也就是个标识为。同时也看到我们熟悉的红黑树构造方法

方法是从nextTable里进行查询节点，而不是以自身为头节点进行查找。

extends Node[] nextTable;

[] tab) {

find(int h,Object k) {

[] tab = nextTable;;) {

e; int n;

)e).nextTable;

方法，这个方法是利用一个CAS算法实现无锁化的修改值的操作，他可以大大降低锁代理的性能消耗。这个算法的基本思想就是不断地去比较当前内存中的变量值与你指定的一个变量值是否相等，如果相等，则接受你指定的修改的值，否则拒绝你的操作。因为当前线程中的值已经不是最新的值，你的修改很可能会覆盖掉其他线程修改的结果。这一点与乐观锁，SVN的思想是比较类似的。

代码块控制了一些属性的修改工作，比如最常用的SIZECTL 。在这一版本的concurrentHashMap中，大量应用来的CAS方法进行变量、属性的修改工作。利用CAS进行无锁操作，可以大大提高性能。

k = ConcurrentHashMap.class;

ck = CounterCell.class;

ak = Node[].class;

SEOffset(ak);

方法

Node tabAt(Node[] tab,int i) {

)U.getObjectVolatile(tab,((long)i << ASHIFT) + ABASE);

修改，否则拒绝你的修改

修改可能会覆盖掉其他线程的修改结果有点类似于SVN

c,Node v) {

方法设置节点位置的值

方法initTable

调用它的构造方法仅仅是设置了一些参数而已。而整个table的初始化是在向ConcurrentHashMap中插入元素的时候发生的。如调用put、computeIfAbsent、compute、merge等方法的时候，调用时机是检查table==null。

方法主要应用了关键属性sizeCtl 如果这个值〈0，表示其他线程正在进行初始化，就放弃这个操作。在这也可以看出ConcurrentHashMap的初始化只能由一个线程完成。如果获得了初始化权限，就用CAS方法将sizeCtl置为-1，防止其他线程进入。初始化数组后，将sizeCtl的值改为0.75*n。

[] initTable() {

方法把sizectl的值置为-1 表示本线程正在进行初始化

0) ? sc : DEFAULT_CAPACITY;

[] nt = (Node[])new Node[n];

>> 2);//相当于0.75*n 设置一个扩容的阈值

方法 transfer

方法的基本思想跟HashMap是很像的，但是由于它是支持并发扩容的，所以要复杂的多。原因是它支持多线程进行扩容操作，而并没有加锁。我想这样做的目的不仅仅是为了满足concurrent的要求，而是希望利用并发处理去减少扩容带来的时间影响。因为在扩容的时候，总是会涉及到从一个“数组”到另一个“数组”拷贝的操作，如果这个操作能够并发进行，那真真是极好的了。

次数i，然后利用tabAt方法获得i位置的元素：

=0），如果它是一个链表的头节点，就构造一个反序链表，把他们分别放在nextTable的i和i+n的位置上

代码的69行有一个判断，如果遍历到的节点是forward节点，就向后继续遍历，再加上给节点上锁的机制，就完成了多线程的控制。多线程遍历节点，处理了一个节点，就把对应点的值set为forward，另一个线程看到forward，就向后遍历。这样交叉就完成了复制工作。而且还很好的解决了线程安全的问题。这个方法的设计实在是让我膜拜。

ConcurrentHashMap 总结（ 上 ）

猜你在找的Java相关文章

ConcurrentHashMap 总结（上）