JDK源码解析---TreeMap

1. 概述

TreeMap ，按照 key 的顺序的 Map 实现类。

采用红黑树实现 红黑树具有以下的特性

• 有序性：红黑树是一种二叉平衡查找树，父节点的 key 小于左子节点的 key ，大于右子节点的 key 。这样，就完成了 TreeMap 的有序的特性。
• 高性能：红黑树会进行自平衡，避免树的高度过高，导致查找性能下滑。这样，红黑树能够提供 logN 的时间复杂度。

红黑树的性质：

• 性质1：每个节点要么是黑色，要么是红色。
• 性质2：根节点是黑色。
• 性质3：每个叶子节点（NIL）是黑色。
• 性质4：每个红色结点的两个子结点一定都是黑色。
• 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑

2. 类图

TreeMap 实现的接口、继承的类，如下图所示：

• 继承 java.util.AbstractMap 抽像类。
• 实现 java.util.NavigableMap 接口
• 实现 序列化 接口。
• 实现 克隆接口。

3. 属性

private final Comparator<? super K> comparator;// key 排序器private transient Entry<K,V> root;//红黑树的根节点private transient int size = 0;//key-value 键值对数量private transient int modCount = 0;//修改次数

4. 构造方法

TreeMap 一共有四个构造方法

① #TreeMap()

public TreeMap() {comparator = null;
}

• 默认构造方法，不使用自定义排序，所以此时 comparator 为空。

② #TreeMap(Comparator<? super K> comparator)

public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator;
}

• 可传入 comparator 参数，自定义 key 的排序规则。

③ #TreeMap(SortedMap<K, ? extends V> m)**

public TreeMap(SortedMap<K, ? extends V> m) {// 设置 comparator 属性comparator = m.comparator();try {// 使用 m 构造红黑树buildFromSorted(m.size(), m.entrySet().iterator(), null, null);} catch (java.io.IOException | ClassNotFoundException cannotHappen) {}
}

• 设置比较器为m的比较器。
• 然后调用buildFromSorted方法构建TreeMap。代码如下：

private void buildFromSorted(int size, Iterator<?> it,java.io.ObjectInputStream str,V defaultVal)throws  java.io.IOException, ClassNotFoundException {// 设置 key-value 键值对的数量this.size = size;// computeRedLevel(size) 方法，计算红黑树的高度// 使用 m 构造红黑树，返回根节点root = buildFromSorted(0, 0, size - 1, computeRedLevel(size),it, str, defaultVal);
}

• 设置 key-value 键值对的数量到 size 。

• 调用 #computeRedLevel(int size) 方法，计算红黑树的高度。代码如下：

  private static int computeRedLevel(int size) {return 31 - Integer.numberOfLeadingZeros(size + 1);
  }
  

• 调用 #buildFromSorted(int level, int lo, int hi, int redLevel, Iterator<?> it, ObjectInputStream str, V defaultVal) 方法，使用 m 构造红黑树，返回根节点。代码如下：

