java核心基础ConcurrentHashMap怎么掌握(concurrenthashmap,java,开发技术)

ConcurrentHashMap是基于Hash表的Map接口实现，键与值均不允许为NULL，他是一个线程安全的Map。同时他也是一个无序的Map，不同时间进行遍历可能会得到不同的顺序。在JDK1.8之前，ConcurrentHashMap使用分段锁以在保证线程安全的同时获得更大的效率。JDK1.8开始舍弃了分段锁，使用自旋+CAS+sync关键字来实现同步。本文所述便是基于JDK1.8。
ConcurrentHashMap与HashMap有共同之处，一些HashMap的基本概念与实现，本文不再赘述。

可以看到ConcurrentHashMap继承了AbstractMap及ConcurrentMap抽象类，并实现了Serializable接口，这说明ConcurrentHashMap是一个线程安全的标准Map，且允许序列化。与HashMap不同是ConcurrentHashMap不允许Clone。

ConcurrentHashMap同样是采用懒初始化的方式，有实际元素时才进行容器的初始化。因此其构造方法与HashMap相差无几。

以上构造并没有什么特别的，逻辑也相对简单，不再详细解析，感兴趣的话可以到前言提到的HashMap篇了解。
除此之外，ConcurrentHashMap拥有另外一个值得注意的构造方法：
指定初始容量，装载因子以及并发级别的构造方法：
源码：

解析： 除了初始容量与装载因子外，此构造方法还有一个并发级别concurrencyLevel的参数。在jdk1.7时，并发级别作为分段锁的标准进行分段。但是jdk1.8开始舍弃了分段锁，为了版本兼容，此构造方法依然存在，但是concurrencyLevel也不再具有其分段依据的意义，而是作为初始容量的定义依据。

ConcurrentHashMap采用懒初始化的方式，在第一次putAvl时如果容器为空，则会调用initTable()进行容器的初始化：

解析： 容器初始化完成之前不断的进行循环。这是因为ConcurrentHashMap是一个支持并发的Map，可能同时会有多个线程进入initTable方法，但是只有一个线程执行初始化操作，那么剩下的线程就需要等待初始化完成再跳出initTable方法，以满足接下来的putVal操作。
为了保证只有一个线程执行初始化操作，使用sizeCtl来作为标识，sizeCtl为-1时即说明当前已有线程正在初始化，则放弃CPU继续循环。sizeCtl不为负数时，则使用CAS(通过Unsafe+偏移量的方式实现)将sizeCtl置为-1,如果当前线程成功的话则进入实际的扩容操作。
通过CAS锁定成功后再次判断容器是否为空,这是为了避免并发，比如上面判断了tab为空，然后另一个线程做了初始化操作，结束时sc被设置为扩容阈值，然后继续(sc = sizeCtl) < 0,这时cs还是大于0，所以还是能走进来的，所以这里再判断一下。
如果sc(sizeCtl原值)大于0，则以sc做为初始容量。这个在构造方法篇提到过，对于有初始容量要求的构造，会以sizeCtl暂存初始容量。否则的话就取默认的初始容量DEFAULT_CAPACITY（16）。
接下来就建立目标容量的容器并赋值给容器属性table,计算该容量下的扩容阈值赋值给sizeCtl 。sizeCtl的赋值放到finally里面的原因是因为无论容器创建成功还是失败,都需要放开以sizeCtl为负值作为判断条件的锁，以保证在本线程创建失败的情况其它线程能继续竞争锁继续进行容器创建的工作。
至此，容器的初始化便完成了。

ConcurrentHashMap新数据载入主要通过putVal实现：

