java 集合系列目录：
Java 集合系列 03 ArrayList详细介绍(源码解析)和使用示例
Java 集合系列 04 LinkedList详细介绍(源码解析)和使用示例
Java 集合系列 05 Vector详细介绍(源码解析)和使用示例
Java 集合系列 06 Stack详细介绍(源码解析)和使用示例
Java 集合系列 07 List总结(LinkedList, ArrayList等使用场景和性能分析)
Java 集合系列 09 HashMap详细介绍(源码解析)和使用示例
Java 集合系列 10 Hashtable详细介绍(源码解析)和使用示例
Java 集合系列 11 hashmap 和 hashtable 的区别
概要
5.1 TreeMap的Entry相关函数
5.2 TreeMap的key相关函数
5.3 TreeMap的values()函数
5.4 TreeMap的entrySet()函数
5.5 TreeMap实现的Cloneable接口
5.6 TreeMap实现的Serializable接口
5.7 TreeMap实现的NavigableMap接口
第1部分 红黑树简介
TreeMap的实现是红黑树算法的实现，所以要了解TreeMap就必须对红黑树有一定的了解,其实这篇博文的名字叫做：根据红黑树的算法来分析TreeMap的实现，但是为了与Java提高篇系列博文保持一致还是叫做TreeMap比较好。通过这篇博文你可以获得如下知识点：
1、红黑树的基本概念。
2、红黑树增加节点、删除节点的实现过程。
3、红黑树左旋转、右旋转的复杂过程。
4、Java 中TreeMap是如何通过put、deleteEntry两个来实现红黑树增加、删除节点的。
下面先简单普及红黑树知识。
红黑树又称红-黑二叉树，它首先是一颗二叉树，它具体二叉树所有的特性。同时红黑树更是一颗自平衡的排序二叉树。
我们知道一颗基本的二叉树他们都需要满足一个基本性质--即树中的任何节点的值大于它的左子节点，且小于它的右子节点。按照这个基本性质使得树的检索效率大大提高。我们知道在生成二叉树的过程是非常容易失衡的，最坏的情况就是一边倒（只有右/左子树），这样势必会导致二叉树的检索效率大大降低（O(n)），所以为了维持二叉树的平衡，大牛们提出了各种实现的算法，如：AVL，SBT，伸展树，TREAP ，红黑树等等。
平衡二叉树必须具备如下特性：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。也就是说该二叉树的任何一个等等子节点，其左右子树的高度都相近。
红黑树顾名思义就是节点是红色或者黑色的平衡二叉树，它通过颜色的约束来维持着二叉树的平衡。对于一棵有效的红黑树二叉树而言我们必须增加如下规则：
1、每个节点都只能是红色或者黑色
2、根节点是黑色
3、每个叶节点（NIL节点，空节点）是黑色的。
4、如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。所以红黑树它是复杂而高效的，其检索效率O(log n)。下图为一颗典型的红黑二叉树。
对于红黑二叉树而言它主要包括三大基本操作：左旋、右旋、着色。
左旋 右旋
（图片来自：http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html）
注：由于本文主要是讲解Java中TreeMap，所以并没有对红黑树进行非常深入的了解和研究，如果诸位想对其进行更加深入的研究提供几篇较好的博文：
1、红黑树系列集锦
3、红黑树
第2部分 TreeMap数据结构
TreeMap的定义如下：
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
TreeMap与Map关系如下图：
从图中可以看出：
(01) TreeMap实现继承于AbstractMap，并且实现了NavigableMap接口。
(02) TreeMap的本质是R-B Tree(红黑树)，它包含几个重要的成员变量： root, size, comparator。
root 是红黑数的根节点。它是Entry类型，Entry是红黑数的节点，它包含了红黑数的6个基本组成成分：key(键)、value(值)、left(左孩子)、right(右孩子)、 parent(父节点)、color(颜色)。Entry节点根据key进行排序，Entry节点包含的内容为value。
红黑数排序时，根据Entry中的key进行排序；Entry中的key比较大小是根据比较器comparator来进行判断的。
size是红黑数中节点的个数。
TreeMap继承AbstractMap，实现NavigableMap、Cloneable、Serializable三个接口。其中AbstractMap表明TreeMap为一个Map即支持key-value的集合， NavigableMap（更多）则意味着它支持一系列的导航方法，具备针对给定搜索目标返回最接近匹配项的导航方法 。
TreeMap中同时也包含了如下几个重要的属性：
//比较器，因为TreeMap是有序的，通过comparator接口我们可以对TreeMap的内部排序进行精密的控制
private final Comparator<? super K> comparator;
//TreeMap红-黑节点，为TreeMap的内部类
private transient Entry<K,V> root = null;
//容器大小
private transient int size = 0;
//TreeMap修改次数
private transient int modCount = 0;
//红黑树的节点颜色--红色
private static final boolean RED = false;
//红黑树的节点颜色--黑色
private static final boolean BLACK = true;
对于叶子节点Entry是TreeMap的内部类，它有几个重要的属性：
//键
K key;
//值
V value;
//左孩子
Entry<K,V> left = null;
//右孩子
Entry<K,V> right = null;
//父亲
Entry<K,V> parent;
//颜色
boolean color = BLACK;
在下面两节我将重点讲解treeMap的put()、delete()方法。通过这两个方法我们会了解红黑树增加、删除节点的核心算法。
第3部分 TreeMap put()方法
3.1 TreeMap put()方法分析
在了解TreeMap的put()方法之前，我们先了解红黑树增加节点的算法。
红黑树在新增节点过程中比较复杂，复杂归复杂它同样必须要依据上面提到的五点规范，同时由于规则1、2、3基本都会满足，下面我们主要讨论规则4、5。假设我们这里有一棵最简单的树，我们规定新增的节点为N、它的父节点为P、P的兄弟节点为U、P的父节点为G。
对于新节点的插入有如下三个关键地方：
1、插入新节点总是红色节点 。
2、如果插入节点的父节点是黑色, 能维持性质 。
3、如果插入节点的父节点是红色, 破坏了性质. 故插入算法就是通过重新着色或旋转, 来维持性质 。
为了保证下面的阐述更加清晰和根据便于参考，我这里将红黑树的五点规定再贴一遍：
1、每个节点都只能是红色或者黑色
2、根节点是黑色
3、每个叶节点（NIL节点，空节点）是黑色的。
4、如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
一、被插入的节点是根节点。
若新插入的节点N没有父节点，则直接当做根据节点插入即可，同时将颜色设置为黑色。（如图一（1））
二、被插入的节点的父节点是黑色。
这种情况新节点N同样是直接插入，同时颜色为红色，由于根据规则四它会存在两个黑色的叶子节点，值为null。同时由于新增节点N为红色，所以通过它的子节点的路径依然会保存着相同的黑色节点数，同样满足规则5。（如图一（2））
三、被插入的节点的父节点是红色。
穷举下一下几类，就可以画出下面的情况：
对于上述五种情况，列表给出每种的解决方法：
| 叔叔为红 | x父=黑； | |
| x叔=黑； | ||
| x祖=红； | ||
| x祖为新节点； | ||
| 叔叔为黑 | P为左，X为左 | 设x父为黑； |
| 设x祖为红； | ||
| 以x祖右旋； | ||
| P为左，X为右 | x=x的父； | |
| 以x左旋； | ||
| 设x父为黑； | ||
| 设x祖为红； | ||
| 以x祖右旋； | ||
| P为右，X为右 | x的父=黑； | |
| X的祖= 红； | ||
| 左旋（X的祖）； | ||
| P为右，X为左 | x=x的父； | |
| 右旋（X）； | ||
| x的父=黑； | ||
| X的祖= 红； | ||
| 左旋（X的祖）； | ||
上面展示了红黑树新增节点的五种情况，这五种情况涵盖了所有的新增可能，不管这棵红黑树多么复杂，都可以根据这五种情况来进行生成。下面就来分析Java中的TreeMap是如何来实现红黑树的。
下面图表示：
3.2 TreeMap put()代码
在TreeMap的put()的实现方法中主要分为两个步骤，第一：构建排序二叉树，第二：平衡二叉树。
对于排序二叉树的创建，其添加节点的过程如下：
1、以根节点为初始节点进行检索。
2、与当前节点进行比对，若新增节点值较大，则以当前节点的右子节点作为新的当前节点。否则以当前节点的左子节点作为新的当前节点。
3、循环递归2步骤知道检索出合适的叶子节点为止。
4、将新增节点与3步骤中找到的节点进行比对，如果新增节点较大，则添加为右子节点；否则添加为左子节点。
按照这个步骤我们就可以将一个新增节点添加到排序二叉树中合适的位置。如下：
public V put(K key, V value) {
//用t表示二叉树的当前节点
Entry<K,V> t = root;
//t为null表示一个空树，即TreeMap中没有任何元素，直接插入
if (t == null) {
compare(key, key); // type (and possibly null) check
//将新的key-value键值对创建为一个Entry节点，并将该节点赋予给root
root = new Entry<>(key, value, null);
//容器的size = 1，表示TreeMap集合中存在一个元素
size = 1;
//修改次数 + 1
modCount++;
return null;
}
//cmp表示key排序的返回结果
int cmp;
Entry<K,V> parent; //父节点
// split comparator and comparable paths
//指定的排序算法
Comparator<? super K> cpr = comparator;
//如果cpr不为空，则采用既定的排序算法进行创建TreeMap集合
if (cpr != null) {
do {
parent = t;//parent指向上次循环后的t
//比较新增节点的key和当前节点key的大小
cmp = cpr.compare(key, t.key);
//cmp返回值小于0，表示新增节点的key小于当前节点的key，则以当前节点的左子节点作为新的当前节点
if (cmp < 0)
t = t.left;
//cmp返回值大于0，表示新增节点的key大于当前节点的key，则以当前节点的右子节点作为新的当前节点
else if (cmp > 0)
t = t.right;
//cmp返回值等于0，表示两个key值相等，则新值覆盖旧值，并返回新值
else
return t.setValue(value);
} while (t != null);
}
//如果cpr为空，则采用默认的排序算法进行创建TreeMap集合
else {
//key值为空抛出异常
if (key == null)
throw new NullPointerException();
//下面处理过程和上面一样
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);
}
//将新增节点当做parent的子节点
Entry<K,V> e = new Entry<>(key, value, parent);
//如果新增节点的key小于parent的key，则当做左子节点
if (cmp < 0)
parent.left = e;
//如果新增节点的key大于parent的key，则当做右子节点
else
parent.right = e;
/**
* 上面已经完成了排序二叉树的的构建，将新增节点插入该树中的合适位置
* 下面fixAfterInsertion()方法就是对这棵树进行调整、平衡，具体过程参考上面的五种情况
*/
fixAfterInsertion(e);
//TreeMap元素数量 + 1
size++;
//TreeMap容器修改次数 + 1
modCount++;
return null;
}
上面代码中do{}代码块是实现排序二叉树的核心算法，通过该算法我们可以确认新增节点在该树的正确位置。找到正确位置后将插入即可，这样做了其实还没有完成，因为我知道TreeMap的底层实现是红黑树，红黑树是一棵平衡排序二叉树，普通的排序二叉树可能会出现失衡的情况，所以下一步就是要进行调整。fixAfterInsertion(e); 调整的过程务必会涉及到红黑树的左旋、右旋、着色三个基本操作。代码如下：
private void fixAfterInsertion(Entry<K,V> x) {
//新增节点的颜色为红色
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {
//如果X的父节点（P）是其祖父节点（G）的左节点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//获取X的叔节点y(U)
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//如果X的叔节点（U） 为红色（case1）
if (colorOf(y) == RED) {
//将“父节点”设为黑色。
setColor(parentOf(x), BLACK);
//将“叔叔节点”设为黑色。
setColor(y, BLACK);
//将“祖父节点”设为红色。
setColor(parentOf(parentOf(x)), RED);
//将“祖父节点”设为“当前节点”(红色节点)
x = parentOf(parentOf(x));
} else {//如果X的叔节点（U） 为黑色
//如果X节点为其父节点（P）的右子树，则进行左旋转
if (x == rightOf(parentOf(x))) {
//将X的父节点作为X
x = parentOf(x);
//左旋转
rotateLeft(x);
}
//将X的父节点（P）设置为黑色
setColor(parentOf(x), BLACK);
//将X的祖父节点（G）设置红色
setColor(parentOf(parentOf(x)), RED);
//以X的祖父节点（G）为中心右旋转
rotateRight(parentOf(parentOf(x)));
}
} else {//如果X的父节点（P）是其父节点的父节点（G）的右节点
//获取X的叔节点y（U）
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
//如果X的叔节点（U） 为红色
if (colorOf(y) == RED) {
//将X的父节点（P）设置为黑色
setColor(parentOf(x), BLACK);
//将X的叔节点（U）设置为黑色
setColor(y, BLACK);
//将X的祖父节点（G）设置红色
setColor(parentOf(parentOf(x)), RED);
//x设为x的祖父节点
x = parentOf(parentOf(x));
} else {//如果X的叔节点（U为黑色
//如果X节点为其父节点（P）的左子树
if (x == leftOf(parentOf(x))) {
//将X的父节点作为X
x = parentOf(x);
//右旋转
rotateRight(x);
}
//将X的父节点（P）设置为黑色
setColor(parentOf(x), BLACK);
//将X的祖父节点（G）设置红色
setColor(parentOf(parentOf(x)), RED);
//以X的祖父点（G）为中心左旋转
rotateLeft(parentOf(parentOf(x)));
}
}
}
//将根节点G强制设置为黑色
root.color = BLACK;
}
对这段代码的研究我们发现,其处理过程完全符合红黑树新增节点的处理过程。所以在看这段代码的过程一定要对红黑树的新增节点过程有了解。在这个代码中还包含几个重要的操作。左旋(rotateLeft())、右旋（rotateRight()）、着色（setColor()）。
左旋：rotateLeft()
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
//获取P的右子节点，其实这里就相当于新增节点N
Entry<K,V> r = p.right;
//将R的左子树设置为P的右子树
p.right = r.left;
//若R的左子树不为空，则将P设置为R左子树的父亲
if (r.left != null)
r.left.parent = p;
//将P的父亲设置R的父亲
r.parent = p.parent;
//如果P的父亲为空，则将R设置为跟节点
if (p.parent == null)
root = r;
//如果P为其父节点（G）的左子树，则将R设置为P父节点(G)左子树
else if (p.parent.left == p)
p.parent.left = r;
//否则R设置为P的父节点（G）的右子树
else
p.parent.right = r;
//将P设置为R的左子树
r.left = p;
//将R设置为P的父节点
p.parent = r;
}
}
右旋：rotateRight()
private void rotateRight(Entry<K,V> p) {
if (p != null) {
//将L设置为P的左子树
Entry<K,V> l = p.left;
//将L的右子树设置为P的左子树
p.left = l.right;
//若L的右子树不为空，则将P设置L的右子树的父节点
if (l.right != null) l.right.parent = p;
//将P的父节点设置为L的父节点
l.parent = p.parent;
//如果P的父节点为空，则将L设置根节点
if (p.parent == null)
root = l;
//若P为其父节点的右子树，则将L设置为P的父节点的右子树
else if (p.parent.right == p)
p.parent.right = l;
//否则将L设置为P的父节点的左子树
else p.parent.left = l;
//将P设置为L的右子树
l.right = p;
//将L设置为P的父节点
p.parent = l;
}
}
左旋、右旋的示意图如下：
（左旋） （右旋）
（图片来自：http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html）
着色：setColor()
着色就是改变该节点的颜色，在红黑树中，它是依靠节点的颜色来维持平衡的。
private static <K,V> void setColor(Entry<K,V> p, boolean c) {
if (p != null)
p.color = c;
}
第4部分 TreeMap delete()方法
4.1 TreeMap delete()方法分析
红黑树删除节点
针对于红黑树的增加节点而言，删除显得更加复杂，使原本就复杂的红黑树变得更加复杂。同时删除节点和增加节点一样，同样是找到删除的节点，删除之后调整红黑树。但是这里的删除节点并不是直接删除，而是通过走了“弯路”通过一种捷径来删除的：找到被删除的节点D的子节点F，用F来替代D，不是直接删除D，因为D被F替代了，直接删除F即可。所以这里就将删除父节点D的事情转变为了删除子节点F的事情，这样处理就将复杂的删除事件简单化了。子节点F的规则是：如果有右分支，则是右分支最左边，否则，是左分支最右边的。
红-黑二叉树删除节点，最大的麻烦是要保持 各分支黑色节点数目相等。 因为是删除，所以不用担心存在颜色冲突问题——插入才会引起颜色冲突。
红黑树删除节点同样会分成几种情况，这里是按照待删除节点有几个儿子的情况来进行分类：
1、没有儿子，即为叶结点。直接把父结点的对应儿子指针设为NULL，删除儿子结点就OK了。
2、只有一个儿子。那么把父结点的相应儿子指针指向儿子的独生子，删除儿子结点也OK了。
3、有两个儿子。这种情况比较复杂，但还是比较简单。上面提到过用子节点C替代代替待删除节点D，然后删除子节点C即可。
下面就论各种删除情况来进行图例讲解，请时刻牢记红黑树的5点规定：
1、每个节点都只能是红色或者黑色
2、根节点是黑色
3、每个叶节点（NIL节点，空节点）是黑色的。
4、如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
删除节点比较复杂，那么在这里我们就约定一下规则：
1、下面要讲解的删除节点一定是实际要删除节点的后继节点（N），如前面提到的C。
2、下面提到的删除节点的树都是如下结构，该结构所选取的节点是待删除节点的右树的最左边子节点。这里我们规定真实删除节点为N、父节点为P、兄弟节点为W兄弟节点的两个子节点为X1、X2。如下图（2.1）。
现在我们就上面提到的三种情况进行分析、处理。
情况一、无子节点（红色节点）
这种情况对该节点直接删除即可，不会影响树的结构。因为该节点为叶子节点它不可能存在子节点-----如子节点为黑，则违反黑节点数原则（规定5），为红，则违反“颜色”原则（规定4）。 如上图（2.2）。
情况二、有一个子节点
这种情况处理也是非常简单的，用子节点替代待删除节点，然后删除子节点即可。如上图（2.3）
情况三、有两个子节点
这种情况可能会稍微有点儿复杂。它需要找到一个替代待删除节点（N）来替代它，然后删除N即可。它主要分为四种情况。
1、N的兄弟节点W为红色
2、N的兄弟w是黑色的，且w的俩个孩子都是黑色的。
3、N的兄弟w是黑色的，w的左孩子是红色，w的右孩子是黑色。
4、N的兄弟w是黑色的，且w的右孩子时红色的。
情况3.1、N的兄弟节点W为红色
W为红色，那么其子节点X1、X2必定全部为黑色，父节点P也为黑色。
处理策略是：(01) 将x的兄弟节点W设为“黑色”。(02) 将x的父节点P设为“红色”。(03) 对x的父节点P进行左旋。(04) 左旋后，重新设置x的兄弟节点。（即：将X的父节点的右孩子设为新的兄弟节点W）
情况3.2、N的兄弟w是黑色的，且w的俩个孩子都是黑色的。
处理策略是：(01) 将x的兄弟节点设为“红色”。(02) 设置“x的父节点”为“新的x节点”。
情况3.3、N的兄弟w是黑色的，w的左孩子是红色，w的右孩子是黑色。
针对这种情况是将节点W和其左子节点进行颜色交换，然后对W进行右旋转处理
处理策略是：
(01) 将x兄弟节点的左孩子X1设为“黑色”。(02) 将x兄弟节点W设为“红色”。(03) 对x的兄弟节点W进行右旋。(04) 右旋后，重新设置x的兄弟节点。（即：将X的父节点的右孩子设为新的兄弟节点）
情况3.4、N的兄弟w是黑色的，且w的右孩子时红色的。
交换W和父节点P的颜色，同时对P进行左旋转操作。这样就把左边缺失的黑色节点给补回来了。同时将W的右子节点X2置黑。这样左右都达到了平衡。
处理策略是：
(01) 将x父节点P颜色赋值给 x的兄弟节点W。(02) 将x父节点P设为“黑色”。(03) 将x兄弟节点的右子节X2设为“黑色”。(04) 对x的父节点P进行左旋。(05) 设置“x”为“根节点”。
上述各种操作完成，最后都要把X设为黑色。
下面列表给出每种情况以及解决方法：
| 现象说明 | 处理策略 | |
| Case 1 | x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。 | (01) 将x的兄弟节点设为“黑色”。 |
| (02) 将x的父节点设为“红色”。 | ||
| (03) 对x的父节点进行左旋。 | ||
| (04) 左旋后，重新设置x的兄弟节点。 | ||
| Case 2 | x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。 | (01) 将x的兄弟节点设为“红色”。 |
| (02) 设置“x的父节点”为“新的x节点”。 | ||
| Case 3 | x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。 | (01) 将x兄弟节点的左孩子设为“黑色”。 |
| (02) 将x兄弟节点设为“红色”。 | ||
| (03) 对x的兄弟节点进行右旋。 | ||
| (04) 右旋后，重新设置x的兄弟节点。 | ||
| Case 4 | x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色。 | (01) 将x父节点颜色 赋值给 x的兄弟节点。 |
| (02) 将x父节点设为“黑色”。 | ||
| (03) 将x兄弟节点的右子节设为“黑色”。 | ||
| (04) 对x的父节点进行左旋。 | ||
| (05) 设置“x”为“根节点”。 |
4.2 TreeMap delete()代码
/**
* Delete node p, and then rebalance the tree.
*/
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--; /*
* 被删除节点的左子树和右子树都不为空，那么就用 p节点的中序后继节点代替 p 节点
* successor(P)方法为寻找P的替代节点。规则是右分支最左边，或者 左分支最右边的节点
*
*/
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children //replacement为替代节点，如果P的左子树存在那么就用左子树替代，否则用右子树替代
Entry<K,V> replacement = (p.left != null ? p.left : p.right); //如果替代节点不为空
if (replacement != null) {
// Link replacement to parent
/*
*replacement来替代P节点
*/
//若P没有父节点，则跟节点直接变成replacement
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
//如果P为左节点，则用replacement来替代为左节点
else if (p == p.parent.left)
p.parent.left = replacement;
//如果P为右节点，则用replacement来替代为右节点
else
p.parent.right = replacement; // Null out links so they are OK to use by fixAfterDeletion.
p.left = p.right = p.parent = null; /*
* 若P为红色直接删除，红黑树保持平衡
* 但是若P为黑色，则需要调整红黑树使其保持平衡
*/
// Fix replacement
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node. p没有父节点，表示为P根节点，直接删除即可
root = null;
} else { // No children. Use self as phantom replacement and unlink.
if (p.color == BLACK)
fixAfterDeletion(p); //删除P节点
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
寻找替代节点replacement，其实现方法为successor()，即寻找中序后继节点。如下：
/**
* Returns the successor of the specified Entry, or null if no such.
*/
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
删除完节点后，就要根据情况来对红黑树进行复杂的调整：fixAfterDeletion()。
private void fixAfterDeletion(Entry<K,V> x) {
// 删除节点需要一直迭代，知道 直到 x 不是根节点，且 x 的颜色是黑色
while (x != root && colorOf(x) == BLACK) {
//若X节点为左节点
if (x == leftOf(parentOf(x))) {
//获取其兄弟节点
Entry<K,V> sib = rightOf(parentOf(x));
//如果兄弟节点为红色----（情况3.1）
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
//兄弟节点为黑色
//兄弟节点的左右子节点都是黑色----（情况3.2）
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
//兄弟节点的只有右子节点为黑色，左子节点为红色----(情况3.3)
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
//兄弟节点的右子节点是红色----(情况3.4)
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // 对称的，X节点为右节点与其为做节点处理过程差不多，这里就不在累述了
Entry<K,V> sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
第5部分 TreeMap的相关函数
5.1 TreeMap的Entry相关函数
TreeMap的 firstEntry()、 lastEntry()、 lowerEntry()、 higherEntry()、 floorEntry()、 ceilingEntry()、 pollFirstEntry() 、 pollLastEntry() 原理都是类似的；下面以firstEntry()来进行详细说明
我们先看看firstEntry()和getFirstEntry()的代码：
public final Map.Entry<K,V> firstEntry() {
return exportEntry(subLowest());
}
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
从中，我们可以看出 firstEntry() 和 getFirstEntry() 都是用于获取第一个节点。
但是，firstEntry() 是对外接口； getFirstEntry() 是内部接口。而且，firstEntry() 是通过 getFirstEntry() 来实现的。那为什么外界不能直接调用 getFirstEntry()，而需要多此一举的调用 firstEntry() 呢?
这么做的目的是：防止用户修改返回的Entry。getFirstEntry()返回的Entry是可以被修改的，但是经过firstEntry()返回的Entry不能被修改，只可以读取Entry的key值和value值。下面我们看看到底是如何实现的。
(01) getFirstEntry()返回的是Entry节点，而Entry是红黑树的节点，然后可以调用Entry的getKey()、getValue()来获取key和value值，以及调用setValue()来修改value的值。
(02) firstEntry()返回的是exportEntry(getFirstEntry())。
/**
* Return SimpleImmutableEntry for entry, or null if null
*/
static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
return (e == null) ? null :
new AbstractMap.SimpleImmutableEntry<>(e);
}
实际上，exportEntry() 是新建一个AbstractMap.SimpleImmutableEntry类型的对象，并返回。
SimpleImmutableEntry的实现在AbstractMap.java中，下面我们看看AbstractMap.SimpleImmutableEntry是如何实现的，代码如下：
public static class SimpleImmutableEntry<K,V>
implements Entry<K,V>, java.io.Serializable
{
private static final long serialVersionUID = 7138329143949025153L; private final K key;
private final V value; public SimpleImmutableEntry(K key, V value) {
this.key = key;
this.value = value;
} public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) {
this.key = entry.getKey();
this.value = entry.getValue();
} public K getKey() {
return key;
} public V getValue() {
return value;
} public V setValue(V value) {
throw new UnsupportedOperationException();
} public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
return eq(key, e.getKey()) && eq(value, e.getValue());
} public int hashCode() {
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
} public String toString() {
return key + "=" + value;
} }
从中，我们可以看出SimpleImmutableEntry实际上是简化的key-value节点。
它只提供了getKey()、getValue()方法类获取节点的值；但不能修改value的值，因为调用 setValue() 会抛出异常UnsupportedOperationException();
再回到我们之前的问题：那为什么外界不能直接调用 getFirstEntry()，而需要多此一举的调用 firstEntry() 呢?
现在我们清晰的了解到：
(01) firstEntry()是对外接口，而getFirstEntry()是内部接口。
(02) 对firstEntry()返回的Entry对象只能进行getKey()、getValue()等读取操作；而对getFirstEntry()返回的对象除了可以进行读取操作之后，还可以通过setValue()修改值。
5.2 TreeMap的key相关函数
TreeMap的firstKey()、lastKey()、lowerKey()、higherKey()、floorKey()、ceilingKey()原理都是类似的；下面以ceilingKey()来进行详细说明
ceilingKey(K key)的作用是“返回大于/等于key的最小的键值对所对应的KEY，没有的话返回null”，它的代码如下：
public K ceilingKey(K key) {
return keyOrNull(getCeilingEntry(key));
}
ceilingKey()是通过getCeilingEntry()实现的。其中keyOrNull()的代码很简单，它是获取节点的key，没有的话，返回null。
static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
return (e == null) ? null : e.key;
}
getCeilingEntry(K key)的作用是“返回大于等于给定键的最小键；如果不存在这样的键，则返回 null。”。它的实现代码如下：
final Entry<K,V> getCeilingEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
// 情况一：若“p的key” > key。
// 若 p 存在左孩子，则设 p=“p的左孩子”；
// 否则，返回p
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
} else if (cmp > 0) {// 情况二：若“p的key” < key。
// 若 p 存在右孩子，则设 p=“p的右孩子”
if (p.right != null) {
p = p.right;
} else {
// 若 p 不存在右孩子，则找出 p 的后继节点，并返回
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
} else // 情况三：若“p的key” = key。
return p;
}
return null;
}
5.3 TreeMap的values()函数
values() 返回“TreeMap中值的集合”
values()的实现代码如下：
public Collection<V> values() {
Collection<V> vs = values;
return (vs != null) ? vs : (values = new Values());
}
说明：values()是通过 new Values() 来实现 “返回TreeMap中值的集合”。
那么Values()是如何实现的呢？ 没错！由于返回的是值的集合，那么Values()肯定返回一个集合；而Values()正好是集合类Value的构造函数。Values继承于AbstractCollection，它的代码如下：
class Values extends AbstractCollection<V> {
// 返回迭代器
public Iterator<V> iterator() {
return new ValueIterator(getFirstEntry());
}
// 返回个数
public int size() {
return TreeMap.this.size();
}
// "TreeMap的值的集合"中是否包含"对象o"
public boolean contains(Object o) {
return TreeMap.this.containsValue(o);
}
// 删除"TreeMap的值的集合"中的"对象o"
public boolean remove(Object o) {
for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
if (valEquals(e.getValue(), o)) {
deleteEntry(e);
return true;
}
}
return false;
}
// 清空删除"TreeMap的值的集合"
public void clear() {
TreeMap.this.clear();
}
}
说明：从中，我们可以知道Values类就是一个集合。而 AbstractCollection 已经实现了除 size() 和 iterator() 之外的其它函数，因此只需要在Values类中实现这两个函数即可。
size() 的实现非常简单，Values集合中元素的个数=该TreeMap的元素个数。(TreeMap每一个元素都有一个值嘛！)
iterator() 则返回一个迭代器，用于遍历Values。下面，我们一起可以看看iterator()的实现：
public Iterator<V> iterator() {
return new ValueIterator(getFirstEntry());
}
说明： iterator() 是通过ValueIterator() 返回迭代器的，ValueIterator是一个类。代码如下：
final class ValueIterator extends PrivateEntryIterator<V> {
ValueIterator(Entry<K,V> first) {
super(first);
}
public V next() {
return nextEntry().value;
}
}
说明：ValueIterator的代码很简单，它的主要实现应该在它的父类PrivateEntryIterator中。下面我们一起看看PrivateEntryIterator的代码：
abstract class PrivateEntryIterator<T> implements Iterator<T> {
// 下一节点
Entry<K,V> next;
// 上一次返回的节点
Entry<K,V> lastReturned;
int expectedModCount;
PrivateEntryIterator(Entry<K,V> first) {
expectedModCount = modCount;
lastReturned = null;
next = first;
}
// 是否存在下一个节点
public final boolean hasNext() {
return next != null;
}
// 返回下一个节点
final Entry<K,V> nextEntry() {
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
next = successor(e);
lastReturned = e;
return e;
}
// 返回上一节点
final Entry<K,V> prevEntry() {
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
next = predecessor(e);
lastReturned = e;
return e;
}
// 删除当前节点
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
// deleted entries are replaced by their successors
if (lastReturned.left != null && lastReturned.right != null)
next = lastReturned;
deleteEntry(lastReturned);
expectedModCount = modCount;
lastReturned = null;
}
}
说明：PrivateEntryIterator是一个抽象类，它的实现很简单，只只实现了Iterator的remove()和hasNext()接口，没有实现next()接口。
而我们在ValueIterator中已经实现的next()接口。
至此，我们就了解了iterator()的完整实现了。
有关迭代器的其他内容请参加设计模式 3 —— 迭代器和组合模式
5.4 TreeMap的entrySet()函数
entrySet() 返回“键值对集合”。顾名思义，它返回的是一个集合，集合的元素是“键值对”。
下面，我们看看它是如何实现的？entrySet() 的实现代码如下：
public Set<Map.Entry<K,V>> entrySet() {
EntrySet es = entrySet;
return (es != null) ? es : (entrySet = new EntrySet());
}
说明：entrySet()返回的是一个EntrySet对象。
下面我们看看EntrySet的代码：
// EntrySet是“TreeMap的所有键值对组成的集合”，
// EntrySet集合的单位是单个“键值对”。
class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator(getFirstEntry());
} // EntrySet中是否包含“键值对Object”
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
V value = entry.getValue();
Entry<K,V> p = getEntry(entry.getKey());
return p != null && valEquals(p.getValue(), value);
} // 删除EntrySet中的“键值对Object”
public boolean remove(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
V value = entry.getValue();
Entry<K,V> p = getEntry(entry.getKey());
if (p != null && valEquals(p.getValue(), value)) {
deleteEntry(p);
return true;
}
return false;
} // 返回EntrySet中元素个数
public int size() {
return TreeMap.this.size();
} public void clear() {
TreeMap.this.clear();
}
}
说明：
EntrySet是“TreeMap的所有键值对组成的集合”，而且它单位是单个“键值对”。
EntrySet是一个集合，它继承于AbstractSet。而AbstractSet实现了除size() 和 iterator() 之外的其它函数，因此，我们重点了解一下EntrySet的size() 和 iterator() 函数
size() 的实现非常简单，AbstractSet集合中元素的个数=该TreeMap的元素个数。
iterator() 则返回一个迭代器，用于遍历AbstractSet。从上面的源码中，我们可以发现iterator() 是通过EntryIterator实现的；下面我们看看EntryIterator的源码：
final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
EntryIterator(Entry<K,V> first) {
super(first);
}
public Map.Entry<K,V> next() {
return nextEntry();
}
}
说明：和Values类一样，EntryIterator也继承于PrivateEntryIterator类。
5.5 TreeMap实现的Cloneable接口
TreeMap实现了Cloneable接口，即实现了clone()方法。
clone()方法的作用很简单，就是克隆一个TreeMap对象并返回。
// 克隆一个TreeMap，并返回Object对象
public Object clone() {
TreeMap<K,V> clone = null;
try {
clone = (TreeMap<K,V>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError();
} // Put clone into "virgin" state (except for comparator)
clone.root = null;
clone.size = 0;
clone.modCount = 0;
clone.entrySet = null;
clone.navigableKeySet = null;
clone.descendingMap = null; // Initialize clone with our mappings
try {
clone.buildFromSorted(size, entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
} return clone;
}
5.6 TreeMap实现的Serializable接口
TreeMap实现java.io.Serializable，分别实现了串行读取、写入功能。
串行写入函数是writeObject()，它的作用是将TreeMap的“容量，所有的Entry”都写入到输出流中。
而串行读取函数是readObject()，它的作用是将TreeMap的“容量、所有的Entry”依次读出。
readObject() 和 writeObject() 正好是一对，通过它们，能实现TreeMap的串行传输。
// java.io.Serializable的写入函数
// 将TreeMap的“容量，所有的Entry”都写入到输出流中
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out the Comparator and any hidden stuff
s.defaultWriteObject(); // Write out size (number of Mappings)
s.writeInt(size); // Write out keys and values (alternating)
for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
Map.Entry<K,V> e = i.next();
s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
}
// java.io.Serializable的读取函数：根据写入方式读出
// 先将TreeMap的“容量、所有的Entry”依次读出
private void readObject(final java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in the Comparator and any hidden stuff
s.defaultReadObject(); // Read in size
int size = s.readInt(); buildFromSorted(size, null, s, null);
}
5.7 TreeMap实现的NavigableMap接口
举例讲解一个descendingMap()
descendingMap() 的作用是返回当前TreeMap的反向的TreeMap。所谓反向，就是排序顺序和原始的顺序相反。
我们已经知道TreeMap是一颗红黑树，而红黑树是有序的。
TreeMap的排序方式是通过比较器，在创建TreeMap的时候，若指定了比较器，则使用该比较器；否则，就使用Java的默认比较器。
而获取TreeMap的反向TreeMap的原理就是将比较器反向即可！
理解了descendingMap()的反向原理之后，再讲解一下descendingMap()的代码。
// 获取TreeMap的降序Map
public NavigableMap<K, V> descendingMap() {
NavigableMap<K, V> km = descendingMap;
return (km != null) ? km :
(descendingMap = new DescendingSubMap(this,
true, null, true,
true, null, true));
}
从中，我们看出descendingMap()实际上是返回DescendingSubMap类的对象。下面，看看DescendingSubMap的源码：
static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
private static final long serialVersionUID = 912986545866120460L;
DescendingSubMap(TreeMap<K,V> m,
boolean fromStart, K lo, boolean loInclusive,
boolean toEnd, K hi, boolean hiInclusive) {
super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
}
// 反转的比较器：是将原始比较器反转得到的。
private final Comparator<? super K> reverseComparator =
Collections.reverseOrder(m.comparator);
// 获取反转比较器
public Comparator<? super K> comparator() {
return reverseComparator;
}
// 获取“子Map”。
// 范围是从fromKey 到 toKey；fromInclusive是是否包含fromKey的标记，toInclusive是是否包含toKey的标记
public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive) {
if (!inRange(fromKey, fromInclusive))
throw new IllegalArgumentException("fromKey out of range");
if (!inRange(toKey, toInclusive))
throw new IllegalArgumentException("toKey out of range");
return new DescendingSubMap(m,
false, toKey, toInclusive,
false, fromKey, fromInclusive);
}
// 获取“Map的头部”。
// 范围从第一个节点 到 toKey, inclusive是是否包含toKey的标记
public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
if (!inRange(toKey, inclusive))
throw new IllegalArgumentException("toKey out of range");
return new DescendingSubMap(m,
false, toKey, inclusive,
toEnd, hi, hiInclusive);
}
// 获取“Map的尾部”。
// 范围是从 fromKey 到 最后一个节点，inclusive是是否包含fromKey的标记
public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
if (!inRange(fromKey, inclusive))
throw new IllegalArgumentException("fromKey out of range");
return new DescendingSubMap(m,
fromStart, lo, loInclusive,
false, fromKey, inclusive);
}
// 获取对应的降序Map
public NavigableMap<K,V> descendingMap() {
NavigableMap<K,V> mv = descendingMapView;
return (mv != null) ? mv :
(descendingMapView =
new AscendingSubMap(m,
fromStart, lo, loInclusive,
toEnd, hi, hiInclusive));
}
// 返回“升序Key迭代器”
Iterator<K> keyIterator() {
return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
}
// 返回“降序Key迭代器”
Iterator<K> descendingKeyIterator() {
return new SubMapKeyIterator(absLowest(), absHighFence());
}
// “降序EntrySet集合”类
// 实现了iterator()
final class DescendingEntrySetView extends EntrySetView {
public Iterator<Map.Entry<K,V>> iterator() {
return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
}
}
// 返回“降序EntrySet集合”
public Set<Map.Entry<K,V>> entrySet() {
EntrySetView es = entrySetView;
return (es != null) ? es : new DescendingEntrySetView();
}
TreeMap.Entry<K,V> subLowest() { return absHighest(); }
TreeMap.Entry<K,V> subHighest() { return absLowest(); }
TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
TreeMap.Entry<K,V> subHigher(K key) { return absLower(key); }
TreeMap.Entry<K,V> subFloor(K key) { return absCeiling(key); }
TreeMap.Entry<K,V> subLower(K key) { return absHigher(key); }
}
从中，我们看出DescendingSubMap是降序的SubMap，它的实现机制是将“SubMap的比较器反转”。
它继承于NavigableSubMap。而NavigableSubMap是一个继承于AbstractMap的抽象类；它包括2个子类——"(升序)AscendingSubMap"和"(降序)DescendingSubMap"。NavigableSubMap为它的两个子类实现了许多公共API。
下面看看NavigableSubMap的源码。
static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, java.io.Serializable {
// TreeMap的拷贝
final TreeMap<K,V> m;
// lo是“子Map范围的最小值”，hi是“子Map范围的最大值”；
// loInclusive是“是否包含lo的标记”，hiInclusive是“是否包含hi的标记”
// fromStart是“表示是否从第一个节点开始计算”，
// toEnd是“表示是否计算到最后一个节点 ”
final K lo, hi;
final boolean fromStart, toEnd;
final boolean loInclusive, hiInclusive; // 构造函数
NavigableSubMap(TreeMap<K,V> m,
boolean fromStart, K lo, boolean loInclusive,
boolean toEnd, K hi, boolean hiInclusive) {
if (!fromStart && !toEnd) {
if (m.compare(lo, hi) > 0)
throw new IllegalArgumentException("fromKey > toKey");
} else {
if (!fromStart) // type check
m.compare(lo, lo);
if (!toEnd)
m.compare(hi, hi);
} this.m = m;
this.fromStart = fromStart;
this.lo = lo;
this.loInclusive = loInclusive;
this.toEnd = toEnd;
this.hi = hi;
this.hiInclusive = hiInclusive;
} // 判断key是否太小
final boolean tooLow(Object key) {
// 若该SubMap不包括“起始节点”，
// 并且，“key小于最小键(lo)”或者“key等于最小键(lo)，但最小键却没包括在该SubMap内”
// 则判断key太小。其余情况都不是太小！
if (!fromStart) {
int c = m.compare(key, lo);
if (c < 0 || (c == 0 && !loInclusive))
return true;
}
return false;
} // 判断key是否太大
final boolean tooHigh(Object key) {
// 若该SubMap不包括“结束节点”，
// 并且，“key大于最大键(hi)”或者“key等于最大键(hi)，但最大键却没包括在该SubMap内”
// 则判断key太大。其余情况都不是太大！
if (!toEnd) {
int c = m.compare(key, hi);
if (c > 0 || (c == 0 && !hiInclusive))
return true;
}
return false;
} // 判断key是否在“lo和hi”开区间范围内
final boolean inRange(Object key) {
return !tooLow(key) && !tooHigh(key);
} // 判断key是否在封闭区间内
final boolean inClosedRange(Object key) {
return (fromStart || m.compare(key, lo) >= 0)
&& (toEnd || m.compare(hi, key) >= 0);
} // 判断key是否在区间内, inclusive是区间开关标志
final boolean inRange(Object key, boolean inclusive) {
return inclusive ? inRange(key) : inClosedRange(key);
} // 返回最低的Entry
final TreeMap.Entry<K,V> absLowest() {
// 若“包含起始节点”，则调用getFirstEntry()返回第一个节点
// 否则的话，若包括lo，则调用getCeilingEntry(lo)获取大于/等于lo的最小的Entry;
// 否则，调用getHigherEntry(lo)获取大于lo的最小Entry
TreeMap.Entry<K,V> e =
(fromStart ? m.getFirstEntry() :
(loInclusive ? m.getCeilingEntry(lo) :
m.getHigherEntry(lo)));
return (e == null || tooHigh(e.key)) ? null : e;
} // 返回最高的Entry
final TreeMap.Entry<K,V> absHighest() {
// 若“包含结束节点”，则调用getLastEntry()返回最后一个节点
// 否则的话，若包括hi，则调用getFloorEntry(hi)获取小于/等于hi的最大的Entry;
// 否则，调用getLowerEntry(hi)获取大于hi的最大Entry
TreeMap.Entry<K,V> e =
TreeMap.Entry<K,V> e =
(toEnd ? m.getLastEntry() :
(hiInclusive ? m.getFloorEntry(hi) :
m.getLowerEntry(hi)));
return (e == null || tooLow(e.key)) ? null : e;
} // 返回"大于/等于key的最小的Entry"
final TreeMap.Entry<K,V> absCeiling(K key) {
// 只有在“key太小”的情况下，absLowest()返回的Entry才是“大于/等于key的最小Entry”
// 其它情况下不行。例如，当包含“起始节点”时，absLowest()返回的是最小Entry了！
if (tooLow(key))
return absLowest();
// 获取“大于/等于key的最小Entry”
TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
return (e == null || tooHigh(e.key)) ? null : e;
} // 返回"大于key的最小的Entry"
final TreeMap.Entry<K,V> absHigher(K key) {
// 只有在“key太小”的情况下，absLowest()返回的Entry才是“大于key的最小Entry”
// 其它情况下不行。例如，当包含“起始节点”时，absLowest()返回的是最小Entry了,而不一定是“大于key的最小Entry”！
if (tooLow(key))
return absLowest();
// 获取“大于key的最小Entry”
TreeMap.Entry<K,V> e = m.getHigherEntry(key);
return (e == null || tooHigh(e.key)) ? null : e;
} // 返回"小于/等于key的最大的Entry"
final TreeMap.Entry<K,V> absFloor(K key) {
// 只有在“key太大”的情况下，(absHighest)返回的Entry才是“小于/等于key的最大Entry”
// 其它情况下不行。例如，当包含“结束节点”时，absHighest()返回的是最大Entry了！
if (tooHigh(key))
return absHighest();
// 获取"小于/等于key的最大的Entry"
TreeMap.Entry<K,V> e = m.getFloorEntry(key);
return (e == null || tooLow(e.key)) ? null : e;
} // 返回"小于key的最大的Entry"
final TreeMap.Entry<K,V> absLower(K key) {
// 只有在“key太大”的情况下，(absHighest)返回的Entry才是“小于key的最大Entry”
// 其它情况下不行。例如，当包含“结束节点”时，absHighest()返回的是最大Entry了,而不一定是“小于key的最大Entry”！
if (tooHigh(key))
return absHighest();
// 获取"小于key的最大的Entry"
TreeMap.Entry<K,V> e = m.getLowerEntry(key);
return (e == null || tooLow(e.key)) ? null : e;
} // 返回“大于最大节点中的最小节点”，不存在的话，返回null
final TreeMap.Entry<K,V> absHighFence() {
return (toEnd ? null : (hiInclusive ?
m.getHigherEntry(hi) :
m.getCeilingEntry(hi)));
} // 返回“小于最小节点中的最大节点”，不存在的话，返回null
final TreeMap.Entry<K,V> absLowFence() {
return (fromStart ? null : (loInclusive ?
m.getLowerEntry(lo) :
m.getFloorEntry(lo)));
} // 下面几个abstract方法是需要NavigableSubMap的实现类实现的方法
abstract TreeMap.Entry<K,V> subLowest();
abstract TreeMap.Entry<K,V> subHighest();
abstract TreeMap.Entry<K,V> subCeiling(K key);
abstract TreeMap.Entry<K,V> subHigher(K key);
abstract TreeMap.Entry<K,V> subFloor(K key);
abstract TreeMap.Entry<K,V> subLower(K key);
// 返回“顺序”的键迭代器
abstract Iterator<K> keyIterator();
// 返回“逆序”的键迭代器
abstract Iterator<K> descendingKeyIterator(); // 返回SubMap是否为空。空的话，返回true，否则返回false
public boolean isEmpty() {
return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
} // 返回SubMap的大小
public int size() {
return (fromStart && toEnd) ? m.size() : entrySet().size();
} // 返回SubMap是否包含键key
public final boolean containsKey(Object key) {
return inRange(key) && m.containsKey(key);
} // 将key-value 插入SubMap中
public final V put(K key, V value) {
if (!inRange(key))
throw new IllegalArgumentException("key out of range");
return m.put(key, value);
} // 获取key对应值
public final V get(Object key) {
return !inRange(key)? null : m.get(key);
} // 删除key对应的键值对
public final V remove(Object key) {
return !inRange(key)? null : m.remove(key);
} // 获取“大于/等于key的最小键值对”
public final Map.Entry<K,V> ceilingEntry(K key) {
return exportEntry(subCeiling(key));
} // 获取“大于/等于key的最小键”
public final K ceilingKey(K key) {
return keyOrNull(subCeiling(key));
} // 获取“大于key的最小键值对”
public final Map.Entry<K,V> higherEntry(K key) {
return exportEntry(subHigher(key));
} // 获取“大于key的最小键”
public final K higherKey(K key) {
return keyOrNull(subHigher(key));
} // 获取“小于/等于key的最大键值对”
public final Map.Entry<K,V> floorEntry(K key) {
return exportEntry(subFloor(key));
} // 获取“小于/等于key的最大键”
public final K floorKey(K key) {
return keyOrNull(subFloor(key));
} // 获取“小于key的最大键值对”
public final Map.Entry<K,V> lowerEntry(K key) {
return exportEntry(subLower(key));
} // 获取“小于key的最大键”
public final K lowerKey(K key) {
return keyOrNull(subLower(key));
} // 获取"SubMap的第一个键"
public final K firstKey() {
return key(subLowest());
} // 获取"SubMap的最后一个键"
public final K lastKey() {
return key(subHighest());
} // 获取"SubMap的第一个键值对"
public final Map.Entry<K,V> firstEntry() {
return exportEntry(subLowest());
} // 获取"SubMap的最后一个键值对"
public final Map.Entry<K,V> lastEntry() {
return exportEntry(subHighest());
} // 返回"SubMap的第一个键值对"，并从SubMap中删除改键值对
public final Map.Entry<K,V> pollFirstEntry() {
TreeMap.Entry<K,V> e = subLowest();
Map.Entry<K,V> result = exportEntry(e);
if (e != null)
m.deleteEntry(e);
return result;
} // 返回"SubMap的最后一个键值对"，并从SubMap中删除改键值对
public final Map.Entry<K,V> pollLastEntry() {
TreeMap.Entry<K,V> e = subHighest();
Map.Entry<K,V> result = exportEntry(e);
if (e != null)
m.deleteEntry(e);
return result;
} // Views
transient NavigableMap<K,V> descendingMapView = null;
transient EntrySetView entrySetView = null;
transient KeySet<K> navigableKeySetView = null; // 返回NavigableSet对象，实际上返回的是当前对象的"Key集合"。
public final NavigableSet<K> navigableKeySet() {
KeySet<K> nksv = navigableKeySetView;
return (nksv != null) ? nksv :
(navigableKeySetView = new TreeMap.KeySet(this));
} // 返回"Key集合"对象
public final Set<K> keySet() {
return navigableKeySet();
} // 返回“逆序”的Key集合
public NavigableSet<K> descendingKeySet() {
return descendingMap().navigableKeySet();
} // 排列fromKey(包含) 到 toKey(不包含) 的子map
public final SortedMap<K,V> subMap(K fromKey, K toKey) {
return subMap(fromKey, true, toKey, false);
} // 返回当前Map的头部(从第一个节点 到 toKey, 不包括toKey)
public final SortedMap<K,V> headMap(K toKey) {
return headMap(toKey, false);
} // 返回当前Map的尾部[从 fromKey(包括fromKeyKey) 到 最后一个节点]
public final SortedMap<K,V> tailMap(K fromKey) {
return tailMap(fromKey, true);
} // Map的Entry的集合
abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
private transient int size = -1, sizeModCount; // 获取EntrySet的大小
public int size() {
// 若SubMap是从“开始节点”到“结尾节点”，则SubMap大小就是原TreeMap的大小
if (fromStart && toEnd)
return m.size();
// 若SubMap不是从“开始节点”到“结尾节点”，则调用iterator()遍历EntrySetView中的元素
if (size == -1 || sizeModCount != m.modCount) {
sizeModCount = m.modCount;
size = 0;
Iterator i = iterator();
while (i.hasNext()) {
size++;
i.next();
}
}
return size;
} // 判断EntrySetView是否为空
public boolean isEmpty() {
TreeMap.Entry<K,V> n = absLowest();
return n == null || tooHigh(n.key);
} // 判断EntrySetView是否包含Object
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
K key = entry.getKey();
if (!inRange(key))
return false;
TreeMap.Entry node = m.getEntry(key);
return node != null &&
valEquals(node.getValue(), entry.getValue());
} // 从EntrySetView中删除Object
public boolean remove(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
K key = entry.getKey();
if (!inRange(key))
return false;
TreeMap.Entry<K,V> node = m.getEntry(key);
if (node!=null && valEquals(node.getValue(),entry.getValue())){
m.deleteEntry(node);
return true;
}
return false;
}
} // SubMap的迭代器
abstract class SubMapIterator<T> implements Iterator<T> {
// 上一次被返回的Entry
TreeMap.Entry<K,V> lastReturned;
// 指向下一个Entry
TreeMap.Entry<K,V> next;
// “栅栏key”。根据SubMap是“升序”还是“降序”具有不同的意义
final K fenceKey;
int expectedModCount; // 构造函数
SubMapIterator(TreeMap.Entry<K,V> first,
TreeMap.Entry<K,V> fence) {
// 每创建一个SubMapIterator时，保存修改次数
// 若后面发现expectedModCount和modCount不相等，则抛出ConcurrentModificationException异常。
// 这就是所说的fast-fail机制的原理！
expectedModCount = m.modCount;
lastReturned = null;
next = first;
fenceKey = fence == null ? null : fence.key;
} // 是否存在下一个Entry
public final boolean hasNext() {
return next != null && next.key != fenceKey;
} // 返回下一个Entry
final TreeMap.Entry<K,V> nextEntry() {
TreeMap.Entry<K,V> e = next;
if (e == null || e.key == fenceKey)
throw new NoSuchElementException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
// next指向e的后继节点
next = successor(e);
lastReturned = e;
return e;
} // 返回上一个Entry
final TreeMap.Entry<K,V> prevEntry() {
TreeMap.Entry<K,V> e = next;
if (e == null || e.key == fenceKey)
throw new NoSuchElementException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
// next指向e的前继节点
next = predecessor(e);
lastReturned = e;
return e;
} // 删除当前节点(用于“升序的SubMap”)。
// 删除之后，可以继续升序遍历；红黑树特性没变。
final void removeAscending() {
if (lastReturned == null)
throw new IllegalStateException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
// 这里重点强调一下“为什么当lastReturned的左右孩子都不为空时，要将其赋值给next”。
// 目的是为了“删除lastReturned节点之后，next节点指向的仍然是下一个节点”。
// 根据“红黑树”的特性可知：
// 当被删除节点有两个儿子时。那么，首先把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。
// 这意味着“当被删除节点有两个儿子时，删除当前节点之后，'新的当前节点'实际上是‘原有的后继节点(即下一个节点)’”。
// 而此时next仍然指向"新的当前节点"。也就是说next是仍然是指向下一个节点；能继续遍历红黑树。
if (lastReturned.left != null && lastReturned.right != null)
next = lastReturned;
m.deleteEntry(lastReturned);
lastReturned = null;
expectedModCount = m.modCount;
} // 删除当前节点(用于“降序的SubMap”)。
// 删除之后，可以继续降序遍历；红黑树特性没变。
final void removeDescending() {
if (lastReturned == null)
throw new IllegalStateException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
m.deleteEntry(lastReturned);
lastReturned = null;
expectedModCount = m.modCount;
} } // SubMap的Entry迭代器，它只支持升序操作，继承于SubMapIterator
final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
SubMapEntryIterator(TreeMap.Entry<K,V> first,
TreeMap.Entry<K,V> fence) {
super(first, fence);
}
// 获取下一个节点(升序)
public Map.Entry<K,V> next() {
return nextEntry();
}
// 删除当前节点(升序)
public void remove() {
removeAscending();
}
} // SubMap的Key迭代器，它只支持升序操作，继承于SubMapIterator
final class SubMapKeyIterator extends SubMapIterator<K> {
SubMapKeyIterator(TreeMap.Entry<K,V> first,
TreeMap.Entry<K,V> fence) {
super(first, fence);
}
// 获取下一个节点(升序)
public K next() {
return nextEntry().key;
}
// 删除当前节点(升序)
public void remove() {
removeAscending();
}
} // 降序SubMap的Entry迭代器，它只支持降序操作，继承于SubMapIterator
final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
TreeMap.Entry<K,V> fence) {
super(last, fence);
} // 获取下一个节点(降序)
public Map.Entry<K,V> next() {
return prevEntry();
}
// 删除当前节点(降序)
public void remove() {
removeDescending();
}
} // 降序SubMap的Key迭代器，它只支持降序操作，继承于SubMapIterator
final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
TreeMap.Entry<K,V> fence) {
super(last, fence);
}
// 获取下一个节点(降序)
public K next() {
return prevEntry().key;
}
// 删除当前节点(降序)
public void remove() {
removeDescending();
}
}
}
NavigableSubMap源码很多，但不难理解；读者可以通过源码和注释进行理解。
其实，读完NavigableSubMap的源码后，我们可以得出它的核心思想是：它是一个抽象集合类，为2个子类——"(升序)AscendingSubMap"和"(降序)DescendingSubMap"而服务；因为NavigableSubMap实现了许多公共API。它的最终目的是实现下面的一系列函数：
headMap(K toKey, boolean inclusive)
headMap(K toKey)
subMap(K fromKey, K toKey)
subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
tailMap(K fromKey)
tailMap(K fromKey, boolean inclusive)
navigableKeySet()
descendingKeySet()
参考：
1、红黑树系列集锦
3、红黑树