private final Entry<K,V> buildFromSorted(int level, int lo, int hi,int redLevel,Iterator<?> it,java.io.ObjectInputStream str,V defaultVal)throws  java.io.IOException, ClassNotFoundException {/** Strategy: The root is the middlemost element. To get to it, we* have to first recursively construct the entire left subtree,* so as to grab all of its elements. We can then proceed with right* subtree.** The lo and hi arguments are the minimum and maximum* indices to pull out of the iterator or stream for current subtree.* They are not actually indexed, we just proceed sequentially,* ensuring that items are extracted in corresponding order.*/// 递归结束if (hi < lo) return null;// 计算中间值int mid = (lo + hi) >>> 1;// <2.1> 创建左子树Entry<K,V> left  = null;if (lo < mid)// 递归左子树left = buildFromSorted(level + 1, lo, mid - 1, redLevel,it, str, defaultVal);// 获得 key-value 键值对K key;V value;if (it != null) { // 使用 it 迭代器，获得下一个值if (defaultVal == null) {Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next(); // 从 it 获得下一个 Entry 节点key = (K) entry.getKey(); // 读取 keyvalue = (V) entry.getValue(); // 读取 value} else { // 默认值不为空key = (K)it.next();  // 读取 keyvalue = defaultVal; // 设置 default 为 value}} else { // use stream 处理 str 流的情况key = (K) str.readObject(); // 从 str 读取 key 值value = (defaultVal != null ? defaultVal : (V) str.readObject()); // 从 str 读取 value 值}// 创建中间节点Entry<K,V> middle =  new Entry<>(key, value, null);// color nodes in non-full bottommost level red// 如果到树的最大高度，则设置为红节点if (level == redLevel)middle.color = RED;// 如果左子树不为空 设置左子树的父亲为mid mid的左子树是leftif (left != null) {middle.left = left; left.parent = middle; }// 创建右子树if (mid < hi) {// 递归右子树Entry<K,V> right = buildFromSorted(level + 1, mid + 1, hi, redLevel,it, str, defaultVal);// 当前节点，设置右子树middle.right = right;// 右子树，设置父节点为当前节点right.parent = middle;}// 返回当前节点return middle;
}

④ #TreeMap(Map<? extends K, ? extends V> m)

// TreeMap.javapublic TreeMap(Map<? extends K, ? extends V> m) {comparator = null;// 添加所有元素putAll(m);
}

• 传入 m 的是 Map 类型，构建成初始的 TreeMap 。
• 调用 #putAll(Map<? extends K, ? extends V> map) 方法，添加所有元素。代码如下：

public void putAll(Map<? extends K, ? extends V> map) {// 满足如下条件，调用 buildFromSorted 方法来优化处理int mapSize = map.size();if (size == 0 // 如果 TreeMap 的大小为 0&& mapSize != 0 // map 的大小非 0&& map instanceof SortedMap) { // 如果是 map 是 SortedMap 类型if (Objects.equals(comparator, ((SortedMap<?,?>)map).comparator())) { // 排序规则相同// 增加修改次数++modCount;// 基于 SortedMap 顺序迭代插入即可try {buildFromSorted(mapSize, map.entrySet().iterator(),null, null);} catch (java.io.IOException | ClassNotFoundException cannotHappen) {}return;}}// 直接遍历 map 来添加super.putAll(map);
}

5. 添加单个元素

#put(K key, V value) 方法，添加单个元素。代码如下：

public V put(K key, V value) {// 记录当前根节点Entry<K,V> t = root;// //如果根结点为空 直接使用这个键值对作为根结点 然后返回。if (t == null) {// 校验 key 类型。compare(key, key); // type (and possibly null) check// 创建 Entry 节点root = new Entry<>(key, value, null);// 设置 key-value 键值对的数量size = 1;// 增加修改次数modCount++;return null;}// 开始遍历红黑树int cmp;标记位 标记key比父结点小还是大Entry<K,V> parent; // 父节点// split comparator and comparable pathsComparator<? super K> cpr = comparator;if (cpr != null) {//不为空do {//记录下当前的父亲结点parent = t;//key和这个结点比较大小cmp = cpr.compare(key, t.key);//key比当前结点小。则遍历左子树if (cmp < 0)t = t.left;//比当前结点大 遍历右子树else if (cmp > 0)t = t.right;elsereturn t.setValue(value);// 一样 说明找到了位置。修改其值} while (t != null);//循环}else { // 如果没有自定义 comparator ，则使用 key 自身比较器来比较if (key == null) // 如果 key 为空，则抛出异常throw new NullPointerException();@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key;do {// 记录新的父节点parent = t;// 比较 keycmp = k.compareTo(t.key);// 比 key 小，说明要遍历左子树if (cmp < 0)t = t.left;// 比 key 大，说明要遍历右子树else if (cmp > 0)t = t.right;// 说明，相等，说明要找到的 t 就是 key 对应的节点，直接设置 value 即可。elsereturn t.setValue(value);} while (t != null); }// 创建 key-value 的 Entry 节点Entry<K,V> e = new Entry<>(key, value, parent);// 设置左右子树if (cmp < 0) parent.left = e;elseparent.right = e;// 插入后，进行自平衡fixAfterInsertion(e);// 设置 key-value 键值对的数量size++;// 增加修改次数modCount++;return null;
}

