1.8的TreeMap是通过红黑树实现的，下面看看是怎么实现的。
TreeMap初始化的时候会初始化下列参数，第一个Comparator是可以自己定义实现的一个比较的实现，默认为Null,那么默认的比较方式就是compare方法。root默认为Null。其中Entry内部维护了left,right,parent,color 其中color默认是black。
默认构造函数
默认属性
下面我们来看看依次添加会发生哪些变化？
例子1：依次添加1、2、3，从下面的代码可以看到，如果跟节点为空，则直接把第一个对象包装为Entry对象，然后设置为根root，返回null。现在存放第二个对象，此事后显然跟节点不为Null了
设置根节点
添加1完成后的情况如下：
添加节点1并设置为根
跟节点不为null情况下然后我们判断比较对象为不为null，如果不为null，则走下面的方法，如果为null，则走最先的else。默认情况下我们一般都不会去设置设个对象。所以这里不看了。其实流程和默认的是一样的，唯一不同是比较方式不同。
根据自定义的比较方式设置
下面是默认的比较，其实很简单，key不能为null，然后把我们的key强制转换为比Comparable对象，然后先用parent保存t（当前是根节点），对新加入的节点和t的key比较，这里的t其实是始终指向寻位路径的节点，如果比较结果<0则表示比当前节点的key小，然后寻位到左节点，如果>0则寻位到右节点，然后判断是不是Null，如果是null，说明已经找到了该对象应该存放的位置。如果不为Null，然后继续先把该节点保存为parent，然后在比较新加对象和当前节点的大小，然后决定是走左边还是走右边，然后追踪到下一个节点循环追踪，直到该位置为Null为止。
追踪路径过程
找到该位置后，先把传进来的对象包装为entry对象，然后传入父节点(在上一步中始终保存着追踪节点)，然后通过父节点来执行该位置。完成后进入了fixAfterInsertion方法中。这个方法完成了红黑树的自调整。也就是红黑树的核心。
保存节点并设置节点引用关系过程
在fixAfterInsertion方法中，进来后首先把新加入的对象的color设置为红色。由此可见，红黑树的核心是每加入一个新节点首先设置为红色，然后再进行调整。然后再进行判断，节点不为null且节点不是root，且父节点的颜色为红色才进入调整，如果条件不满足直接跳过这个while循环，直接设置根节点为黑色，就完成了添加操作。
判断是否需要调整
始终保持根节点为黑色。
添加了2后的情况如下：
2添加完成
下面看继续添加3：
前序不表，直接看添加后的结果，此时，while里面的判断显然满足了判断条件，父节点为red，进入到循环里面。
添加后未调整前
首先来看进入后的第一个判断，parentOf方法就是返回当前传入对象的父节点，然后leftOf就是返回传入对象的左子节点。此时我们的对象x是新加入的3，从表达式可以看出是在判断x节点的父节点是祖父节点的左子节点还是右子节点，如果是左子节点则进入里面，我们先看看这时候做了些什么。
（如上图）如果判断x节点的父节点是祖父节点的左子节点，则先把右子节点拿到，然后判断右子节点的color是不是红色，如果是，则先把上图中的 左 设置为黑色，然后把 右 设置为黑色，祖父节点设置为红色，然后把当前节点替换为祖父节点。然后while条件判断。
如果是左路径调整方式
如果不是红色，则判断当前节点是不是父节点的右节点，如果是，则把当前节点(指向新加入节点的对象x)指向父节点，然后进入rotateLeft方法进行左旋转，然后在在这个基础上进行颜色改变。这里先不看怎么旋转的。
如果当前节点是父节点的左子节点，则把父节点设置为黑色，祖父节点的右子节点设置为红色，把当前节点(指向新加入节点的对象x)指向祖父节点进入右旋转调整。
上面处理了如果父节点是祖父节点的左子节点的3种情况，第一种：新加入节点的父节点和它的兄弟节点都是红色，第二种新加入节点的父节点是红色，兄弟节点是黑色，它是父节点的右节点，第三种和第二种不同的地方是它是父节点的左节点。
下面看如果父节点是祖父节点右节点的情况：先拿到父节点的兄弟节点(祖父节点的左子节点)，然后判断左子节点是不是红色，如果是红色，则把父节点，祖父节点的左子节点设置为黑色，祖父节点设置为红色，当前节点(原指向新加入节点)指向祖父节点，然后while循环继续调整。如下下图：
父节点红色兄弟节点红色调整方式
如果父节点的兄弟节点不是红色，判断自己是父节点的左节点还是右节点，如果是左节点，把当前节点指向父节点，然后以当前节点为基准进行右旋转，旋转完成后再进行颜色转换在进入左选择。如下图
这种直接进入旋转调整
如果自己是父节点的右子节点，则把父节点设置为黑色，祖父节点设置为红色，然后把当前节点指向祖父节点，进入while循环。
到这里为止，存在的集中可能都已经描述完成了。下面我们看看自旋的2种方式
右自旋的源码
左旋转源码
、我们根据上文中的判断条件分别看都是怎么做的。
1：首先如下图所示
完成一次左旋
继续调整如下图
先改变颜色，然后进入右旋
右旋过程先把p的left指向L的right
最后把P调整为L的right
这样一次调整就完成了。其实这里面需要注意的一点就是，如果新加入的节点的父节点是红色，祖父节点是黑色，且他是父节点的右节点，则先通过一次自旋调整为左节点的做节点红色冲突（这里不管新加入节点是祖父节点P的左子节点PL的任意节点，都需要先调整为P-PL-PL关系）。然后再依次从父节点开始改变颜色，然后右旋。从这里我们可以看到这一个过程的实现其实是，一个已经存在的树P（黑），PL（红），PR（黑）。新加入的节点PLL是PL的左子节点，则这里先把PL变成黑色，P变为红色，然后提升PL到P位置，把P调整为PL的PLR。这样完成了一次调整。文字描述晦涩，配合上图则非常直观。如果新加入节点PLR是PL的右子节点，则先通过自旋调整PL和PLR的关系，调整为PL是PLR的PLL，然后改变PLR的颜色为黑色，P为红色，然后旋转为P为PLR的右节点，PLR到P的位置，这样也完成了一次调整。这里不论图中L的右节点是不是null，其实都不影响整个过程。
下面用图来说明另外一种情况：即新加入的节点N是祖父节点P的右节点PR的子节点。如果是左子节点PRL，则先调整关系为顺线关系也就是P-PR-PR这种模式。
先调整冲突节点为P-PR-PRR模式
然后改变颜色并进行自旋调整
最后改变引用关系完成调整
红黑树的自旋调整基本都是基于这两个关系的。通过这样的调整，保证了红黑树的平衡。在concurrentHashMap中如果总个数超过64，且单个link超过8个则修改为红黑树。s
网友评论