并发编程：ConcurrentHashMap

线程安全的集合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中主要的优化就是分段的思想，里面还加了很多细节上的处理。
分段/分片这种思想在分布式场景也非常常见，不知不觉又发现了其实知识点学到一定程度都是相通的。

红黑树

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

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

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

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