• 红黑树是一颗平衡树 所以可以根据二分查找的规则 使用定义的比较器来查找插入的位置
• 插入后红黑树需要自平衡处理。

6. 获得单个元素

#get(Object key) 方法，获得 key 对应的 value 值。代码如下：

// TreeMap.javapublic V get(Object key) {// 获得 key 对应的 Entry 节点Entry<K,V> p = getEntry(key);// 返回 value 值return (p == null ? null : p.value);
}final Entry<K,V> getEntry(Object key) { // 不使用 comparator 查找// Offload comparator-based version for sake of performance// 如果自定义了 comparator 比较器，则基于 comparator 比较来查找if (comparator != null)return getEntryUsingComparator(key);// 如果 key 为空，抛出异常if (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key;// 遍历红黑树Entry<K,V> p = root;while (p != null) {// 比较值int cmp = k.compareTo(p.key);// 如果 key 小于当前节点，则遍历左子树if (cmp < 0)p = p.left;// 如果 key 大于当前节点，则遍历右子树else if (cmp > 0)p = p.right;// 如果 key 相等，则返回该节点elsereturn p;}// 查找不到，返回 nullreturn null;
}final Entry<K,V> getEntryUsingComparator(Object key) { // 使用 comparator 查找@SuppressWarnings("unchecked")K k = (K) key;Comparator<? super K> cpr = comparator;if (cpr != null) {// 遍历红黑树Entry<K,V> p = root;while (p != null) {// 比较值int cmp = cpr.compare(k, p.key);// 如果 key 小于当前节点，则遍历左子树if (cmp < 0)p = p.left;// 如果 key 大于当前节点，则遍历右子树else if (cmp > 0)p = p.right;// 如果 key 相等，则返回该节点elsereturn p;}}// 查找不到，返回 nullreturn null;
}

• 查找逻辑和添加逻辑很类似。不再赘述

7. 删除单个元素

相比 添加 来说，删除会更加复杂一些。所以呢，我们先看删除的四种情况。为了让案例更加复杂，我们会使用一颗二叉查找树来举例子。因为，在去掉自平衡的逻辑的情况下，红黑树的删除和二叉查查找树的删除逻辑是一致的。

对于二叉查找树的删除，需要保证删除节点后，能够继续满足二叉和查找的特性。

该图通过 http://btv.melezinek.cz/binary-search-tree.html 绘制

情况一，无子节点。
直接删除父节点对其的指向即可。
例如说，叶子节点 5、11、14、18 。

情况二，只有左子节点。
将删除节点的父节点，指向删除节点的左子节点。
例如说，节点 20 。可以通过将节点 15 的右子节点指向节点 19 。

情况三，只有右子节点。
和情况二的处理方式一致。将删除节点的父节点，指向删除节点的右子节点。
图中暂无示例，胖友自己脑补下，嘿嘿。

情况四，有左子节点 + 右子节点。
这种情况，相对会比较复杂，可以选择左子树中的最大值 或者右子树中的最小值来替代这个被删除的结点。

代码如下：

public V remove(Object key) {// 获得 key 对应的 Entry 节点Entry<K,V> p = getEntry(key);// 如果不存在，则返回 null ，无需删除if (p == null)return null;V oldValue = p.value;// 删除节点deleteEntry(p);return oldValue;//返回旧值
}

