4.jpg
前言：
在上一篇文章：Java集合框架—LinkedHashMap—源码研读 中，我们深入学习了LinkedHashMap，现在，让我们开始学习更进阶一点的内容——TreeMap。学习TreeMap前，最好需要先了解一下比较器Comparat、二叉排序树、红黑树据结构的知识。
所以此篇文章，分为3个部分：
1.比较器Comparator和Comparable接口
2.红黑树和二叉排序树
3.红黑树的左旋和右旋
4.TreeMap的源码分析-put()方法、fixAfterInsertion()解读
1.比较器Comparator和Comparable接口
首先，HashMap中的键值对是无序的，LinkedHashMap的出现使得键值对可以按照插入顺序被遍历，但是有很多场景下，我需要根据插入其中的键值对中的key来进行排序，而不是简单的根据插入顺序。那么此时LinkedHashMap便无能为力了！这时，TreeMap就派上了用场，因为TreeMap天生就实现了SortedMap接口，而SortedMap是为了排序而存在的。
让我们先看一下Map接口的关系图和TreeMap的类关系图：
image
image
可见：TreeMap继承自AbstractMap，实现了NavigableMap、Cloneable和Serializable接口。
其中有一点需要注意，NavigableMap继承自SortedMap，而SortedMap接口就是TreeMap中对象有序的核心。
SortedMap接口是干嘛的？简单来说SortedMap接口中包含Comparator比较器，可以自定义比较方法用于实现key的比较。即实现SortedMap的类，其中的对象即可根据比较器中定义的方法，对key进行排序从而达到类中对象有序的目的。
目前java中SortedMap接口的实现类只有TreeMap。如果对Comparable和Comparator还不太熟悉，可以看看下面的内容，否则可以pass掉。
Comparable 和 Comparator的区别：
首先，Comparable和Comparator都是用于比较的接口，全名：java.lang.Comparable 和 java.util.Comparator
Comparable接口主要用于自然比较，里面只有一个方法：public int compareTo(T o);
Integer、String都实现了Comparable接口并实现了接口中的compareTo方法，Integer中的compareTo方法如下：
public int compareTo(Integer anotherInteger) {
return compare(this.value, anotherInteger.value);
}
public static int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}
Comparator主要用于外部定义的比较器，譬如自定义的某个bean对象需要进行比较，那么比较的规则就可以通过Comparator来实现。
详细可以参考:Java 解惑：Comparable 和 Comparator 的区别
说了前面的Comparator其实是为了给今天的主角TreeMap做铺垫，因为TreeMap正是通过比较器Comparator中的方法来实现的排序，从而达到有序的目的。现在让我们看看TreeMap的类定义：
image
private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
private transient int size = 0;
private transient int modCount = 0;
类变量中第一位就是Comparator类的变量comparator，这个comparator即treeMap用于制定排序规则的比较器。root，即treeMap中的根节点；size和modCount我们都已经见过很多次，就不说了。除了类变量外，我们也注意到TreeMap的初始化有4种方式，分别是：
空构造器、定义了comparator的构造方法、初始Map作为参数的构造方法、初始SortedMap作为参数的构造方法。现在，想一下如果初始化时未定义比较器comparator，那么TreeMap还可以正常排序么？如果可以是怎样排序的？
答案是：YES
如果初始未定义比较器，则如果key是Integer、Double、String等已经实现了Comparable接口的类，否则会默认调用其compareTo方法来比较key的大小。
如果key没有实现Comparable接口，则会报ClassCastException异常。
2.红黑树和二叉排序树
红黑树，是一种近似平衡的二叉排序树。
二叉排序树(二叉搜索树)或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。
红黑树，顾名思义，通过给树节点增加一位，颜色属性，来标记节点的颜色。颜色只能为红或者黑色。这些颜色位用于确保树在插入和删除期间保持近似平衡。
让我们看一下维基百科中对【红黑树】规则的讲解：
image
除了对二叉搜索树施加的要求之外，红黑树还必须满足以下要求：[16]
- 每个节点都是红色或黑色。
- 根是黑色的。有时会省略此规则。由于根始终可以从红色变为黑色，但不一定相反，因此该规则对分析几乎没有影响。
- 所有叶子（NIL）都是黑色的。
- 如果节点为红色，则其子节点均为黑色。
- 从给定节点到其任何后代NIL节点的每条路径都包含相同数量的黑色节点。
一些定义：从根到节点的黑色节点数是节点的黑色深度 ; 从根到叶子的所有路径中的黑色节点的统一数量被称为红黑树的黑色高度。[17]
这些约束强制执行红黑树的关键属性：从根到最远叶子的路径不超过从根到最近叶子的路径的两倍。结果是树大致高度平衡。由于诸如插入，删除和查找值之类的操作需要与树的高度成比例的最坏情况时间，因此与最普通的二叉搜索树不同，这种高度的理论上限允许红黑树在最坏的情况下是有效的。
要了解为什么这是有保证的，只需考虑属性4和5的影响就足够了。对于红黑树T，设B为属性5中的黑色节点数。让从T的根到任何叶子的最短可能路径由B个黑色节点组成。可以通过插入红色节点来构造更长的可能路径。但是，属性4使得无法插入多个连续的红色节点。因此，忽略任何黑色NIL叶，最长可能路径包括2 * B节点，交替黑色和红色（这是最坏的情况）。计算黑色NIL叶，最长可能路径由2 * B-1个节点组成。
最短路径具有所有黑色节点，并且最长路径在红色和黑色节点之间交替。由于所有最大路径具有相同数量的黑色节点，因此通过属性5，这表明没有路径是任何其他路径的两倍多。
红黑树，除了定义中规定的要求以外，在Java实现中还增加了如下要求：
1..新插入的节点必须为红色。
2.任意节点其左右子树最多相差2层红节点。
3.插入过程（仅限于插入点那条路径上）中不允许任一节点有2个红色儿子节点。
这些规定使得红黑树的实际表现近似平衡的二叉排序树，即一个n个节点的红黑树，其平均高度为logN,最差情况高度为2log(N+1). 故其查找效率为O(logN)。综合查找、插入和删除节点所引起的时间开销，其实际表现通常优于平衡二叉树。
3.红黑树的左旋和右旋
为什么要介绍红黑树的左旋和右旋操作呢？因为，这是红黑树中最核心的操作，在TreeMap源码中插入或删除红黑树中节点时，可能会引发红黑树结构的变化，那为了重新调整结构变化过的树，使之成为符合红黑树5项要求的树，最重要的操作就是1.改变某些节点的颜色；2.左旋rotateLeft和右旋rotateRight。
改变颜色比较容易，关键在于左旋和右旋操作，下面还是借用一下图片来举例说明，关于红黑树的左旋、右旋等详细过程的图文讲解，部分引用于一篇github上不错的文章：
A.左旋
image
如上图所示，以3号节点为中心的左旋操作，实际上是逆时针旋转，对应的右旋即顺时针旋转。可以想象下，3在左旋逆时针向下的过程中必然会和10号节点左下角的6发生碰撞，结果是3号节点成功上位，成为了10号节点新的左孩子，那么被【碰撞出去】的6号节点只能顺势成为了3号节点的孩子(右孩子)
B.右旋
image
10号节点右旋，即顺时针旋转。旋转到3号节点右下角成为其右孩子。3号节点原本的右孩子6号节点被挤掉，成为了10号节点的左孩子。
4.TreeMap的源码分析-put()方法
在进入put方法前，我们先看一下TreeMap中红黑树Entry节点的定义：
image
如图所示，Entry类的成员变量除了key-value外还有leftt、right用于标记左、右孩子节点；
parent用于标记父节点。boolean类型的color变量用于记录红黑树的颜色BLACK或RED。
OK，现在让我们看一下TreeMap中的put()方法：
image
首先，判断红黑树的root节点，若为空则new一个root节点，将key、value值放置进去。
不空则进入下面：
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
创建一个Comparator比较器变量cpr，这个comparator可以由外部传入，如果不传则为null。
然后：
if (cpr != null) {
...
}
else {...}
如果cpr！=null则进入第一个分支，若cpr==null则进入else分支，由于分支内操作类似，我们以else分支为例看一下操作：
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else分支下首先会进行判断：if (key == null)，如果成立则throw new NullPointerException();
否则创建一个Comparable比较器变量k，值为key。这一步需要注意的是，如果初始没有设置比较器，而且key的类型并没有实现Comparable接口，则会抛出ClassCastException，表示类型转换异常。当然，如果key是Integer,String等实现了Comparable接口，且覆写了compareTo方法的类型，则不会抛异常。
下一步，进入do...while循环中去，循环从根节点开始遍历，直到遍历到叶子节点t = null时跳出，或者找到key值相等的节点t.key= k,则将新value值覆盖原value值后跳出循环。
最后：
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
新建一个红黑树节点e，根据cmp<0或>0来决定将其插入至parent节点的左边或者右边。
插入完成后，调用fixAfterInsertion()方法来判断是否需要对整个红黑树进行结构调整。
为什么需要结构调整？因为红黑树存在是要符合如下要求的：
- 每个节点都是红色或黑色。
- 根是黑色的。有时会省略此规则。由于根始终可以从红色变为黑色，但不一定相反，因此该规则对分析几乎没有影响。
- 所有叶子（NIL）都是黑色的。
- 如果节点为红色，则其子节点均为黑色。
- 从给定节点到其任何后代NIL节点的每条路径都包含相同数量的黑色节点。
新插入的节点默认是黑色的，这样必然会违反第5条原则，故必须通过fixAfterInsertion()来调整。让我们看一下TreeMap中的精髓之一操作红黑树的fixAfterInsertion()方法：
image
直接看代码肯定不容易理解，特别是结合了红黑树的左旋、右旋操作更是容易看晕，所以此处我们还是对着图片讲解，以图(a)中新插入了一个6号节点为例，对着代码看一下红黑树调整的过程。
image
通过代码我们能够看到，情况2其实是落在情况3内的。情况4～情况6跟前三种情况是对称的，因此图解中并没有画出后三种情况，读者可以参考代码自行理解。
到此，我们TreeMap中put()方法的源码就已经分析完成了，红黑树的部分关键在于看图理解，之后再看代码就很清楚了看完文章觉得不错亲盆好友们，麻烦动动小手，点个👍哦，谢谢
网友评论