解析： 完成为空校验后，通过spread方法来计算出hash以确定下标位置，spread的计算方式为(h ^ (h >>> 16)) & HASH_BITS,HASH_BITS的值为0x7fffffff，描述出来就是将hashCode的高16位和低16位做异或操作，并保证最高位符号位为0（结果是一个正数），注解表示这样做的原因是为了使数据更加分散，尽可能的避免hash冲突。
如果容器tab为空或者长度为0说明容器未初始化，那么就调用initTable进行容器初始化。
否则的话对hash与现容量进行与运算得出数据应处的下标，判断此下标所在处节点是否为空，为空说明没有元素，直接创建一个新节点作为头元素放进去，这一步通过CAS操作实现，避免并发情况下另外的线程先一步完成头节点创建操作。
如果下标所在处节点不为空，说明该处已经有元素了，此时判断头节点的hash是否为MOVED，MOVED的值为-1。上面提到过，正常元素通过spread方法计算出来的hash值都会使正数。此处-1为一个特殊值，意味着此节点正在进行扩容迁移工作，那么此时就调用8 辅助扩容-helpTransfer方法进行辅助迁移工作。
如果节点hash不为MOVED，意味着这是一个正常节点，就执行元素载入工作，使用synchronized关键字实现同步， 同步块内开始还要使用tabAt(tab, i) == f判断进入同步后i处的节点还是原节点，接下来就是元素的载入工作了，整体和HashMap的流程是相差无几的，感兴趣的话可以去文首提到的解析HashMap的文章了解一下。synchronized块将元素载入节点后，接着会对binCount进行判断，binCount在节点还处于链表模式下的情况下记录节点在新元素载入后的元素总数量，此处判断binCount达到TREEIFY_THRESHOLD(8) 树化阈值后，就会对该节点进行树化操作。树化操作依然是通过synchronized来完成的，这里不做过多延伸。
以上整个新元素载入操作都是一个自旋的过程，一直到新元素载入成功后通过break跳出自旋过程。
新元素载入节点后，需要对count实时维护，count通过6 维护与启动扩容-addCount 方法完成同步维护工作。

ConcurrentHashMap通过addCount方法实时维护内部元素数量，并在达到扩容阈值的情况下启动扩容操作：

解析： count的维护有两种方式：未产生并发场景时通过baseCount维护，经历过并发场景后转变为通过counterCells维护。baseCount模式为直接使用int进行加减运算，cas保证同步，counterCells模式类似于1.8之前的ConcurrentHashMap，采用一个分段的概念，运算时随机找一个槽，通过cas保证一个槽的值加算同步，count即为所以槽的加和(使用LongAdder实现)。
addCount方法初始即通过counterCells是否为空(为空说明未经历初始化，使用的baseCount模式)来判断当前是否为counterCells模式，如果处于counterCells模式则进入counterCells模式计算逻辑，否则的话使用baseCount模式来维护count并记录为s，如果遭遇并发导致维护失败，则转换为counterCells模式进入counterCells模式计算逻辑。
进入counterCells模式，首先看counterCells是否已完成初始化，若为初始化进入fullAddCount，已初始化的话则随机找到counterCells中的一个槽位，如果这个槽位未初始化则进入fullAddCount，如果已初始化则对这个操作进行CAS的加操作来维护count，CAS成功则维护完成，并发导致CAS维护失败则进入fullAddCount。fullAddCount有点类似于CMS的full GC退化机制，会完成counterCells的初始化以及并发冲突场景下同步完成count维护。counterCells最后则判断check是否小于等于1(1表示是当前节点的第一个元素,-1标识是replace方法或者clear过来的，这些都不需要扩容)则直接结束，不进行扩容判定，否则的话通过sumCount获得当前count并记录为s以准备后续的扩容判定。
check大于等于0(即不是replace或者clear方法引起的count改变)时进行扩容判定，执行扩容需要满足三个条件：1.count大于扩容阈值或者当前正在执行扩容操作2.容器已初始化完毕3.容量未达到最大容量。满足以上条件则需判定当前是否正在扩容，因为扩容时会将SIZECTL设置为一个特征值，这个特征值为负值，因此通过sc是否小于0来判定当前是否处于扩容状态。接下来使用resizeStamp获得容量特征值(一个表示容量n的左0数量并将高位置1的值)，如果当前未处于扩容过程，则通过容量特征值获得扩容特征值(高16位为容量特征值，低16位为扩容线程量特征值)并通过CAS修改SIZECTL为扩容特征值，成功则当前线程作为第一个扩容线程启动扩容，失败则重新计算count并进行扩容判定。
如果已处于扩容过程，则判断是否还要写辅助扩容线程，满足以下几个条件则：1.此次扩容的容量与当前正在进行的容量一致2.扩容线程未达到最大额定值3.不是处于扩容收尾阶段(只剩下一个辅助扩容线程，nextTable已经为空，扩容下标已为0无法继续分配)则使用CAS修改扩容特征值成功后当前线程作为辅助扩容线程加入扩容任务，不满足条件则重新计算count并自旋进行扩容判定。

ConcurrentHashMap的实际扩容操作通过transfer来完成：

