ConcurrentHashMap的JDK7与JDK8对比学习

版权声明:本文为作者原创文章,转载请附上原文出处链接和本声明。
本文链接:https://www.weijc.cn/jdetail/380286992660826112

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程序员日常学习笔记,如理解有误欢迎各位交流讨论!

展开阅读全文
还能输入1000个字符