面试必问的JDK 8 ConcurrentHashMap实现原理：数据结构、get操作与put操作

职位：Java软件工程师

这是本人的署名原创文章，未经许可不支持转载，请勿抄袭。本公众号的所有文章均为本人原创。为了更容易理解和记忆，今后所有文章将以图解为主、代码为辅，忽略不太重要的细节，但是保留关键性的技术细节。如果您感兴趣，欢迎关注！

ConcurrentHashMap相信大家都已经知道怎么使用，并且它的源码可以算是JDK 并发包中最长最复杂的了。虽然目前网络上已经有很多分析ConcurrentHashMap实现原理的文章，但大多数都是贴代码，看起来很费劲，也没有把实现原理真正讲清楚。本文将深度解析ConcurrentHashMap实现原理，让人一看就明白。请注意，本文分析的是JDK 8中的ConcurrentHashMap。不要相信那些一文就懂JDK 1.7 和JDK 1.8的文章，因为细节很丰富，一篇文章怎么能覆盖？就算这样的文章写出来了，也是篇幅超长，难以学会。

说明：下文所述的bin、槽位、位置等词语均指代ConcurrentHashMap中的最外层的table数组中的某个元素。

ConcurrentHashMap内部数据结构：基本形态

当hash值冲突较少且当前没有resize操作的时候，ConcurrentHashMap的内部数据结构跟HashMap非常接近，是一个拉链表，即binned(bucketed) hash table。这个拉链表的最外层是一个数组（长度必须是2的n次幂），每个数组元素保存一个单链表的表头。

注意，上图所示拉链表结构是最简单的情况。为了保证线程安全性，对这个结构的读写操作都需要使用volatile、atomic或CAS操作。向这个table的每个空bin（bin指的是数组中的每个元素）插入第一个Node是用CAS操作完成，其次，每个bin中的第一个Node结点作为一个synchronized锁，保护后面的insert, update, remove操作的线程安全性。可见，如果key-value mapping的hash值都被映射到同一个bin，则插入、删除、修改操作都需要加锁，而且这个锁是每个bin链表中的头结点，且使用的是synchronize锁。

说到这里，不得不纠正某些人的错误观点。有一些人反对使用ConcurrentHashMap（包括我公司里的某些人），而且自认为他们了解ConcurrentHashMap。因为上面提到的这个特征，他们就片面认为"向ConcurrentHashMap插入数据有锁操作，所以会影响性能"，这是只知其一、不知其二。实际上，如果key的hash函数的随机化程度足够，锁的问题其实并不大。因为根据JDK官方的统计，hash表中每个bin的结点个数近似服从泊松分布（Poisson distribution），即链表长度的概率大概是

两个线程竞争ConcurrentHashMap中同一个锁的概率是1/8n（n是数组长度，初值等于16）。所以，一开始的竞争概率约0.78%。如果扩容以后，这个概率将会更小。这样小的概率，就害怕到不敢使用吗？除非故意设计成让hash值冲突。

假如hash值真的冲突了，现在JDK8也有应对策略，即下文所介绍内容。

ConcurrentHashMap内部数据结构：红黑树形态

当拉链表数组（table）中的某个bin元素个数太多、链表长度太长之后（前面说过了，这种情况的发生概率只有0.78%），并且hash表的Key实现了Comparable接口，原来的单链表结构被转换成红黑树，如下图所示：

需要注意，并非当bin中链表长度足够长就马上转换成红黑树，还需要等table数组的长度也到达某个阈值才会转换成树。如果某个bin的长度太长，但是table数组长度较短，则只会先触发resize扩容。另外，顺便说一下，JDK 8的HashMap针对bin中的单链表过长的问题，也是将它转换为红黑树来处理的。

ConcurrentHashMap内部数据结构：转移节点形态

当有resize操作在进行中的时候，已经转移到新数组的bin原来的位置被放进一个ForwardingNode结点。这保证了有resize操作正在进行中的时候，不会阻塞对ConcurrentHashMap的读操作。例如，如果有一个调用get操作的线程，它的key的hash码映射到了一个ForwardingNode，那么它会从这个ForwadingNode结点中的nextTable字段找到新数组的引用，然后再找到新数组nextTable的对应bin。

另外，数组table除了可以存放Node, TreeBin和ForwadingNode之外，还可以存放一种特殊类型的结点ReservationNode，它主要是用来帮助实现Java 8的新增API ConcurrentHashMap.comptuteIfAbsent的，不影响我们分析ConcurrentHashMap的主体实现，今后将会撰文解析。

ConcurrentHashMap的get操作

你可能以为get操作需要实现线程安全性，所以它的实现会很复杂吧？其实，JDK 8中的ConcurrentHashMap的get操作非常简单。相关变量都加上了volatile修饰，所以get操作自身几乎无需考虑线程安全性和变量可见性，只需要注意原子性。这里的原子性指的是，get操作中的被多个线程共享的table变量及节点属性等可能也在被其他线程修改，所以需要一开始就把它们保存到局部变量，然后再使用，这样就不必担心有其他线程修改了。get操作的主体逻辑用伪代码说明如下（个人认为比流程图或直接贴代码清晰）：

解释一下，"简单处理"指的是对key的原始hashCode进行一些简单的位变换（解决hashCode高比特位没有使用的问题），"h & (n – 1)"中的n是table的长度，因为n一定是2的幂，那么n-1刚好是掩码，用来与h进行位运算后刚好是table的下标。table[idx]的hash值小于0表示这个节点不是单链表（Node），而是其他类型的节点，比如ForwadingNode（需要到新table中继续查找）、TreeBin（用红黑树算法搜索）或ReservationNode（直接返回null）。

ConcurrentHashMap的put操作

put操作既需要到ConcurrentHashMap中查询有没有对应的key，还需要写入key-value，并且保证多线程写入的线程安全性，并且还会参与到可能正在进行中的resize操作。那么如何实现呢？我们用伪代码描述如下（如果需要了解非常细节的地方，还需查看源码，若只想明白原理，看伪代码足矣）：

理解上述put操作过程要注意，只有在执行到break之后才会跳出循环，没有遇到break则会重试。JDK代码的重试功能几乎全部是用死循环来实现的。

从以上执行过程可以看出，put操作的线程安全性是利用"分类讨论"方法保证的。或者说，分情况处理，即只有在需要的时候才加锁、不需要的时候不加锁，而JDK 7则是每次在一个segment中写入都要加锁。分成的情况：

1. 如果位置上是空的（null），那么用cas操作来保证线程安全性。
2. 如果这个位置是ForwardingNode，则执行一部分transfer工作，然后在新table中重试。
3. 如果这个位置是单链表或红黑树，那么才进行加锁。

这里之所以用synchronized锁，而不用ReentrantLock是因为JVM对于synchronized有许多优化，在没有竞争的时候，synchronized性能优于ReentrantLock显式锁（例如锁消除、偏向锁、自旋等优化措施）。关于ConcurrentHashMap的分析尚未全部覆盖，其扩容、计数器优化、遍历优化等内容且看下回分解。如果您感兴趣，欢迎关注。