首页 > 其他 > 详细

并发编程:ConcurrentHashMap

时间:2020-07-13 23:55:31      阅读:81      评论:0      收藏:0      [点我收藏+]

线程安全的集合ConcurrentHashMap

JDK1.7和JDK1.8的区别
1、取消了segment分段设计
2、增加了链表转红黑树的设计

基本原理和HashMap差不多,不熟悉的同学可以先去看看HashMap的结构,本文主要看其对并发安全的设计

ConcurrentHashMap中重要的并发方法
  • 初始化table(Node[])数组:初始化使用的是CAS抢占sizeCtl执行权,抢到了之后初始化一个长度为16的数组,并算出下一次扩容的容量为 sizeCtl = cap - cap >>> 2 = cap * 0.75
  • putVal空节点:同样使用了CAS将第一个节点放到对应的下标中(此处检查的时候是get了一个 volatile变量,不是直接检查tab[i]位置,利用了volatile的happens-before规则)
  • putVal结束后addCount:用CounterCell数组来记录容器的长度,分段记录value,然后记录总数的时候会将数组中的value全部加起来。
    记录的流程是先cas baseCount,失败后产生随机数去数组对应下标cas初始化,之后cas增加value。
  • putVal存在的节点:使用synchronized锁定头结点
  • 扩容时先CAS抢占sizeCtl为负数(非-1,-2代表1个线程在扩容,-3代表2个线程在扩容),一看这个标记,惊了。
    还可以多个线程扩容,仔细看,进行了花里胡哨的位运算,高16位代表扩容戳(16的周期内),低16位代表参与的线程数(每2代表1个线程,换成2进制是10代表一个线程)
  • transfer():里面有strider的概念,代表每个CPU分段扩容的数量,然后线程并行扩容,扩容完成之后还要synchronized锁住头节点进行数据搬家,数据搬家的过程和hashmap类似,会用哈希值和旧容量做与运算 即 hash & n , = 0 原位不动, = 1 则 + 原容量到新位置(这里是原理其实就是对新容量的取模,大家可以好好思考思考),不过这里是先准备好链表或红黑树之后才通过CAS迁移,而不用每个Node单独CAS,降低了CAS次数,又是一个优化。

可以看到hashmap中主要的优化就是分段的思想,里面还加了很多细节上的处理。
分段/分片这种思想在分布式场景也非常常见,不知不觉又发现了其实知识点学到一定程度都是相通的。

红黑树

红黑树是一种二叉平衡查找树,它定义了以下规则:

  • 每个节点颜色不是红色就是黑色
  • 根节点是黑色
  • 每个叶子节点是黑色
  • 如果一个节点是红色,那么它的两个子节点都是黑色
  • 从任一节点到其每个叶子的所有简单路径,都包含相同树木的黑色节点

当加入的节点破坏红黑树的关系时,会发生左旋、右旋及重新着色从而达到平衡
左旋:当前节点的右子节点被提起来,当前节点成为其左子节点。旧的右子节点的左子节点成为当前节点的右子节点。
右旋:当前节点的左子节点被提起来,当前节点成为其右子节点。旧的左子节点的右子节点成为当前节点的左子节点。
重新着色:插入节点默认是红色,然后根据平衡规则重新着色。

并发编程:ConcurrentHashMap

原文:https://www.cnblogs.com/fcb-it/p/13296389.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!