ConcurrentHashMap可以说是目前使用最多的并发数据结构之一。作为这样一个核心的基础组件，它不仅要满足我们的功能需求，还要满足性能需求。实现一个高性能的线程安全的HashMap并不容易。作为JDK8的内部实现，ConcurrentHashMap是一个成功的例子，有很多值得我们学习和致敬的地方。在全局搜索项目中的这个类时，发现使用了很多项目代码和源代码。为什么如此受欢迎？这到底是道德的吗……呸。下面我们来看一下ConcurrentHashMap的内部实现，感受一下它的精妙之处！ConcurrentHashMap的内部数据结构在JDK8中，ConcurrentHashMap的内部实现发生了翻天覆地的变化。这里介绍一下基于JDK8的ConcurrentHashMap的内部实现。从静态数据结构来看，ConcurrentHashMap包含以下内容：intsizeCtl这是一个多功能字段，可以用来记录参与Map扩容的线程数，也可以用来记录新表的扩容阈值。CounterCell[]counterCells是用来记录元素个数的，它是一个数组，使用数组来记录，避免多线程竞争时可能出现的冲突。在使用数组的时候，当多个线程同时修改数量的时候，很有可能实际上操作的是数组中的不同元素，从而减少竞争。Node[]表是实际存放Map内容的地方。map其实就是一个Node数组，每个Node包含key和value信息。Node[]nextTable当表需要扩容时，会将新的数据填充到nextTable中，也就是说nextTable是一个扩容的Map。以上就是ConcurrentHashMap的核心元素，其中最值得一提的是Node。Node并没有想象中那么简单。下图是Node的家族结构：可以看出，Map中的Node并不是一个简单的Node对象。其实，一般来说，它可能是一个Node对象，也可能是一个Treebin或ForwardingNode。那么什么时候是Node，什么时候是TreeBin，什么时候是ForwardingNode呢？其实大部分场景还是会用到Node。从Node数据结构不难看出Node其实是一个链表。也就是说，一个普通的Map可能是这样的：在上图中，绿色部分代表的是Node数组，里面的元素是Node，也就是链表的头部。当两个元素在数据中的位置发生冲突时，将它们以链表的形式放入槽中。当数组槽对应一个链表时，只需要简单的遍历就可以找到链表中的key。当数据不多时，这是可以接受的。当有很多冲突的数据时，这种简单的遍历就有点慢了。.所以在具体实现中，当链表长度大于等于8时，链表会变成树形，即变成红黑树。如下图，其中一个slot变成了一棵树，就是TreeBin（TreeNode用来构造TreeBin中的整个分支树）。当阵列容量快满时，即容量超过75%时，就需要对阵列进行扩容。在扩展过程中，如果旧数组已经被复制，旧数组中的元素将被ForwardingNode对象替换，表明当前槽中的数据已经被处理过，不需要再次处理。这样当多个线程同时参与扩容时，就不会发生冲突。put()方法的实现现在让我们看一下作为HashMap的最重要的方法put()：publicVput(Kkey,Vvalue)它负责将给定的键值对存储到HashMap中。它的主要工作是如下步骤：如果数组没有初始化，则尝试初始化数组如果当前正在扩容，则参与帮助扩容（调用helpTransfer()方法）将给定的key和value放入对应的slot中并计数触发扩容操作的元素总数根据上面四个主要步骤依次详细解释：如果数组没有初始化，尝试初始化数组，并初始化数据生成一个Node数组：Node[]nt=(节点[])新节点[n];默认n为16，同时设置sizeCtl为n-(n>>>2)；这意味着sizeCtl是n的75%，表示Map的大小，也就是说ConcurrentHashMap的负载因子是0.75。（为了避免冲突，Map的容量为数组的75%，如果超过这个阈值，就会扩容。）如果当前正在扩容，参与帮助扩容elseif((fh=f.hash)==MOVED)tab=helpTransfer(tab,f);如果一个节点的hash为MOVE，说明这是一个ForwardingNode，即当前正在扩容。为了尽快完成扩容，当前线程会参与扩容工作，而不是等待扩容操作完成，如此严密细致的操作恰恰是ConcurrentHashMap高性能的原因。代码中的f.hash==MOVE在语义上等同于finstanceofForwardingNode，但是使用整数相等判断的效率要比instanceof高很多，所以这也是对性能的一种极致优化。将给定的key和value放入对应的slot大多数情况下，应该会走到这一步，即将key和value放入数组中。在此操作中，将使用以下操作：Nodef;synchronized(f){if（槽为链表）插入链表elseif（槽为红黑树）插入树if（链表长度大于8[TREEIFY_THRESHOLD]）对树进行树化linkedlist}可以看出，这里使用了synchronized关键字来锁定Node对象。由于在大多数情况下，不同的线程大概率会操作不同的Node，所以这里的竞争应该不会太大。并且随着数组的大小变大，竞争的概率会越来越小，所以ConcurrentHashMap具有优秀的并行性。统计元素总数为了有一个高性能的size()方法，ConcurrentHashMap使用单独的方法统计元素总数，CounterCell数组中统计元素个数：CounterCell[]counterCells;@sun.misc.ContendedstaticfinalclassCounterCell{volatilelongvalue;CounterCell(longx){value=x;}}CounterCell采用伪共享优化，读写性能高。将counterCells中所有成员的值加到整个Map的大小上。这里使用数组来防止冲突。如果单纯的使用一个变量，多线程累加一个计数器时难免会发生竞争。现在分散成一个数组，这样竞争小很多，对并发友好。累加的主要逻辑如下：if(as==null||(m=as.length-1)<0||//不同的线程映射到不同的数组元素，防止冲突(a=as[ThreadLocalRandom.getProbe()&m])==null||//使用CAS直接增加对应的数据！(uncontended=U.compareAndSwapLong(a,CELLVALUE,v=a.value,v+x)))//如果有竞争，这里会Retry，如果竞争严重，会扩容CounterCell[]数组，减少竞争，触发扩容操作。最后ConcurrentHashMap也会检查是否需要扩容。它将检查当前Map大小是否超过阈值。如果超过了，也会进行扩容。ConcurrentHashMap的扩展过程非常巧妙。它并没有完全打乱现有元素的位置，而是在数组扩展2倍后将一半元素移动到新空间。所有元素根据高位是否为1分为低节点和高节点：//n是数组的长度，数组的长度是2的次方，所以必须是二进制数如100100010000100000//这里低节点串在一起，高节点串在一起if((ph&n)==0)ln=newNode(ph,pk,pv,ln);elsehn=newNode(ph,pk,pv,hn);然后，重新定位这些元素的位置：//lownode停留在当前位置setTabAt(nextTab,i,ln);//highnode展开后放置在新位置，新位置与旧位置相距较远nsetTabAt(nextTab,i+n,hn);//扩展完成，用ForwardingNode填充setTabAt(tab,i,fwd);下图是从8扩展到16时可能的扩展情况，注意新位置总是在旧位置n后面，这样做的好处是不需要重新计算每个元素的位置。查找的时候，总是n-1（必须是像111111111111111这样的二进制数）按位与，所以高级别的节点自然会出现在+n的位置。get()方法的实现比put()方法简单。步骤如下：根据hash值，得到对应的slot(n-1)&h如果当前slot的第一个元素的key与请求的相同，则直接返回；否则，调用Node的find()方法查找ForwardingNode，ForwardingNode使用。find()使用红黑树的TreeBin。find()为链表槽，依次查找对应的key写在末尾.ConcurrentHashMap可以说是并发设计的典范。在JDK8中，ConcurrentHashMap可以说是又一次重生，全新的架构和实现带来了飞一般的体验（JDK7中的ConcurrentHashMap仍然是用比较骨感的段实现的），仔细一想还是有不少收获的阅读。他和HashMap的区别，优缺点对比，这也是经常考的考点，所以不管是理解，工作还是面试，大家应该都熟悉一下。我会继续更新多线程系列。我是敖丙你知道的越多，你不知道的就越多。江湖见。