解析： transfer采用分段扩容的方式，从n-1->0,每个线程每次会占用一个步长的区间，然后针对这个区间进行扩容，扩容完毕再去占用下一个区间，直到无法占用新的区间则结束扩容流程。
步长的计算与应用的CPU数有关，如果当前应用CPU数为1则步长为n,即单线程库扩容。如果当前应用CPU数不为1，则为0.25n/CPU，但是如果算出的步长小于最小MIN_TRANSFER_STRIDE(16),则以MIN_TRANSFER_STRIDE为步长。
接下来通过nextTable 是否为空判断是否为初始扩容线程，如果是的话就创建一个长度为2n的新容器并记录到nextTable属性，所有扩容线程共同使用nextTable作为新容器，同时记录当前扩容进度下标transferIndex为n（扩容占用是从n到0的，因此初始未占用时就是n）。这里虽然没进行加锁但是依然不会有并发问题，因为nextTable为空的只有初始线程，而初始线程的创建则是线程安全的。
步长确认完毕，新容器创建完毕，扩容进度下标初始化完成，接下来就开始进行区间占用了：使用自旋+CAS来进行线程安全的区间占用，advance作为自旋结束的条件：如果i大于bound意味着本次占用的区间还没处理完则结束自旋。finishing意味着扩容已经进入尾声了，也无需再加入扩容，结束自旋。扩容进度下标transferIndex小于等于0说明所有的区间都已经被占用了也无需再加入扩容，结束自旋。如果以上条件不成立，则使用CAS修改扩容进度下标transferIndex尝试占用一个步长的区间，如果失败则自旋继续判定区间占用，修改成功则意味着区间占用成功，赋值本次区间的扩容游标i以及下标边界bound。
区间占用成功后开始从i到bound的扩容阶段，首先需要判断i的合法性(需要在i和n之间，即判断是不是已扩容完毕，如–i的循环会使得i为负数表示扩容完毕)，如果没占据到区间则判断是不是处于于finishing阶段，处于的话说明自己以及是最后一个扩容线程了，将新容器nextTable赋值为table，并设置新的扩容阈值。如果不是处于finishing阶段则因为当前线程没占据到区间需要退出扩容，那么响应的扩容特征值也要相应的-1来完成扩容线程量特征值的维护，如果扩容特征值维护失败则需要继续自旋尝试退出，如果维护成功则判断自己退出之后是不是只能先一个扩容线程,因为起始扩容线程的线程扩容量特征值为+2，所以通过-2来判断，如果自己退出之后仅剩一个线程在扩容，那么就把finishing设置为true，以使其在扩容工作结束后进行新容器的赋值以及新扩容阈值的维护。
如果i处于合法范围内，说明处于正常扩容中，那么获取i处的节点，节点为空则利用一个CAS为其赋值一个ForwardingNode节点，这个节点是一个中继节点，意味着这个节点正处于扩容状态，其hash值为特殊值MOVED(-1)，在5 新数据载入-putVal 的过程中如果发现目标节点hash值为MOVED，那么putVal线程就会暂停put操作，作为辅助扩容线程先行扩容容器，扩容完毕后再进行put操作。
如果i处节点不会空但是hash值已经是MOVED，那么说明节点已经处于迁移状态则跳过。
如果以上均不符合，说明i合法，且i处拥有实际的数据节点，那么使用i处的节点f作为锁通过synchronized来达成线程安全的扩容，因为putVal过程中也是用i处的节点f作为锁进行synchronized的，意味着对i处的操作扩容和赋值只有一个过程能操作，以此来保证putVal和transfer的并发安全性。synchronized内部的扩容过程因为已经保证了线程同步，因此和HashMap的扩容过程区别并不大，这里不再描述，感兴趣的话可以查看9: 从源码看HashMap:一文看懂HashMap了解。

在5 新数据载入-putVal 中以及7 进行扩容-transfer中都提到过如果putVal过程中发现目标节点是一个中继节点ForwardingNode(hash值为特殊值MOVED)那么putVal会暂停put操作，通过helpTransfer方法进行辅助扩容：

解析： 这个方法是不是看起来很熟悉，是的，除了ForwardingNode判断，其主要逻辑和6 维护与启动扩容-addCount判定扩容时的逻辑大致相当。因此也不在额外表述。这里贴出来的目的仅仅是为了完整的体现putVal遭遇扩容并发的处理过程。