private void deleteEntry(Entry<K,V> p) {modCount++;size--;// If strictly internal, copy successor's element to p and then make p// point to successor.// 如果删除的节点 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// Start fixup at replacement node, if it exists.// 左右孩子中不为空的那个作为替换结点Entry<K,V> replacement = (p.left != null ? p.left : p.right);// 有子节点的情况// 有结点if (replacement != null) {// Link replacement to parentreplacement.parent = p.parent;//这个替换结点的父亲结点改成被删除结点的父亲结点。if (p.parent == null)//表示删除的是根结点root = replacement;//根结点设置成替换结点。else if (p == p.parent.left)// 如果被删除结点是其父结点的左孩子 则父结点的做孩子设置成替换结点p.parent.left  = replacement;else //否则相反p.parent.right = replacement;// Null out links so they are OK to use by fixAfterDeletion.p.left = p.right = p.parent = null; // 置空// Fix replacementif (p.color == BLACK) // 如果p的颜色是黑色 执行自平衡fixAfterDeletion(replacement);} else if (p.parent == null) { // return if we are the only node.root = null;// 如果删除的没有左子树，又没有右子树} else { // No children. Use self as phantom replacement and unlink.// 如果 p 的颜色是黑色，则执行自平衡if (p.color == BLACK)fixAfterDeletion(p);// 删除 p 和其父节点的相互指向if (p.parent != null) {// 如果 p 是父节点的左子节点，则置空父节点的左子节点if (p == p.parent.left)p.parent.left = null;// 如果 p 是父节点的右子节点，则置空父节点的右子节点else if (p == p.parent.right)p.parent.right = null;// 置空 p 对父节点的指向p.parent = null;}}
}

• 删除的逻辑也就是刚才上面分析的一样。首先如果左右孩子都不为空，则调用一下的函数得到右子树中的最小值。然后修改被删除的结点的键值 表示替换。然后将要删除的结点指针指向找到的这个最小值。
• 相当于将最复杂的一种情况 转换成了上面的三种情况中的一种。接着就是对着三种情况的不同处理。
  • 被删除节点有至少一个孩子。那么就将这个孩子替换被删除的结点。如果这个节点的颜色是黑色，则需要执行自平衡操作。
  • 被删除的结点没有父亲结点 则将根结点设置为空
  • 被删除节点没有孩子 则判断这个节点的颜色是不是黑色 若是黑色则执行自平衡。 然后删除这个节点。

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {// <1> 如果 t 为空，则返回 nullif (t == null)return null;// <2> 如果 t 的右子树非空，则取右子树的最小值else if (t.right != null) {// 先取右子树的根节点Entry<K,V> p = t.right;// 再取该根节点的做子树的最小值，即不断遍历左节点while (p.left != null)p = p.left;// 返回return p;// <3> 如果 t 的右子树为空} else {// 先获得 t 的父节点Entry<K,V> p = t.parent;// 不断向上遍历父节点，直到子节点 ch 不是父节点 p 的右子节点Entry<K,V> ch = t;while (p != null // 还有父节点&& ch == p.right) { // 继续遍历的条件，必须是子节点 ch 是父节点 p 的右子节点ch = p;p = p.parent;}return p;}
}

• 返回中序遍历中比t大的下一个值。

8. 自平衡

8.1插入后自平衡

