【原】ConcurrentHashMap的JDK7与JDK8对比学习

ConcurrentHashMap是面试的重点，尤其是jdk7与8的对比，这里进行总结对比学习。

总结对比图

直接上jdk7与jdk8对ConcurrentHashMap底层实现的对比图，对比如下图：

jdk7的ConcurrentHashMap底层结构是Segment数组，可以在初始化的时候指定Segment数组的长度，并且不可变。而Segment继承了ReentrantLock，它存储数据的实现与HashMap很像。也就是说jdk7的ConcurrentHashMap可以看成是由线程安全的HashMap组成的一个map数组，数组的长度决定了支持的最大的并发量。

jdk8的ConcurrentHashMap的底层结构与HashMap又一样了，底层是一个Node的数组，而通过对Node数组以CAS方式实现扩容和对Node数组的每个元素的synchronized保证ConcurrentHashMap整体的线程安全。

jdk8在链表数组结构上进行了优化，与HashMap在jdk8的优化一样，当链表长度达到8的时候会把链表转成红黑树，能够提高查找性能。至于红黑树的特点与优点这里就不扩展了，有兴趣的同学可以网上去了解。

jdk8put方法实现

因为jdk7的ConcurrentHashMap的实现已经过时了，所以这里就不详解了，直接看jdk8的实现，put方法依赖putVal方法，所以直接看putVal方法源码与详解如下图：

可以看到putVal有一点点长，但是也并不复杂，主要分计算hash和一个死循环，所以主要在死循环里面的内容，死循环主要有四种情况：

1、table还没有初始化，所以初始化table，然后进入下次循环；

2、table初始化了,但是hash对应在table中的位置并没有初始化，采用CAS方式把当前要put的值设置进这处，设置失败则进入下次循环，成功则保存成功，退出循环；

3、如果判断有其他线程正在对ConcurrentHashMap扩容，获取要去获取新的tab，进入下次循环；

4、找到了对应节点f，直接对f加synchronized同步，然后判断f节点是链表结构还是红黑树结构，链表结构则遍历链表进行设置，红黑树则采用红黑树设置进去。设置成功后判断是否需要把链表结构转红黑树；

整体来看put方法还是比较简单的死循环加CAS是并发里面的典型应用可以保证table的线程安全，然后找到对应节点f进行同步再次保证每个节点线程安全，所以ConcurrentHashMap支持的最多并发数是table数组长度。

get方法源码

get源码比较简单，源码详解如下图：

get方法的源码还是非常简单的，首先根据hash值找到在table对应处的节点，然后根据节点是红黑树还是链表查找元素，这里有一个小优化是先直接对头结点进行了比对，有可能直接返回，因为如果hash值设计的好的话是很容易比对上的。

jdk7与jdk8实现比较

首先是支持的最大并发度：jdk7是在初始化的时候指定并且不可变，默认16最大32，而jdk8是针对数组中每个元素进行同步，所以数组越大支持的并发也越大。

线程安全实现方式：jdk7是采用Segment继承ReentrantLockt通过锁来实现，而jdk8是通过CAS+synchronized来实现。

hash冲突解决方式：jdk7采用的是链表，而jdk8采用的是链表+红黑树的方式，在hash冲突严重的情况下jdk8的查找效率会更高。

为什么链表长度超过8才转红黑树

首先因为红黑树中节点是TreeBin它继承Node，为了实现红黑树TreeBin需要扩展一些功能，所以TreeBin比Node更占空间。

同时遍历链表的平均查找时间复杂度是 O(n)，红黑树查找的时间复杂度控制在 O(log(n))，在n较小的情况O(n)和 O(log(n)) 差别不大，所以不能直接采用红黑树的方式。

所以能不用还是尽量不要红黑树，那么至于为什么是8呢？

这在ConcurrentHashMap源码中有说明，大概意思是如果hash值设置的好分布很均匀的话，链表一般不会太长（因为达到容量的0.75就扩容了），如果设置转红黑树的链表长度越大转红黑树的概率就越小，通过大量测试当长度为 8 的时候，链表转红黑树的概率仅为 0.00000006，所以采用了8。

同时也说明一般来说是很少情况会出现红黑树结构的，如果出现了一般情况下我们就要考虑是不是我们设计的对象的hash方法有问题！

总结

通过对jdk7与jdk8的ConcurrentHashMap对比学习能够理解更加深入，面试也会经常问这块的相关知识，总结出来以后感觉就很好回答相关问题了。

Java程序员日常学习笔记，如理解有误欢迎各位交流讨论！