速读摘要文章源自JAVA秀-https://www.javaxiu.com/20614.html
在JDK8中，ConcurrentHashMap的内部实现发生了天翻地覆的变化。使用了数组，那么多个线程同时修改数量时，极有可能实际操作数组中不同的单元，从而减少竞争。当数组容量快满时，即超过75%的容量时，数组还需要进行扩容，在扩容过程中，如果老的数组已经完成了复制，那么就会将老数组中的元素使用ForwardingNode对象替代，表示当前槽位的数据已经处理了，不需要再处理了，当有多个线程同时参与扩容时，就不会冲突。文章源自JAVA秀-https://www.javaxiu.com/20614.html
原文约 2417 字 | 图片 4 张 | 建议阅读 5 分钟 | 评价反馈文章源自JAVA秀-https://www.javaxiu.com/20614.html
深入浅出ConcurrentHashMap内部实现
三太子敖丙 三太子敖丙 文章源自JAVA秀-https://www.javaxiu.com/20614.html
收录于话题文章源自JAVA秀-https://www.javaxiu.com/20614.html
#多线程文章源自JAVA秀-https://www.javaxiu.com/20614.html
11个文章源自JAVA秀-https://www.javaxiu.com/20614.html
ConcurrentHashMap可以说是目前使用最多的并发数据结构之一，作为如此核心的基本组件，不仅仅要满足我们功能的需求，更要满足性能的需求。而实现一个高性能的线程安全的HashMap也绝非易事。文章源自JAVA秀-https://www.javaxiu.com/20614.html
ConcurrentHashMap作为JDK8的内部实现，一个成功的典范，有着诸多可以让我们学习和致敬的地方。文章源自JAVA秀-https://www.javaxiu.com/20614.html
我全局在项目中搜索这个类的时候，发现大量项目代码和源码都用到了，为什么他会这么吃香呢？到底是道德的....呸。文章源自JAVA秀-https://www.javaxiu.com/20614.html
下面我们就来扒一扒，ConcurrentHashMap的内部实现，来体会一下它的精妙之处吧！文章源自JAVA秀-https://www.javaxiu.com/20614.html
ConcurrentHashMap的内部数据结构
在JDK8中， ConcurrentHashMap的内部实现发生了天翻地覆的变化。这里依据JDK8，来介绍一下ConcurrentHashMap的内部实现。文章源自JAVA秀-https://www.javaxiu.com/20614.html
从静态数据结构上说，ConcurrentHashMap包含以下内容：文章源自JAVA秀-https://www.javaxiu.com/20614.html
int sizeCtl
这是一个多功能的字段，可以用来记录参与Map扩展的线程数量，也用来记录新的table的扩容阈值文章源自JAVA秀-https://www.javaxiu.com/20614.html
CounterCell[] counterCells
用来记录元素的个数，这是一个数组，使用数组来记录，是因为避免多线程竞争时，可能产生的冲突。使用了数组，那么多个线程同时修改数量时，极有可能实际操作数组中不同的单元，从而减少竞争。文章源自JAVA秀-https://www.javaxiu.com/20614.html
Node<K,V>[] table
实际存放Map内容的地方，一个map实际上就是一个Node数组，每个Node里包含了key和value的信息。文章源自JAVA秀-https://www.javaxiu.com/20614.html
Node<K,V>[] nextTable
当table需要扩充时，会把新的数据填充到nextTable中，也就是说nextTable是扩充后的Map。文章源自JAVA秀-https://www.javaxiu.com/20614.html
以上就是ConcurrentHashMap的核心元素，其中最值得注意的便是Node，Node并非想象中如此简单，下面的图展示了Node的类族结构：文章源自JAVA秀-https://www.javaxiu.com/20614.html
文章源自JAVA秀-https://www.javaxiu.com/20614.html
可以看到，在Map中的Node并非简单的Node对象，实际上，它有可能是Node对象，也有可能是一个Treebin或者ForwardingNode。文章源自JAVA秀-https://www.javaxiu.com/20614.html
那什么时候是Node，什么时候是TreeBin，什么时候又是一个ForwardingNode呢？文章源自JAVA秀-https://www.javaxiu.com/20614.html
其实在绝大部分场景中，使用的依然是Node，从Node数据结构中，不难看出，Node其实是一个链表，也就是说，一个正常的Map可能是长这样的：文章源自JAVA秀-https://www.javaxiu.com/20614.html
文章源自JAVA秀-https://www.javaxiu.com/20614.html
上图中，绿色部分表示Node数组，里面的元素是Node，也就是链表的头部，当两个元素在数据中的位置发生冲突时，就将它们通过链表的形式，放在一个槽位中。文章源自JAVA秀-https://www.javaxiu.com/20614.html
当数组槽位对应的是一个链表时，在一个链表中查找key只能使用简单的遍历，这在数据不多时，还是可以接受的，当冲突数据比较多少，这种简单的遍历就有点慢了。文章源自JAVA秀-https://www.javaxiu.com/20614.html
因此，在具体实现中，当链表的长度大于等于8时，会将链表树状化，也就是变成一颗红黑树。如下图所示，其中一个槽位就变成了一颗树，这就是TreeBin(在TreeBin中使用TreeNode构造整科树)。文章源自JAVA秀-https://www.javaxiu.com/20614.html
文章源自JAVA秀-https://www.javaxiu.com/20614.html
当数组容量快满时，即超过75%的容量时，数组还需要进行扩容，在扩容过程中，如果老的数组已经完成了复制，那么就会将老数组中的元素使用ForwardingNode对象替代，表示当前槽位的数据已经处理了，不需要再处理了，这样，当有多个线程同时参与扩容时，就不会冲突。文章源自JAVA秀-https://www.javaxiu.com/20614.html
put()方法的实现
现在来看一下作为一个HashMap最为重要的方法put()：文章源自JAVA秀-https://www.javaxiu.com/20614.html
public V put(K key, V value)文章源自JAVA秀-https://www.javaxiu.com/20614.html
它负责将给定的key和value对存入HashMap，它的工作主要有以下几个步骤：文章源自JAVA秀-https://www.javaxiu.com/20614.html
如果没有初始化数组，则尝试初始化数组文章源自JAVA秀-https://www.javaxiu.com/20614.html
如果当前正在扩容，则参与帮助扩容(调用helpTransfer()方法)文章源自JAVA秀-https://www.javaxiu.com/20614.html
将给定的key,value 放入对应的槽位文章源自JAVA秀-https://www.javaxiu.com/20614.html
统计元素总数文章源自JAVA秀-https://www.javaxiu.com/20614.html
触发扩容操作文章源自JAVA秀-https://www.javaxiu.com/20614.html
根据以上主要4个步骤，来依次详细说明一下：文章源自JAVA秀-https://www.javaxiu.com/20614.html
如果没有初始化数组，则尝试初始化数组
初始化数据会生成一个Node数组:文章源自JAVA秀-https://www.javaxiu.com/20614.html
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];默认情况下，n为16。同时设置sizeCtl为·n - (n >>> 2); 这意味着sizeCtl为n的75%，表示Map的size，也就是说ConcurrentHashMap的负载因子是0.75。（为了避免冲突，Map的容量是数组的75%，超过这个阈值，就会扩容）文章源自JAVA秀-https://www.javaxiu.com/20614.html
如果当前正在扩容，则参与帮助扩容
else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f);如果一个节点的hash是MOVE，则表示这是一个ForwardingNode，也就是当前正在扩容中，为了尽快完成扩容，当前线程就会参与到扩容的工作中，而不是等待扩容操作完成，如此紧密细致的操作，恰恰是ConcurrentHashMap高性能的原因。文章源自JAVA秀-https://www.javaxiu.com/20614.html
而代码中的f.hash==MOVE语义上等同于f instanceof ForwardingNode，但是使用整数相等的判断的效率要远远高于instanceof，所以，这里也是一处对性能的极限优化。文章源自JAVA秀-https://www.javaxiu.com/20614.html
将给定的key,value 放入对应的槽位
在大部分情况下，应该会走到这一步，也就是将key和value放入数组中。在这个操作中会使用大概如下操作：文章源自JAVA秀-https://www.javaxiu.com/20614.html
Node<K,V> f;synchronized (f) { if(所在槽位是一个链表) 插入链表 else if(所在槽位是红黑树) 插入树 if(链表长度大于8[TREEIFY_THRESHOLD]) 将链表树状化}可以看到，这使用了synchronized关键字，锁住了Node对象。由于在绝大部分情况下，不同线程大概率会操作不同的Node，因此这里的竞争应该不会太大。文章源自JAVA秀-https://www.javaxiu.com/20614.html
并且随着数组规模越来越大，竞争的概率会越来越小，因此ConcurrentHashMap有了极好的并行性。文章源自JAVA秀-https://www.javaxiu.com/20614.html
统计元素总数
为了有一个高性能的size()方法，ConcurrentHashMap使用了单独的方法来统计元素总数，元素数量统计在CounterCell数组中：文章源自JAVA秀-https://www.javaxiu.com/20614.html
CounterCell[] counterCells;@sun.misc.Contended static final class CounterCell { volatile long value; CounterCell(long x) { value = x; }}CounterCell使用伪共享优化，具有很高的读写性能。counterCells中所有的成员的value相加，就是整个Map的大小。这里使用数组，也是为了防止冲突。文章源自JAVA秀-https://www.javaxiu.com/20614.html
如果简单使用一个变量，那么多线程累加一个计数器时，难免要有竞争，现在分散到一个数组中，这种竞争就小了很多，对并发就更加友好了。文章源自JAVA秀-https://www.javaxiu.com/20614.html
累加的主要逻辑如下：文章源自JAVA秀-https://www.javaxiu.com/20614.html
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))) //如果有竞争，在这里会重试，如果竞争严重还会将CounterCell[]数组扩容，以减少竞争触发扩容操作
最后，ConcurrentHashMap还会检查是否需要扩容，它会检查当前Map的大小是否超过了阈值，如果超过了，还会进行扩容。文章源自JAVA秀-https://www.javaxiu.com/20614.html
ConcurrentHashMap的扩容过程非常巧妙，它并没有完全打乱当前已有的元素位置，而是在数组扩容2倍后，将一半的元素移动到新的空间中。文章源自JAVA秀-https://www.javaxiu.com/20614.html
所有的元素根据高位是否为1分为low节点和high节点：文章源自JAVA秀-https://www.javaxiu.com/20614.html
//n是数组长度，数组长度是2的幂次方，因此一定是100 1000 10000 100000这种二进制数字//这里将low节点串一起， high节点串一起if ((ph & n) == 0) ln = new Node<K,V>(ph, pk, pv, ln);else hn = new Node<K,V>(ph, pk, pv, hn);接着，重新放置这些元素的位置：文章源自JAVA秀-https://www.javaxiu.com/20614.html
//low节点留在当前位置setTabAt(nextTab, i, ln);//high节点放到扩容后的新位置，新位置距离老位置nsetTabAt(nextTab, i + n, hn);//扩容完成，用ForwardingNode填充setTabAt(tab, i, fwd);下图显示了 从8扩充到16时的可能得一种扩容情况，注意，新的位置总是在老位置的后面n个槽位（n为原数组大小）文章源自JAVA秀-https://www.javaxiu.com/20614.html
文章源自JAVA秀-https://www.javaxiu.com/20614.html
这样做的好处是，每个元素的位置不需要重新计算，进行查找时，由于总是会对n-1(一定是一个类似于1111 11111 111111这样的二进制数)按位与，因此，high类的节点自然就会出现在+n的位置上。文章源自JAVA秀-https://www.javaxiu.com/20614.html
get()方法的实现
与put()方法相比，get()方法就比较简单了。步骤如下：文章源自JAVA秀-https://www.javaxiu.com/20614.html
根据hash值 得到对应的槽位 (n - 1) & h文章源自JAVA秀-https://www.javaxiu.com/20614.html
如果当前槽位第一个元素key就和请求的一样，直接返回文章源自JAVA秀-https://www.javaxiu.com/20614.html
否则调用Node的find()方法查找文章源自JAVA秀-https://www.javaxiu.com/20614.html
对于ForwardingNode 使用的是 ForwardingNode.find()文章源自JAVA秀-https://www.javaxiu.com/20614.html
对于红黑树 使用的是TreeBin.find()文章源自JAVA秀-https://www.javaxiu.com/20614.html
对于链表型的槽位，依次顺序查找对应的key文章源自JAVA秀-https://www.javaxiu.com/20614.html
写在最后
ConcurrentHashMap可以说是并发设计的典范，在JDK8中，ConcurrentHashMap可以说是再一次脱胎换骨，全新的架构和实现带来了飞一般的体验（JDK7中的ConcurrentHashMap还是采用比较骨板的segment实现的），细细品读，还是有不少的收获。文章源自JAVA秀-https://www.javaxiu.com/20614.html
他和HashMap的区别，优劣势对比，这也是常考的考点，所以大家不管是为了了解、工作还是面试，都应该好好的熟悉一下。文章源自JAVA秀-https://www.javaxiu.com/20614.html
多线程系列我会继续更新，我是敖丙，你知道的越多，你不知道的越多，我们江湖见。文章源自JAVA秀-https://www.javaxiu.com/20614.html
评论