private void fixAfterInsertion(Entry<K,V> x) {x.color = RED;// 以三层为一个单位while (x != null && x != root && x.parent.color == RED) {// x 不为空 并且 x不是根结点 并且 x的父亲是红色的，if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {// 如果x的父亲是x父亲的父亲的左孩子Entry<K,V> y = rightOf(parentOf(parentOf(x)));// y指向x的父亲的兄弟 也就是x父亲的父亲的右孩子if (colorOf(y) == RED) {// 如果y是红色的 说明插入的结点不会导致二叉树失去平衡setColor(parentOf(x), BLACK);// 设置x的父亲为黑色setColor(y, BLACK);// 设置y的颜色为黑色setColor(parentOf(parentOf(x)), RED);//设置x的父亲的父亲为红色 也就是y的父亲为红色x = parentOf(parentOf(x));// x指向x的父亲的父亲} else {//y是黑色 这就需要自平衡处理if (x == rightOf(parentOf(x))) {// 如果x是父亲的右孩子x = parentOf(x);// x指向x的父亲rotateLeft(x);//左旋}setColor(parentOf(x), BLACK);//设置x的父亲为黑色setColor(parentOf(parentOf(x)), RED);// 设置x的父亲的父亲为红色rotateRight(parentOf(parentOf(x)));//右旋}} else {// x的父亲是x父亲的父亲的右孩子Entry<K,V> y = leftOf(parentOf(parentOf(x)));//y指向x的父亲的兄弟 也就是x父亲的父亲的左孩子if (colorOf(y) == RED) {//如果y是红色 说明插入的结点不会导致二叉树失去平衡setColor(parentOf(x), BLACK);//这是x的父亲是黑色setColor(y, BLACK);//设置y的颜色为黑色setColor(parentOf(parentOf(x)), RED);//设置x的父亲的父亲为红色 也就是y的父亲为红色x = parentOf(parentOf(x));//x指向x的父亲的父亲} else {// y 是黑色 这就需要自平衡处理if (x == leftOf(parentOf(x))) {// 如果x是父亲的左孩子x = parentOf(x);// x指向x的父亲rotateRight(x);//右旋}setColor(parentOf(x), BLACK);//设置x的父亲为黑色setColor(parentOf(parentOf(x)), RED);// 设置设置x的父亲的父亲为红色rotateLeft(parentOf(parentOf(x)));//左旋}}}root.color = BLACK;
}

在插入方法执行完后 需要执行上述的自平衡方法。可以把自平衡操作当前结点和他的父亲和他的爷爷看成一个单位。

三者的关系可以有如下四种

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-J9Iq7pHs-1597754100773)(/Users/gongsenlin/Library/Application Support/typora-user-images/截屏2020-08-18 下午4.52.06.png)]

上述的代码也是根据这4种情况进行处理的。最下面的是当前结点x。上面两个分别是x的父亲和x的父亲的父亲。

照着这个流程就可以懂得如何旋转来实现自平衡的了。

可以发现。当x的父亲的兄弟是红色的时候是不会导致二叉树失去平衡的 只有当x的父亲的兄弟是黑色的时候才会导致二叉树失去平衡。

不管是前两种情况还是后两种情况。执行的修改颜色的操作都是一样的。

8.2 删除后自平衡

有两种情况

一种是删除节点有孩子 则是在删除了节点后 以替换节点作为参数做自平衡

另一种是删除节点没有孩子 则说明是叶子节点，则直接根据这个节点作为参数做自平衡 然后删除这个节点。

具体的删除节点自平衡代码如下

