【JDK1.8】JDK1.8集合源码阅读——TreeMap（二）

在前一篇博客中，我们对TreeMap的继承关系进行了分析，在这一篇里，我们将分析TreeMap的数据结构，深入理解它的排序能力是如何实现的。这一节要有一定的数据结构基础，在阅读下面的之前，推荐大家先看一下：《算法4》深入理解红黑树。（个人比较喜欢算法四这里介绍的红黑树实现：从2-3树到红黑树的过渡很清晰，虽然源码里的实现不是这种方式 T^T），先了解一下红黑树的由来以及它的特性，这样能更好的理解TreeMap的实现。

二、 TreeMap的结构

TreeMap的内部实现就是一个红黑树。

对于红黑树的定义：

节点是红色或黑色。

根是黑色。

所有叶子都是黑色（叶子是NIL节点）。

每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）

从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

三、Tree源码解析

在前一篇博客中，我们已经见过了TreeMap的继承关系，所以这里就不重复了，让我们来看一下它的其他内容。

3.1 TreeMap的成员变量

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable { // Key的比较器，用作排序 private final Comparator<? super K> comparator; //树的根节点 private transient Entry<K,V> root; //树的大小 private transient int size = 0; //修改计数器 private transient int modCount = 0; //返回map的Entry视图 private transient EntrySet entrySet; private transient KeySet<K> navigableKeySet; private transient NavigableMap<K,V> descendingMap; //定义红黑树的颜色 private static final boolean RED = false; private static final boolean BLACK = true; }