3.2.2红黑树
先看红黑树的基本概念：红黑树是一课特殊的平衡二叉树，主要用它存储有序的数据，提供高效的数据检索，时间复杂度为O(lgn)。红黑树每个节点都有一个标识位表示颜色，红色或黑色，具备五种特性：
每个节点非红即黑
根节点为黑色
每个叶子节点为黑色。叶子节点为NIL节点，即空节点
如果一个节点为红色，那么它的子节点一定是黑色
从一个节点到该节点的子孙节点的所有路径包含相同个数的黑色节点
对于红黑树而言，它主要包括三个步骤：左旋、右旋、着色。所有不符合上面五个特性的“红黑树”都可以通过这三个步骤调整为正规的红黑树。
3.2.2.1旋转
当对红黑树进行插入和删除操作时可能会破坏红黑树的特性。为了继续保持红黑树的性质，则需要通过对红黑树进行旋转和重新着色处理，其中旋转包括左旋、右旋。
3.2.2.2左旋
左旋示意图如下：
左旋处理过程比较简单，将E的右孩子S调整为E的父节点、S节点的左孩子作为调整后E节点的右孩子。
3.2.2.3右旋
3.2.2.4红黑树插入节点
由于链表转换为红黑树只有添加操作，加上篇幅有限所以这里就只介绍红黑树的插入操作，关于红黑树的详细情况，烦请各位Google。
在分析过程中，我们已下面一颗简单的树为案例，根节点G、有两个子节点P、U，我们新增的节点为N
红黑树默认插入的节点为红色，因为如果为黑色，则一定会破坏红黑树的规则5（从一个节点到该节点的子孙节点的所有路径包含相同个数的黑色节点）。尽管默认的节点为红色，插入之后也会导致红黑树失衡。红黑树插入操作导致其失衡的主要原因在于插入的当前节点与其父节点的颜色冲突导致（红红，违背规则4：如果一个节点为红色，那么它的子节点一定是黑色）。
要解决这类冲突就靠上面三个操作：左旋、右旋、重新着色。由于是红红冲突，那么其祖父节点一定存在且为黑色，但是叔父节点U颜色不确定，根据叔父节点的颜色则可以做相应的调整。
3.2.2.4.1 叔父U节点是红色
如果叔父节点为红色，那么处理过程则变得比较简单了：更换G与P、U节点的颜色，下图（一）。
当然这样变色可能会导致另外一个问题了，就是父节点G与其父节点GG颜色冲突（上图二），那么这里需要将G节点当做新增节点进行递归处理。
3.2.2.4.2 叔父U节点为黑叔
如果当前节点的叔父节点U为黑色，则需要根据当前节点N与其父节点P的位置决定，分为四种情况：
N是P的右子节点、P是G的右子节点
N是P的左子节点，P是G的左子节点
N是P的左子节点，P是G的右子节点
N是P的右子节点，P是G的左子节点
情况1、2称之为外侧插入、情况3、4是内侧插入，之所以这样区分是因为他们的处理方式是相对的。
3.2.2.4.2.1 外侧插入
以N是P的右子节点、P是G的右子节点为例，这种情况的处理方式为：以P为支点进行左旋，然后交换P和G的颜色（P设置为黑色，G设置为红色），如下：
左外侧的情况（N是P的左子节点，P是G的左子节点）和上面的处理方式一样，先右旋，然后重新着色。
3.2.2.4.2.2 内侧插入
以N是P的左子节点，P是G的右子节点情况为例。内侧插入的情况稍微复杂些，经过一次旋转、着色是无法调整为红黑树的，处理方法如下：先进行一次右旋，再进行一次左旋，然后重新着色，即可完成调整。注意这里两次右旋都是以新增节点N为支点不是P。这里将N节点的两个NIL节点命名为X、Y。如下：
至于左内侧则处理逻辑如下：先进行右旋，然后左旋，最后着色。
3.2.2.5红黑树的应用
TreeMap、TreeSet以及JDK1.8之后的HashMap底层都用到了红黑树。
红黑树这么优秀，为何不直接使用红黑树得了？
我们知道红黑树属于（自）平衡二叉树，但是为了保持“平衡”是需要付出代价的，红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，这费事啊。你说说我们引入红黑树就是为了查找数据快，如果链表长度很短的话，根本不需要引入红黑树的，你引入之后还要付出代价维持它的平衡。但是链表过长就不一样了。至于为什么选 8 这个值呢？通过概率统计所得，这个值是综合查询成本和新增元素成本得出的最好的一个值。
3.2.3 put方法
final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); int binCount = 0; for (Node<K, V>[] tab = table;;) { Node<K, V> f; int n, i, fh; if (tab == null || (n = tab.length) == 0) tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //1、如果相应位置的Node还未初始化，则通过CAS插入相应的数据； if (casTabAt(tab, i, null, new Node<K, V>(hash, key, value, null))) break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); else { //2、如果相应位置的Node不为空，且当前该节点不处于移动状态， //则对该节点加synchronized锁，如果该节点的hash不小于0，则遍历链表更新节点或插入新节点； V oldVal = null; synchronized (f) { if (tabAt(tab, i) == f) { if (fh >= 0) { binCount = 1; for (Node<K, V> e = f;; ++binCount) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K, V> pred = e; if ((e = e.next) == null) { pred.next = new Node<K, V>(hash, key, value, null); break; } } //3.如果该节点是TreeBin类型的节点，说明是红黑树结构，则通过putTreeVal方法往红黑树中插入节点； } else if (f instanceof TreeBin) { Node<K, V> p; binCount = 2; if ((p = ((TreeBin<K, V>) f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } //4、如果binCount不为0，说明put操作对数据产生了影响，如果当前链表的个数达到8个， //则通过treeifyBin方法转化为红黑树，如果oldVal不为空， //说明是一次更新操作，没有对元素个数产生影响，则直接返回旧值； if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } //5、如果插入的是一个新节点，则执行addCount()方法尝试更新元素个数baseCount； addCount(1L, binCount); return null; }
详细源码注释可以看
四、参考文章
【死磕Java并发】-----J.U.C之Java并发容器：ConcurrentHashMap_chenssy 的技术博客-CSDN博客
【死磕Java并发】-----J.U.C之ConcurrentHashMap红黑树转换分析_chenssy 的技术博客-CSDN博客_concurrenthashmap转红黑树