private void fixAfterDeletion(Entry<K,V> x) {while (x != root && colorOf(x) == BLACK) {// x不为根 且x的颜色是黑色if (x == leftOf(parentOf(x))) {// 如果x是父亲的左孩子。Entry<K,V> sib = rightOf(parentOf(x));//sib是x的兄弟if (colorOf(sib) == RED) {//如果兄弟是红色 同时也说明x有兄弟 sib为空的情况下 颜色是默认黑色的setColor(sib, BLACK);// 设置兄弟为黑色setColor(parentOf(x), RED);//设置父亲为红色rotateLeft(parentOf(x));// 左旋 以x的父亲为中心左旋sib = rightOf(parentOf(x)); // sib指向}if (colorOf(leftOf(sib))  == BLACK &&colorOf(rightOf(sib)) == BLACK) {//sib的 左右孩子都是黑色 则把它设置为红色 这是红黑树的一条规则setColor(sib, RED);x = parentOf(x);//x指向x的父亲} else {if (colorOf(rightOf(sib)) == BLACK) {//如果兄弟的右孩子是黑色setColor(leftOf(sib), BLACK);//这是兄弟的做孩子为黑色setColor(sib, RED);//设置sib的颜色为红色rotateRight(sib);//右旋 sib = rightOf(parentOf(x)); // sib指向x的父亲的右孩子 也就是旋转后的x的兄弟}setColor(sib, colorOf(parentOf(x))); // 这是sib的颜色为x的父亲的颜色setColor(parentOf(x), BLACK);//设置x的父亲的颜色为黑色setColor(rightOf(sib), BLACK);// 设置sib的右孩子为黑色rotateLeft(parentOf(x));// 左旋x = root;//x指向根}} else { // x是父亲的右孩子Entry<K,V> sib = leftOf(parentOf(x));//那么x的兄弟 就是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);}

9. 查找接近的元素

在 NavigableMap 中，定义了四个查找接近的元素：

• #lowerEntry(K key) 方法，小于 key 的节点
• #floorEntry(K key) 方法，小于等于 key 的节点
• #higherEntry(K key) 方法，大于 key 的节点
• #ceilingEntry(K key) 方法，大于等于 key 的节点

#ceilingEntry(K key) 方法，大于等于 key 的节点。代码如下：

public Map.Entry<K,V> ceilingEntry(K key) {return exportEntry(getCeilingEntry(key));
}static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {return (e == null) ? null :new AbstractMap.SimpleImmutableEntry<>(e);
}final Entry<K,V> getCeilingEntry(K key) {Entry<K,V> p = root;// 二叉查找遍历红黑树while (p != null) {// 比较 keyint cmp = compare(key, p.key);// 当前节点比 key 大，则遍历左子树，这样缩小节点的值if (cmp < 0) {// 如果有左子树，则遍历左子树if (p.left != null)p = p.left;// 如果没有，则直接返回该节点elsereturn p;// 当前节点比 key 小，则遍历右子树，这样放大节点的值} else if (cmp > 0) {// 如果有右子树，则遍历右子树if (p.right != null) {p = p.right;} else {// 找到当前的后继节点Entry<K,V> parent = p.parent;Entry<K,V> ch = p;while (parent != null && ch == parent.right) {ch = parent;parent = parent.parent;}return parent;}// 如果相等，则返回该节点即可} elsereturn p;}return null;
}

• 逻辑很简单。就是二叉查找。
• 如果遍历的当前结点大。则去左子树中找。如果左子树不存在 则返回当前结点。
• 如果遍历的当前结点小。则去右子树中找。如果右子树不存在。则去找当前结点的中序遍历的后继。然后返回。

#higherEntry(K key) 方法，大于 key 的节点。代码如下：

public Map.Entry<K,V> higherEntry(K key) {return exportEntry(getHigherEntry(key));
}final Entry<K,V> getHigherEntry(K key) {Entry<K,V> p = root;// 循环二叉查找遍历红黑树while (p != null) {// 比较 keyint cmp = compare(key, p.key);// 当前节点比 key 大，则遍历左子树，这样缩小节点的值if (cmp < 0) {// 如果有左子树，则遍历左子树if (p.left != null)p = p.left;// 如果没有，则直接返回该节点elsereturn p;// 当前节点比 key 小，则遍历右子树，这样放大节点的值} else {// 如果有右子树，则遍历右子树if (p.right != null) {p = p.right;} else {// 找到当前的后继节点Entry<K,V> parent = p.parent;Entry<K,V> ch = p;while (parent != null && ch == parent.right) {ch = parent;parent = parent.parent;}return parent;}}// 此处，相等的情况下，不返回}// 查找不到，返回 nullreturn null;
}

• 和 #ceilingEntry(K key) 逻辑的差异，相等的情况下，不返回该节点。

#ceilingEntry(K key) 方法，小于等于 key 的节点。代码如下：

public Map.Entry<K,V> floorEntry(K key) {return exportEntry(getFloorEntry(key));
}final Entry<K,V> getFloorEntry(K key) {Entry<K,V> p = root;// 循环二叉查找遍历红黑树while (p != null) {// 比较 keyint cmp = compare(key, p.key);if (cmp > 0) {// 如果有右子树，则遍历右子树if (p.right != null)p = p.right;// 如果没有，则直接返回该节点elsereturn p;// 当前节点比 key 小，则遍历右子树，这样放大节点的值} else if (cmp < 0) {// 如果有左子树，则遍历左子树if (p.left != null) {p = p.left;} else {// 找到当前节点的前继节点Entry<K,V> parent = p.parent;Entry<K,V> ch = p;while (parent != null && ch == parent.left) {ch = parent;parent = parent.parent;}return parent;}// 如果相等，则返回该节点即可} elsereturn p;}// 查找不到，返回 nullreturn null;
}

• 思路没啥变化。

#getLowerEntry(K key) 方法，小于 key 的节点。代码如下：

public Map.Entry<K,V> lowerEntry(K key) {return exportEntry(getLowerEntry(key));
}final Entry<K,V> getLowerEntry(K key) {Entry<K,V> p = root;// 循环二叉查找遍历红黑树while (p != null) {// 比较 keyint cmp = compare(key, p.key);// 当前节点比 key 小，则遍历右子树，这样放大节点的值if (cmp > 0) {// 如果有右子树，则遍历右子树if (p.right != null)p = p.right;// 如果没有，则直接返回该节点elsereturn p;// 当前节点比 key 大，则遍历左子树，这样缩小节点的值} else {// 如果有左子树，则遍历左子树if (p.left != null) {p = p.left;} else {// 找到当前节点的前继节点Entry<K,V> parent = p.parent;Entry<K,V> ch = p;while (parent != null && ch == parent.left) {ch = parent;parent = parent.parent;}return parent;}}// 此处，相等的情况下，不返回}// 查找不到，返回 nullreturn null;
}

在一些场景下，我们并不需要返回 Entry 节点，只需要返回符合条件的 key 即可。所以有了对应的如下四个方法：

// TreeMap.javapublic K lowerKey(K key) {return keyOrNull(getLowerEntry(key));
}public K floorKey(K key) {return keyOrNull(getFloorEntry(key));
}public K ceilingKey(K key) {return keyOrNull(getCeilingEntry(key));
}public K higherKey(K key) {return keyOrNull(getHigherEntry(key));
}static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {return (e == null) ? null : e.key;
}

10. 获得首尾的元素

#firstEntry() 方法，获得首个 Entry 节点。代码如下：

public Map.Entry<K,V> firstEntry() {return exportEntry(getFirstEntry());
}final Entry<K,V> getFirstEntry() {Entry<K,V> p = root;if (p != null)// 循环，不断遍历到左子节点，直到没有左子节点while (p.left != null)p = p.left;return p;
}

• 通过不断遍历到左子节点，直到没有左子节点。

• 在 #getFirstEntry() 方法的基础上，还提供了另外两个方法：

  // TreeMap.javapublic Map.Entry<K,V> pollFirstEntry() { // 获得并移除首个 Entry 节点// 获得首个 Entry 节点Entry<K,V> p = getFirstEntry();Map.Entry<K,V> result = exportEntry(p);// 如果存在，则进行删除。if (p != null)deleteEntry(p);return result;
  }public K firstKey() {return key(getFirstEntry());
  }
  static <K> K key(Entry<K,?> e) {if (e == null) // 如果不存在 e 元素，则抛出 NoSuchElementException 异常throw new NoSuchElementException();return e.key;
  }
  

#lastEntry() 方法，获得尾部 Entry 节点。代码如下：

// TreeMap.javapublic Map.Entry<K,V> lastEntry() {return exportEntry(getLastEntry());
}final Entry<K,V> getLastEntry() { Entry<K,V> p = root;if (p != null)// 循环，不断遍历到右子节点，直到没有右子节点while (p.right != null)p = p.right;return p;
}

• 通过不断遍历到右子节点，直到没有右子节点。

• 在 #getLastEntry() 方法的基础上，还提供了另外两个方法：

  // TreeMap.javapublic Map.Entry<K,V> pollLastEntry() { // 获得并移除尾部 Entry 节点// 获得尾部 Entry 节点Entry<K,V> p = getLastEntry();Map.Entry<K,V> result = exportEntry(p);// 如果存在，则进行删除。if (p != null)deleteEntry(p);return result;
  }public K lastKey() {return key(getLastEntry());
  }
  

在这里，补充一个 #containsValue(Object value) 方法，通过中序遍历的方式，遍历查找值为 value 的节点是否存在。代码如下：

// TreeMap.javapublic boolean containsValue(Object value) {for (Entry<K,V> e = getFirstEntry(); // 获得首个 Entry 节点e != null;  // 遍历到没有下一个节点e = successor(e)) { // 通过中序遍历，获得下一个节点if (valEquals(value, e.value)) // 判断值是否相等return true;}return false;
}static final boolean valEquals(Object o1, Object o2) {return (o1==null ? o2==null : o1.equals(o2));
}

11. 清空

#clear() 方法，清空。代码如下：

// TreeMap.javapublic void clear() {// 增加修改次数modCount++;// key-value 数量置为 0size = 0;// 设置根节点为 nullroot = null;
}

12. 克隆

#clone() 方法，克隆 TreeMap 。代码如下：

// TreeMap.javapublic Object clone() {// 克隆创建 TreeMap 对象TreeMap<?,?> clone;try {clone = (TreeMap<?,?>) super.clone();} catch (CloneNotSupportedException e) {throw new InternalError(e);}// Put clone into "virgin" state (except for comparator)// 重置 clone 对象的属性clone.root = null;clone.size = 0;clone.modCount = 0;clone.entrySet = null;clone.navigableKeySet = null;clone.descendingMap = null;// Initialize clone with our mappings// 使用自己，构造 clone 对象的红黑树try {clone.buildFromSorted(size, entrySet().iterator(), null, null);} catch (java.io.IOException | ClassNotFoundException cannotHappen) {}return clone;
}

13. 序列化

#writeObject(ObjectOutputStream s) 方法，序列化 TreeMap 对象。代码如下：

// TreeMap.java@java.io.Serial
private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException {// Write out the Comparator and any hidden stuff// 写入非静态属性、非 transient 属性s.defaultWriteObject();// Write out size (number of Mappings)// 写入 key-value 键值对数量s.writeInt(size);// Write out keys and values (alternating)// 写入具体的 key-value 键值对for (Map.Entry<K, V> e : entrySet()) {s.writeObject(e.getKey());s.writeObject(e.getValue());}
}

14. 反序列化

#readObject(ObjectInputStream s) 方法，反序列化成 TreeMap 对象。代码如下：

// TreeMap.java@java.io.Serial
private void readObject(final java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {// Read in the Comparator and any hidden stuff// 读取非静态属性、非 transient 属性s.defaultReadObject();// Read in size// 读取 key-value 键值对数量 sizeint size = s.readInt();// 使用输入流，构建红黑树。// 因为序列化时，已经是顺序的，所以输入流也是顺序的buildFromSorted(size, null, s, null); // 注意，此时传入的是 s 参数，输入流
}

15. 转换成 Set/Collection

15.1 keySet

#keySet() 方法，获得正序的 key Set 。代码如下：

/*** 正序的 KeySet 缓存对象*/
private transient KeySet<K> navigableKeySet;public Set<K> keySet() {return navigableKeySet();
}public NavigableSet<K> navigableKeySet() {KeySet<K> nks = navigableKeySet;return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
}

15.2 descendingKeySet

#descendingKeySet() 方法，获得倒序的 key Set 。代码如下：

/*** 倒序的 NavigableMap 缓存对象*/
private transient NavigableMap<K,V> descendingMap;public NavigableSet<K> descendingKeySet() {return descendingMap().navigableKeySet();
}public NavigableMap<K, V> descendingMap() {NavigableMap<K, V> km = descendingMap;return (km != null) ? km :(descendingMap = new DescendingSubMap<>(this,true, null, true,true, null, true));
}

15.3 values

#values() 方法，获得 value 集合。代码如下：

public Collection<V> values() {Collection<V> vs = values;if (vs == null) {vs = new Values();values = vs; // values 缓存，来自 AbstractMap 的属性}return vs;
}

15.4 entrySet

#entrySet() 方法，获得 Entry 集合。代码如下：

/*** Entry 缓存集合*/
private transient EntrySet entrySet;public Set<Map.Entry<K,V>> entrySet() {EntrySet es = entrySet;return (es != null) ? es : (entrySet = new EntrySet());
}