项目
博客
文档
归档
资源链接
关于我
项目
博客
文档
归档
资源链接
关于我
JDK 源码解析 —— 集合（六）TreeMap
2020-11-13
·
芋道源码
·
转载
·
·
本文共 8,820个字，预计阅读需要 30分钟。
> `转载`于【[芋道源码](http://svip.iocoder.cn/)】 ## 1. 概述 在 [《JDK 源码解析 —— 集合（四）哈希表 LinkedHashMap》](http://svip.iocodder.cn/JDK/Collection-LinkedHashMap) 中，我们提到了两种**有序** Map 的选择。一种是 LinkedHashMap ，以前在该文进行了详细解析，而本文，我们开始 TreeMap 之旅，**按照 key 的顺序**的 Map 实现类。 在开始之前，艿艿捉摸了下，什么业务场景下适合使用 TreeMap 呢？发现好像基本没有，嘿嘿。然后，我又翻了自己团队的几个项目，发现唯一在使用的，就是在 [签名生成算法](https://pay.weixin.qq.com/wiki/doc/api/jsapi.php?chapter=4_3) 时，要求按照请求参数的 key 排序，然后拼接后加密。如果胖友有 TreeMap 的使用场景，请一定在星球给留言，艿艿可以补充到本文。 ## 2. 类图 TreeMap 实现的接口、继承的类，如下图所示：[](http://static.iocoder.cn/images/JDK/2019_12_13_02/01.png)类图 - 实现 [`java.util.Map`](https://github.com/YunaiV/openjdk/blob/master/src/java.base/share/classes/java/util/Map.java) 接口，并继承 [`java.util.AbstractMap`](https://github.com/YunaiV/openjdk/blob/master/src/java.base/share/classes/java/util/AbstractMap.java) 抽像类。 - 直接实现`java.util.NavigableMap`接口，间接实现`java.util.NavigableMap`接口。关于这两接口的定义的操作，已经添加注释，胖友可以直接点击查看。因为 SortedMap 有很多雷同的寻找最接近 key 的操作，这里简单总结下： - lower ：小于 ；floor ：小于等于 - higher ：大于；ceiling ：大于等于 - 实现 [`java.io.Serializable`](https://github.com/YunaiV/openjdk/blob/master/src/java.base/share/classes/java/io/Serializable.java) 接口。 - 实现 [`java.lang.Cloneable`](https://github.com/YunaiV/openjdk/blob/master/src/java.base/share/classes/java/lang/Cloneable.java) 接口。 ## 3. 属性 在开始看 TreeMap 的具体属性之前，我们先来简单说说 TreeMap 的实现原理。 在 [《JDK 源码解析 —— 集合（三）哈希表 HashMap》](http://svip.iocoder.cn/JDK/Collection-HashMap) 文章中，我们提到，HashMap 的数组，每个桶的链表在元素过多的情况下，会转换成**红黑树**。而 TreeMap 也是基于红黑树实现的，并且只是**一棵**红黑树。所以 TreeMap 可以理解成 HashMap 数组中的**一个**转换成**红黑树**的桶。 为什么 TreeMap 会采用红黑树实现呢？我们来看一段红黑树的定义： > FROM [《维基百科 —— 红黑树》](https://zh.wikipedia.org/wiki/红黑树) > > **红黑树**（英语：Red–black tree）是一种[自平衡二叉查找树](https://zh.wikipedia.org/wiki/自平衡二叉查找树)，是在[计算机科学](https://zh.wikipedia.org/wiki/计算机科学)中用到的一种[数据结构](https://zh.wikipedia.org/wiki/数据结构)，典型的用途是实现[关联数组](https://zh.wikipedia.org/wiki/关联数组)。 > > 它在 1972 年由[鲁道夫·贝尔](https://zh.wikipedia.org/wiki/鲁道夫·贝尔)发明，被称为”**对称二叉B树**“，它现代的名字源于 Leo J. Guibas 和 [Robert Sedgewick](https://zh.wikipedia.org/wiki/Robert_Sedgewick) 于 [1978年] (https://zh.wikipedia.org/wiki/1978年) 写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况[运行时间](https://zh.wikipedia.org/wiki/算法分析)，并且在实践中高效：它可以在 `logN` 时间内完成查找，插入和删除，这里的 `N` 是树中元素的数目。 - **有序性**：红黑树是一种**二叉查找树**，父节点的 key 小于左子节点的 key ，大于右子节点的 key 。这样，就完成了 TreeMap 的有序的特性。 - **高性能**：红黑树会进行**自平衡**，避免树的高度过高，导致查找性能下滑。这样，红黑树能够提供 `logN` 的时间复杂度。 > 艿艿：绝大多数情况下，包括面试，我们无需了解红黑树是怎么实现的，甚至原理是什么。只要知道，红黑树的上述概念，和时间复杂度即可。 > > 所以，本文我们不会涉及红黑树的**自平衡**的内容。如果感兴趣的胖友，可以自己阅读如下的文章： > > - [《教你初步了解红黑树》](https://blog.csdn.net/v_july_v/article/details/6105630) > - [《史上最清晰的红黑树讲解（上）》](https://www.cnblogs.com/CarpenterLee/p/5503882.html) > - [《史上最清晰的红黑树讲解（下）》](https://www.cnblogs.com/CarpenterLee/p/5525688.html) 下面，让我们来看看 TreeMap 的属性。代码如下： ``` // TreeMap.java /** * key 排序器 */ private final Comparator<? super K> comparator; /** * 红黑树的根节点 */ private transient Entry<K,V> root; /** * key-value 键值对数量 */ private transient int size = 0; /** * 修改次数 */ private transient int modCount = 0; ``` - `comparator` 属性，key 排序器。通过该属性，可以自定义 key 的排序规则。如果未设置，则使用 key 类型自己的排序。 - `root` 属性，红黑树的根节点。其中，Entry 是 TreeMap 的内部静态类，代码如下： ``` // TreeMap.java /** * 颜色 - 红色 */ private static final boolean RED = false; /** * 颜色 - 黑色 */ private static final boolean BLACK = true; static final class Entry<K,V> implements Map.Entry<K,V> { /** * key 键 */ K key; /** * value 值 */ V value; /** * 左子节点 */ Entry<K,V> left; /** * 右子节点 */ Entry<K,V> right; /** * 父节点 */ Entry<K,V> parent; /** * 颜色 */ boolean color = BLACK; // ... 省略一些 } ``` ## 4. 构造方法 TreeMap 一共有四个构造方法，我们分别来看看。 **① `#TreeMap()`** ``` // TreeMap.java public TreeMap() { comparator = null; } ``` - 默认构造方法，不使用自定义排序，所以此时 `comparator` 为空。 **② `#TreeMap(Comparator<? super K> comparator)`** ``` // TreeMap.java public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; } ``` - 可传入 `comparator` 参数，自定义 key 的排序规则。 **③ `#TreeMap(SortedMap<K, ? extends V> m)`** ``` // TreeMap.java public TreeMap(SortedMap<K, ? extends V> m) { // <1> 设置 comparator 属性 comparator = m.comparator(); try { // <2> 使用 m 构造红黑树 buildFromSorted(m.size(), m.entrySet().iterator(), null, null); } catch (java.io.IOException | ClassNotFoundException cannotHappen) { } } ``` - 传入已经排序的 `m` ，然后构建出 TreeMap 。 - `<1>` 处，使用 `m` 的 key 排序器，设置到 `comparator` 属性。 - `<2>` 处，调用 `#buildFromSorted(int size, Iterator<?> it, ObjectInputStream str, V defaultVal)` 方法，使用 `m` 构造红黑树。因为 `m` 是 SortedMap 类型，所以天然**有序**，所以可以基于 `m` 的中间为红黑树的根节点，`m` 的左边为左子树，`m` 的右边为右子树。😈 胖友，发挥下自己的想象力。 `#buildFromSorted(int size, Iterator<?> it, ObjectInputStream str, V defaultVal)` ，代码如下： ``` // TreeMap.java private void buildFromSorted(int size, Iterator<?> it, java.io.ObjectInputStream str, V defaultVal) throws java.io.IOException, ClassNotFoundException { // <1> 设置 key-value 键值对的数量 this.size = size; // <2> computeRedLevel(size) 方法，计算红黑树的高度 // <3> 使用 m 构造红黑树，返回根节点 root = buildFromSorted(0, 0, size - 1, computeRedLevel(size), it, str, defaultVal); } ``` - `<1>` 处，设置 key-value 键值对的数量到 `size` 。 - `<2>` 处，调用 `#computeRedLevel(int size)` 方法，计算红黑树的高度。代码如下： ``` // TreeMap.java private static int computeRedLevel(int size) { return 31 - Integer.numberOfLeadingZeros(size + 1); } ``` - `<3>` 处，调用 `#buildFromSorted(int level, int lo, int hi, int redLevel, Iterator<?> it, ObjectInputStream str, V defaultVal)` 方法，使用 `m` 构造红黑树，返回根节点。 `#buildFromSorted(int level, int lo, int hi, int redLevel, Iterator<?> it, ObjectInputStream str, V defaultVal)` 方法，代码如下： ``` // TreeMap.java 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. */ // <1.1> 递归结束 if (hi < lo) return null; // <1.2> 计算中间值 int mid = (lo + hi) >>> 1; // <2.1> 创建左子树 Entry<K,V> left = null; if (lo < mid) // <2.2> 递归左子树 left = buildFromSorted(level + 1, lo, mid - 1, redLevel, it, str, defaultVal); // extract key and/or value from iterator or stream // <3.1> 获得 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(); // 读取 key value = (V) entry.getValue(); // 读取 value } else { key = (K)it.next(); // 读取 key value = defaultVal; // 设置 default 为 value } } else { // use stream 处理 str 流的情况 key = (K) str.readObject(); // 从 str 读取 key 值 value = (defaultVal != null ? defaultVal : (V) str.readObject()); // 从 str 读取 value 值 } // <3.2> 创建中间节点 Entry<K,V> middle = new Entry<>(key, value, null); // color nodes in non-full bottommost level red // <3.3> 如果到树的最大高度，则设置为红节点 if (level == redLevel) middle.color = RED; // <3.4> 如果左子树非空，则进行设置 if (left != null) { middle.left = left; // 当前节点，设置左子树 left.parent = middle; // 左子树，设置父节点为当前节点 } // <4.1> 创建右子树 if (mid < hi) { // <4.2> 递归右子树 Entry<K,V> right = buildFromSorted(level + 1, mid + 1, hi, redLevel, it, str, defaultVal); // <4.3> 当前节点，设置右子树 middle.right = right; // <4.3> 右子树，设置父节点为当前节点 right.parent = middle; } // 返回当前节点 return middle; } ``` - 基于**有序**的 `it` 迭代器或者 `str` 输入流，将其的中间点作为根节点，其左边作为左子树，其右边作为右子树。因为是基于递归实现，所以中间点是基于 `lo` 和 `hi` 作为 `it` 或 `str` 的“数组”范围。 > 如果胖友有学习过数据结构与算法，这里代码的实现，就是基于 [《五大常用算法之一：分治算法》](https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741370.html) 。 - `<1.1>` 处，如果 `hi` 小于 `lo` ，说明已经超过范围，所以可以结束循环。 - `<1.2>` 处，计算中间位置。 - 左子树 - `<2.1>` 处，处理 `mid` 中间位置的左边，处理左子树。 - `<2.2>` 处，调用 `#buildFromSorted(int level, int lo, int hi, int redLevel, Iterator<?> it, ObjectInputStream str, V defaultVal)` 方法，递归处理 `it` 或 `str` 的 `[lo, mid - 1]` 范围，创建左子树，返回该子树的根节点，赋值给 `left` 。 - 当前节点（中间节点） - `<3.1>` 处，获得 key-value 键值对。分成使用 `it` 或 `str` 读取的两种情况。有一点要注意，在 `defaultVal` 非空的时候，使用它作为 value 。 - `<3.2>` 处，创建当前节点。 - `<3.3>` 处，如果到树的最大高度，则设置为红节点。 - `<3.4>` 处，如果左子树非空，则进行设置。 - 右子树 - `<4.1>` 处，处理 `mid` 中间位置的右边，处理右子树。 - `<4.2>` 处，调用 `#buildFromSorted(int level, int lo, int hi, int redLevel, Iterator<?> it, ObjectInputStream str, V defaultVal)` 方法，递归处理 `it` 或 `str` 的 `[mid + 1, high]` 范围，创建右子树，返回该子树的根节点，赋值给 `right` 。 - `<4.3>` 处，设置右子树。 - 返回当前节点。因为是递归，所以递归的第一层，是 TreeMap 红黑树的根节点。 **④ `#TreeMap(Map<? extends K, ? extends V> m)`** ``` // TreeMap.java public TreeMap(Map<? extends K, ? extends V> m) { comparator = null; // 添加所有元素 putAll(m); } ``` - 传入 `m` 的是 Map 类型，构建成初始的 TreeMap 。 - 调用 `#putAll(Map<? extends K, ? extends V> map)` 方法，添加所有元素。 `#putAll(Map<? extends K, ? extends V> map)` 方法，代码如下： ``` // TreeMap.java public void putAll(Map<? extends K, ? extends V> map) { // <1> 路径一，满足如下条件，调用 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; } } // <2> 路径二，直接遍历 map 来添加 super.putAll(map); } ``` - 分成 `<1>` 和 `<2>` 两种情况。其中，`<1>` 是作为优化的方式，处理在 TreeMap 为空时，并且 `map` 为 SortedMap 类型时，可以直接调用 `#buildFromSorted(int level, int lo, int hi, int redLevel, Iterator<?> it, ObjectInputStream str, V defaultVal)` 方法，可以基于 SortedMap 顺序迭代插入即可，性能更优。 ## 5. 添加单个元素 `#put(K key, V value)` 方法，添加单个元素。代码如下： ``` // TreeMap.java public V put(K key, V value) { // 记录当前根节点 Entry<K,V> t = root; // <1> 如果无根节点，则直接使用 key-value 键值对，创建根节点 if (t == null) { // <1.1> 校验 key 类型。 compare(key, key); // type (and possibly null) check // <1.2> 创建 Entry 节点 root = new Entry<>(key, value, null); // <1.3> 设置 key-value 键值对的数量 size = 1; // <1.4> 增加修改次数 modCount++; return null; } // <2> 遍历红黑树 int cmp; // key 比父节点小还是大 Entry<K,V> parent; // 父节点 // split comparator and comparable paths Comparator<? super K> cpr = comparator; if (cpr != null) { // 如果有自定义 comparator ，则使用它来比较 do { // <2.1> 记录新的父节点 parent = t; // <2.2> 比较 key cmp = cpr.compare(key, t.key); // <2.3> 比 key 小，说明要遍历左子树 if (cmp < 0) t = t.left; // <2.4> 比 key 大，说明要遍历右子树 else if (cmp > 0) t = t.right; // <2.5> 说明，相等，说明要找到的 t 就是 key 对应的节点，直接设置 value 即可。 else return t.setValue(value); } while (t != null); // <2.6> } else { // 如果没有自定义 comparator ，则使用 key 自身比较器来比较 if (key == null) // 如果 key 为空，则抛出异常 throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; do { // <2.1> 记录新的父节点 parent = t; // <2.2> 比较 key cmp = k.compareTo(t.key); // <2.3> 比 key 小，说明要遍历左子树 if (cmp < 0) t = t.left; // <2.4> 比 key 大，说明要遍历右子树 else if (cmp > 0) t = t.right; // <2.5> 说明，相等，说明要找到的 t 就是 key 对应的节点，直接设置 value 即可。 else return t.setValue(value); } while (t != null); // <2.6> } // <3> 创建 key-value 的 Entry 节点 Entry<K,V> e = new Entry<>(key, value, parent); // 设置左右子树 if (cmp < 0) // <3.1> parent.left = e; else // <3.2> parent.right = e; // <3.3> 插入后，进行自平衡 fixAfterInsertion(e); // <3.4> 设置 key-value 键值对的数量 size++; // <3.5> 增加修改次数 modCount++; return null; } ``` - 虽然比较长，逻辑还是相对清晰的。因为红黑树是二叉查找树，所以我们可以使用二分查找的方式遍历红黑树。循环遍历红黑树的节点，根据不同的结果，进行处理： - 如果当前节点比 `key` 小，则遍历左子树。 - 如果当前节点比 `key` 大，则遍历右子树。 - 如果当前节点比 `key` 相等，则直接设置该节点的 `value` 即可。 - 如果遍历到叶子节点，无法满足上述情况，则说明我们需要给 key-value 键值对，创建 Entry 节点。如果比叶子节点小，则作为左子树；如果比叶子节点大，则作为右子树。 - `<1>` 处，如果无根节点，则直接使用 key-value 键值对，创建根节点。 - `<1.1>` 处，调用 `#compare(Object k1, Object k2)` 方法， 比较 `key` 。代码如下： ``` // TreeMap.java final int compare(Object k1, Object k2) { return comparator == null ? ((Comparable<? super K>)k1).compareTo((K)k2) // 如果没有自定义 comparator 比较器，则使用 key 自身比较 : comparator.compare((K)k1, (K)k2); // 如果有自定义 comparator 比较器，则使用它来比较。 } ``` - 根据是否有自定义的 `comparator` 比较器，进行 key 的比较。 - `<1.2>` 处，创建 key-value 键值对的 Entry 节点，并赋值给 `root` 节点。 - <2>处，遍历红黑树。会分成是否有自定义的comparator作为遍历左右节点的比较器，逻辑是相同的。所以，我们只看cpr != null的部分先。 - `<2.1>` 处，记录新的父节点。目的是，如果遍历到叶子节点 `t` 时，无法继续遍历时，此时 `parent` 作为被插入的父节点。 - `<2.2>` 处，比较 key 。 - `<2.3>` 处， 比 `key` 小，说明要遍历左子树。 - `<2.4>` 处，比 `key` 大，说明要遍历右子树。 - `<2.5>` 处，相等，说明要找到的 `t` 就是 `key` 对应的节点，直接设置 value 即可。 - `<2.6>` 处，通过 `while(t != null)` 来不断遍历，而 `t` 作为当前遍历到的节点。如果遍历到 `t` 为空时，说明二分查找不到 `key` 对应的节点，此时只能创建 key-value 的节点，根据 `key` 大小作为 `parent` 的左右节点。 - <3>处，创建 key-value 的 Entry 节点。 - `<3.1>` 处，如果 `key` 比 `parent` 节点的 key 小，作为 `parent` 的左子节点。 - `<3.2>` 处，如果 `key` 比 `parent` 节点的 key 大，作为 `parent` 的右子节点。 - `<3.3>` 处，调用 `fixAfterInsertion(Entry<K,V> x)` 方法，插入后，进行**自平衡**。关于这块，我们就先不进行深入了。 另外，因为 TreeMap 是基于树的结构实现，所以无需考虑扩容问题。 ## 6. 获得单个元素 `#get(Object key)` 方法，获得 `key` 对应的 value 值。代码如下： ``` // TreeMap.java public 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 相等，则返回该节点 else return p; } // 查找不到，返回 null return 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 相等，则返回该节点 else return p; } } // 查找不到，返回 null return null; } ``` - 和我们在 [「5. 添加单个元素」](http://svip.iocoder.cn/JDK/Collection-TreeMap/#) 中看到的，也是基于红黑树进行二分查找，逻辑是一致的。 - 如果未自定义 `comparator` 比较器，则调用 `#getEntry(Object key)` 方法，使用 key 自身的排序，进行比较二分查找。 - 如果有自定义 `comparator` 比较器，则调用 `#getEntryUsingComparator(Object key)` 方法，使用 `comparator` 的排序，进行比较二分查找。 `#containsKey(Object key)` 方法，判断是否存在指定 key 。代码如下： ``` // TreeMap.java public boolean containsKey(Object key) { return getEntry(key) != null; } ``` - 基于 `#getEntry(key)` 方法来实现。 ## 7. 删除单个元素 相比 [「5. 添加单个元素」](http://svip.iocoder.cn/JDK/Collection-TreeMap/#) 来说，删除会更加复杂一些。所以呢，我们先看删除的四种情况。为了让案例更加复杂，我们会使用一颗二叉查找树来举例子。因为，在去掉自平衡的逻辑的情况下，红黑树的删除和二叉查查找树的删除逻辑是一致的。 对于二叉查找树的删除，需要保证删除节点后，能够继续满足**二叉**和**查找**的特性。 [](http://static.iocoder.cn/images/JDK/2019_12_13_02/02.png)查找二叉树 > 该图通过 http://btv.melezinek.cz/binary-search-tree.html 绘制，胖友可以通过使用它，辅助理解这个过程。 情况一，无子节点。 直接删除父节点对其的指向即可。 例如说，叶子节点 5、11、14、18 。 情况二，**只**有左子节点。 将删除节点的父节点，指向删除节点的左子节点。 例如说，节点 20 。可以通过将节点 15 的右子节点指向节点 19 。 情况三，**只**有右子节点。 和情况二的处理方式一致。将删除节点的父节点，指向删除节点的右子节点。 图中暂无示例，胖友自己脑补下，嘿嘿。 情况四，有左子节点 + 右子节点。 这种情况，相对会比较复杂，因为无法使用子节点替换掉删除的节点。所以此时有一个巧妙的思路。我们结合删除节点 15 来举例。 - 1、先查找节点 15 的右子树的**最小值**，找到是节点 17 。 - 2、将节点 17 设置到节点 15 上。因为节点 17 是右子树的最小值，能够满足比节点 15 的左子树都大，右子树都小。这样，问题就可以变成删除节点 17 。 - 3、删除节点 17 的过程，满足情况三。将节点 19 的左子节点指向节点 18 即可。 理解完这四种情况后，我们来看看代码。`#remove(Object key)` 方法，移除 `key` 对应的 Entry 节点。代码如下： ``` // TreeMap.java public V remove(Object key) { // <1> 获得 key 对应的 Entry 节点 Entry<K,V> p = getEntry(key); // <2> 如果不存在，则返回 null ，无需删除 if (p == null) return null; V oldValue = p.value; // <3> 删除节点 deleteEntry(p); return oldValue; } ``` - `<1>` 处，调用 `#getEntry(Object key)` 方法，获得 `key` 对应的 Entry 节点。 - `<2>` 处，如果不存在，则返回 `null` ，无需删除。 - `<3>` 处，调用 `#deleteEntry(Entry<K,V> p)` 方法，删除该节点。 `#deleteEntry(Entry<K,V> p)` 方法，代码如下： ``` // TreeMap.java private void deleteEntry(Entry<K,V> p) { // 增加修改次数 modCount++; // 减少 key-value 键值对数 size--; // If strictly internal, copy successor's element to p and then make p // point to successor. // <1> 如果删除的节点 p 既有左子节点，又有右子节点， if (p.left != null && p.right != null) { // <1.1> 获得右子树的最小值 Entry<K,V> s = successor(p); // <1.2> 修改 p 的 key-value 为 s 的 key-value 键值对 p.key = s.key; p.value = s.value; // <1.3> 设置 p 指向 s 。此时，就变成删除 s 节点了。 p = s; } // p has 2 children // Start fixup at replacement node, if it exists. // <2> 获得替换节点 Entry<K,V> replacement = (p.left != null ? p.left : p.right); // <3> 有子节点的情况 if (replacement != null) { // Link replacement to parent // <3.1> 替换节点的父节点，指向 p 的父节点 replacement.parent = p.parent; // <3.2.1> 如果 p 的父节点为空，则说明 p 是根节点，直接 root 设置为替换节点 if (p.parent == null) root = replacement; // <3.2.2> 如果 p 是父节点的左子节点，则 p 的父子节的左子节指向替换节点 else if (p == p.parent.left) p.parent.left = replacement; // <3.2.3> 如果 p 是父节点的右子节点，则 p 的父子节的右子节指向替换节点 else p.parent.right = replacement; // Null out links so they are OK to use by fixAfterDeletion. // <3.3> 置空 p 的所有指向 p.left = p.right = p.parent = null; // Fix replacement // <3.4> 如果 p 的颜色是黑色，则执行自平衡 if (p.color == BLACK) fixAfterDeletion(replacement); // <4> 如果 p 没有父节点，说明删除的是根节点，直接置空 root 即可 } else if (p.parent == null) { // return if we are the only node. root = null; // <5> 如果删除的没有左子树，又没有右子树 } else { // No children. Use self as phantom replacement and unlink. // <5.1> 如果 p 的颜色是黑色，则执行自平衡 if (p.color == BLACK) fixAfterDeletion(p); // <5.2> 删除 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; } } } ``` - <1>处，如果删除的节点p既有左子节点，又有右子节点，则符合我们提到的情况四。在这里，我们需要将其转换成情况三。 - `<1.1>` 处，调用 `#successor(Entry<K,V> t)` 方法，获得右子树的最小值。这里，我们先不深究 `#successor(Entry<K,V> t)` 方法的具体代码，知道在这里的用途即可。 - `<1.2>` 处，修改 `p` 的 key-value 为 `s` 的 key-value 键值对。这样，我们就完成 `s` 对 `p` 的替换。 - `<1.3>` 处，设置 `p` 指向 `s` 。此时，就变成删除 `s` 节点了。此时，情况四就转换成了情况三了。 - `<2>` 处，获得替换节点。此时对于 `p` 来说，至多有一个子节点，要么左子节点，要么右子节点，要么没有子节点。 - <3>处，有左子节点，或者右子节点的情况： - `<3.1>` 处，替换节点的父节点，指向 `p` 的父节点。 - `<3.2.1>` + `<3.2.2>` + `<3.2.3>` 处，将 `p` 的父节点的子节点，指向替换节点。 - `<3.3>` 处， 置空 `p` 的所有指向。 - `<3.4>` 处，如果 p 的颜色是黑色，则调用 `#fixAfterDeletion(Entry<K,V> x)` 方法，执行自平衡。 - `<4>` 处，如果 `p` 没有父节点，说明删除的是根节点，直接置空 `root` 即可。 - <5>处，既没有左子树，又没有右子树的情况： - `<5.1>` 处，如果 p 的颜色是黑色，则调用 `#fixAfterDeletion(Entry<K,V> x)` 方法，执行自平衡。 - `<5.2>` 处，删除 `p` 和其父节点的相互指向。 这样一看，其实删除节点的逻辑，也并不是怎么复杂噢。感兴趣的胖友，可以去 LeetCode 找树的题目刷一刷，哈哈。 在前面，我们漏了一个 `#successor(Entry<K,V> t)` 静态方法，没有详细来看。获得 `t` 节点的后继节点，代码如下： ``` // TreeMap.java static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) { // <1> 如果 t 为空，则返回 null if (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; } } ``` - 对于树来说，会存在前序遍历，中序遍历，后续遍历。对于二叉查找树来说，中序遍历恰好满足 key **顺序递增**。所以，这个方法是基于中序遍历的方式，寻找传入 `t` 节点的后续节点，也是下一个比 `t` 大的节点。 - `<1>` 处，如果 `t` 为空，则返回 `null` 。 - `<2>` 处，如果 `t` 有右子树，则右子树的最小值，肯定是它的后继节点。胖友可以自己看下艿艿在代码里写的注释。在 `#deleteEntry(Entry<K,V> p)` 方法的 `<1.1>` 处，就走了这块代码分支逻辑。 - <3>处，如果t没有右子树，则需要向上遍历父节点。胖友可以自己看下艿艿在代码里写的注释，结合图来理解。 - 简单来说，**寻找第一个祖先节点 `p` 是其父节点的左子节点**。因为是中序遍历，该节点的左子树肯定已经遍历完，在没有右子节点的情况下，需要找到其所在的“大子树”，成为左子树的情况。 - 例如说，节点 14 来说，需要按照 `14 -> 13 -> 15` 的路径，从而找到节点 15 是其后继节点。 ## 8. 查找接近的元素 在 NavigableMap 中，定义了四个查找接近的元素： - `#lowerEntry(K key)` 方法，小于 `key` 的节点 - `#floorEntry(K key)` 方法，小于等于 `key` 的节点 - `#higherEntry(K key)` 方法，大于 `key` 的节点 - `#ceilingEntry(K key)` 方法，大于等于 `key` 的节点 我们逐个来看看哈。 `#ceilingEntry(K key)` 方法，大于等于 `key` 的节点。代码如下： ``` // TreeMap.java public Map.Entry<K,V> ceilingEntry(K key) { // <1> // <2> 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; // <3> 循环二叉查找遍历红黑树 while (p != null) { // <3.1> 比较 key int cmp = compare(key, p.key); // <3.2> 当前节点比 key 大，则遍历左子树，这样缩小节点的值 if (cmp < 0) { // <3.2.1> 如果有左子树，则遍历左子树 if (p.left != null) p = p.left; // <3.2.2.> 如果没有，则直接返回该节点 else return p; // <3.3> 当前节点比 key 小，则遍历右子树，这样放大节点的值 } else if (cmp > 0) { // <3.3.1> 如果有右子树，则遍历右子树 if (p.right != null) { p = p.right; } else { // <3.3.2> 找到当前的后继节点 Entry<K,V> parent = p.parent; Entry<K,V> ch = p; while (parent != null && ch == parent.right) { ch = parent; parent = parent.parent; } return parent; } // <3.4> 如果相等，则返回该节点即可 } else return p; } // <3.5> return null; } ``` - `<1>` 处，调用 `#getCeilingEntry(K key)` 方法，查找满足大于等于 `key` 的 Entry 节点。 - `<2>` 处，调用 `#exportEntry(TreeMap.Entry<K,V> e)` 方法，创建不可变的 SimpleImmutableEntry 节点。这样，避免使用者直接修改节点，例如说修改 `key` 导致破坏红黑树。 - 本质上，`#getCeilingEntry(K key)` 方法，是加强版的二叉树查找，在找不到 `key` 的情况下，找到比 `key` **大且最接近**的节点。 - `<3>` 处，循环二叉查找遍历红黑树，每一轮都会在 `<3.1>` 处，通过调用 `#compare(Object k1, Object k2)` 方法，比较当前节点的 key 与 `key` 的大小。 - `<3.4>` 处，当前节点和 `key` 相等，则返回该节点。此时，我们找到了和 `key` **相等**的节点。 - <3.2>处，当前节点比key大，则遍历左子树，这样缩小节点的值。 - `<3.2.1>` 处，如果有左子树，则遍历左子树。 - `<3.2.2>` 处，如果没有，则直接返回该节点。此时，我们找到的是比 `key` **大且最接近**的节点。 - <3.3>处，当前节点比key小，则遍历右子树，这样放大节点的值。 - `<3.3.1>` 处，如果有右子树，则遍历右子树。 - `<3.3.2>` 处，找到当前的后继节点。这小块的代码，和我们在 [「7. 删除单个元素」](http://svip.iocoder.cn/JDK/Collection-TreeMap/#) 的 `#successor(Entry<K,V> t)」` 方法的 `<3>` 处的代码是一致的。 - `<3.5>` 处，极端情况下，找不到，返回 `null` 。 对于 `<3.3.2>` 的逻辑，可能胖友理解起来会有一点懵逼。我们来看一个示例。如下图：[](http://static.iocoder.cn/images/JDK/2019_12_13_02/03.png)查找二叉树 - 假设查找节点 60 时，遍历路径为 `20 -> 30 -> 40 -> 50` ，此时没有右子树，查找后继节点为不存在，返回 `null`。 - 假设查找节点 19 时，遍历路径为 `20 -> 10 -> 15 -> 18` ，此时没有右子树，查找后继节点为节点 20 ，返回节点 20 。 > 艿艿：有点不造怎么特别理论的描述，为什么这样 `<3.3.2>` 的逻辑是成立的。 > > 从直观感受上来说，对于没有右子树的节点，其后继节点一定大于它。 > > 并且，以节点 10 举例子。在我们因为 `key` 比节点 20 小时，遍历其左子树 `leftTree` 。在找不到匹配的节点时，此时 `leftTree` 的根节点 20 ，肯定是满足比 `key` **大且最接近**的节点。恰好，根节点 20 就是节点 18 的后继节点。 > > 等后面我在想想怎么能够描述的更清楚。如果胖友有更好的解释，可以星球给艿艿留言。 > > 目前的话，可以多画图理解。 `#higherEntry(K key)` 方法，大于 `key` 的节点。代码如下： ``` // TreeMap.java 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) { // 比较 key int cmp = compare(key, p.key); // 当前节点比 key 大，则遍历左子树，这样缩小节点的值 if (cmp < 0) { // 如果有左子树，则遍历左子树 if (p.left != null) p = p.left; // 如果没有，则直接返回该节点 else return 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; } } // <X> 此处，相等的情况下，不返回 } // 查找不到，返回 null return null; } ``` - 和 `#ceilingEntry(K key)` 逻辑的差异，在于 `<X>` 处，相等的情况下，不返回该节点。 `#ceilingEntry(K key)` 方法，小于等于 `key` 的节点。代码如下： ``` // TreeMap.java 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) { // 比较 key int cmp = compare(key, p.key); if (cmp > 0) { // 如果有右子树，则遍历右子树 if (p.right != null) p = p.right; // 如果没有，则直接返回该节点 else return 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; } // 如果相等，则返回该节点即可 } else return p; } // 查找不到，返回 null return null; } ``` - 思路是一致的，胖友自己看下注释噢。 `#getLowerEntry(K key)` 方法，小于 `key` 的节点。代码如下： ``` // TreeMap.java 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) { // 比较 key int cmp = compare(key, p.key); // 当前节点比 key 小，则遍历右子树，这样放大节点的值 if (cmp > 0) { // 如果有右子树，则遍历右子树 if (p.right != null) p = p.right; // 如果没有，则直接返回该节点 else return 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; } } // 此处，相等的情况下，不返回 } // 查找不到，返回 null return null; } ``` - 思路是一致的，胖友自己看下注释噢。 在一些场景下，我们并不需要返回 Entry 节点，只需要返回符合条件的 key 即可。所以有了对应的如下四个方法： ``` // TreeMap.java public 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; } ``` ## 9. 获得首尾的元素 `#firstEntry()` 方法，获得首个 Entry 节点。代码如下： ``` // TreeMap.java 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.java public 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.java public 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.java public 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.java public 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)); } ``` ## 10. 清空 `#clear()` 方法，清空。代码如下： ``` // TreeMap.java public void clear() { // 增加修改次数 modCount++; // key-value 数量置为 0 size = 0; // 设置根节点为 null root = null; } ``` ## 11. 克隆 `#clone()` 方法，克隆 TreeMap 。代码如下： ``` // TreeMap.java public 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; } ``` ## 12. 序列化 `#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()); } } ``` - 比较简单，胖友自己瞅瞅即可。 ## 13. 反序列化 `#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 键值对数量 size int size = s.readInt(); // 使用输入流，构建红黑树。 // 因为序列化时，已经是顺序的，所以输入流也是顺序的 buildFromSorted(size, null, s, null); // 注意，此时传入的是 s 参数，输入流 } ``` ## 14. 获得迭代器 `#keyIterator()` 方法，获得 key 的**正序**迭代器。代码如下： ``` // TreeMap.java Iterator<K> keyIterator() { return new KeyIterator(getFirstEntry()); // 获得的是首个元素 } ``` - 创建的是 KeyIterator 迭代器。在 [「14.2 KeyIterator」](http://svip.iocoder.cn/JDK/Collection-TreeMap/#) 详细解析。 `#descendingKeyIterator()` 方法，获得 key 的**倒序**迭代器。代码如下： ``` // TreeMap.java Iterator<K> descendingKeyIterator() { return new DescendingKeyIterator(getLastEntry()); // 获得的是尾部元素 } ``` - 创建的是 DescendingKeyIterator 迭代器。在 [「14.3 DescendingKeyIterator」](http://svip.iocoder.cn/JDK/Collection-TreeMap/#) 详细解析。 不过上述两个方法，都不是 `public` 方法，只提供给 TreeMap 内部使用。 ### 14.1 PrivateEntryIterator PrivateEntryIterator ，实现 Iterator 接口，提供了 TreeMap 的通用实现 Iterator 的抽象类。代码如下： ``` // TreeMap.java 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 节点 // 记录当前节点 Entry<K,V> e = next; // 如果没有下一个，抛出 NoSuchElementException 异常 if (e == null) throw new NoSuchElementException(); // 如果发生了修改，抛出 ConcurrentModificationException 异常 if (modCount != expectedModCount) throw new ConcurrentModificationException(); // 获得 e 的后继节点，赋值给 next next = successor(e); // 记录最后返回的节点 lastReturned = e; // 返回当前节点 return e; } final Entry<K,V> prevEntry() { // 获得前一个 Entry 节点 // 记录当前节点 Entry<K,V> e = next; // 如果没有下一个，抛出 NoSuchElementException 异常 if (e == null) throw new NoSuchElementException(); // 如果发生了修改，抛出 ConcurrentModificationException 异常 if (modCount != expectedModCount) throw new ConcurrentModificationException(); // 获得 e 的前继节点，赋值给 next next = predecessor(e); // 记录最后返回的节点 lastReturned = e; // 返回当前节点 return e; } public void remove() { // 删除节点 // 如果当前返回的节点不存在，则抛出 IllegalStateException 异常 if (lastReturned == null) throw new IllegalStateException(); // 如果发生了修改，抛出 ConcurrentModificationException 异常 if (modCount != expectedModCount) throw new ConcurrentModificationException(); // deleted entries are replaced by their successors // 在 lastReturned 左右节点都存在的时候，实际在 deleteEntry 方法中，是将后继节点替换到 lastReturned 中 // 因此，next 需要指向 lastReturned if (lastReturned.left != null && lastReturned.right != null) next = lastReturned; // 删除节点 deleteEntry(lastReturned); // 记录新的修改次数 expectedModCount = modCount; // 置空 lastReturned lastReturned = null; } } ``` - 整体代码比较简单，胖友自己看看艿艿写的注释噢。 在上述代码中，我们会看到 `#predecessor(Entry<K,V> t)` 静态方法，我们来看看。获得 `t` 节点的前继节点，代码如下： ``` // TreeMap.java static <K,V> Entry<K,V> predecessor(Entry<K,V> t) { // 如果 t 为空，则返回 null if (t == null) return null; // 如果 t 的左子树非空，则取左子树的最大值 else if (t.left != null) { Entry<K,V> p = t.left; while (p.right != null) p = p.right; return p; // 如果 t 的左子树为空 } else { // 先获得 t 的父节点 Entry<K,V> p = t.parent; // 不断向上遍历父节点，直到子节点 ch 不是父节点 p 的左子节点 Entry<K,V> ch = t; while (p != null // 还有父节点 && ch == p.left) { // 继续遍历的条件，必须是子节点 ch 是父节点 p 的左子节点 ch = p; p = p.parent; } return p; } } ``` - 和 `#successor(Entry<K,V> t)` 方法，是一样的思路。所以，胖友跟着注释，自己再理解下。 ### 14.2 KeyIterator KeyIterator ，继承 PrivateEntryIterator 抽象类，key 的**正序**迭代器。代码如下： ``` // TreeMap.java final class KeyIterator extends PrivateEntryIterator<K> { KeyIterator(Entry<K,V> first) { super(first); } // 实现 next 方法，实现正序 public K next() { return nextEntry().key; } } ``` ### 14.3 DescendingKeyIterator DescendingKeyIterator ，继承 PrivateEntryIterator 抽象类，key 的**倒序**迭代器。代码如下： ``` // TreeMap.java final class DescendingKeyIterator extends PrivateEntryIterator<K> { DescendingKeyIterator(Entry<K,V> first) { super(first); } // 实现 next 方法，实现倒序 public K next() { return prevEntry().key; } // 重写 remove 方法，因为在 deleteEntry 方法中，在 lastReturned 左右节点都存在的时候，是将后继节点替换到 lastReturned 中。 // 而这个逻辑，对于倒序遍历，没有影响。 public void remove() { // 如果当前返回的节点不存在，则抛出 IllegalStateException 异常 if (lastReturned == null) throw new IllegalStateException(); // 如果发生了修改，抛出 ConcurrentModificationException 异常 if (modCount != expectedModCount) throw new ConcurrentModificationException(); // 删除节点 deleteEntry(lastReturned); // 置空 lastReturned lastReturned = null; // 记录新的修改次数 expectedModCount = modCount; } } ``` ### 14.4 EntryIterator EntryIterator ，继承 PrivateEntryIterator 抽象类，Entry 的**正序**迭代器。代码如下： ``` // TreeMap.java final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> { EntryIterator(Entry<K,V> first) { super(first); } // 实现 next 方法，实现正序 public Map.Entry<K,V> next() { return nextEntry(); } } ``` ### 14.5 ValueIterator ValueIterator ，继承 PrivateEntryIterator 抽象类，value 的**正序**迭代器。代码如下： ``` // TreeMap.java final class ValueIterator extends PrivateEntryIterator<V> { ValueIterator(Entry<K,V> first) { super(first); } // 实现 next 方法，实现正序 public V next() { return nextEntry().value; } } ``` ## 15. 转换成 Set/Collection > 艿艿：本小节，可以选择性看，或者不看。 ### 15.1 keySet `#keySet()` 方法，获得**正序**的 key Set 。代码如下： ``` // TreeMap.java /** * 正序的 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)); } ``` - 创建的 KeySet 类。它实现 NavigableSet 接口，继承了 [`java.util.AbstractSet`](https://github.com/YunaiV/openjdk/blob/master/src/java.base/share/classes/java/util/AbstractSet.java) 抽像类，是 TreeMap 的内部类。比较简单，就不哔哔了。 - KeySet 使用的迭代器，就是 [「14.2 KeyIterator」](http://svip.iocoder.cn/JDK/Collection-TreeMap/#) 。 ### 15.2 descendingKeySet `#descendingKeySet()` 方法，获得**倒序**的 key Set 。代码如下： ``` // TreeMap.java /** * 倒序的 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)); } ``` - 首先，调用 `#descendingMap()` 方法，返回**倒序**访问当前 TreeMap 的 DescendingSubMap 对象。 - 然后，调用 `#navigableKeySet()` 方法，返回 DescendingSubMap 对象的**正序**的 key Set 。 - 关于 DescendingSubMap 类，我们在 TODO 来详细解析。 ### 15.3 values `#values()` 方法，获得 value 集合。代码如下： ``` // TreeMap.java public Collection<V> values() { Collection<V> vs = values; if (vs == null) { vs = new Values(); values = vs; // values 缓存，来自 AbstractMap 的属性 } return vs; } ``` - 创建的 Values 类。它继承了 [`java.util.AbstractCollection`](https://github.com/YunaiV/openjdk/blob/master/src/java.base/share/classes/java/util/AbstractCollection.java) 抽像类，是 TreeMap 的内部类。比较简单，就不哔哔了。 - Values 使用的迭代器，就是 [「14.4 ValueIterator」](http://svip.iocoder.cn/JDK/Collection-TreeMap/#) 。 ### 15.4 entrySet `#entrySet()` 方法，获得 Entry 集合。代码如下： ``` // TreeMap.java /** * Entry 缓存集合 */ private transient EntrySet entrySet; public Set<Map.Entry<K,V>> entrySet() { EntrySet es = entrySet; return (es != null) ? es : (entrySet = new EntrySet()); } ``` - 创建的 EntrySet 类。它继承了 [`java.util.AbstractSet`](https://github.com/YunaiV/openjdk/blob/master/src/java.base/share/classes/java/util/AbstractSet.java) 抽像类，是 TreeMap 的内部类。比较简单，就不哔哔了。 - EntrySet 使用的迭代器，就是 [「14.3 EntryIterator」](http://svip.iocoder.cn/JDK/Collection-TreeMap/#) 。 ## 16. 查找范围的元素 在 SortedMap 接口中，定义了按照 key 查找范围，返回子 SortedMap 结果的方法： - `#subMap(K fromKey, K toKey)` - `#headMap(K toKey)` - `#tailMap(K fromKey)` 在 NavigableMap 中，定义了按照 key 查找范围，返回子 NavigableMap 结果的方法： - `#subMap(K fromKey, K toKey)` - `#subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)` - `#headMap(K toKey)` - `#headMap(K toKey, boolean inclusive)` - `#tailMap(K fromKey)` - `#tailMap(K fromKey, boolean inclusive)` TreeMap 对上述接口，实现如下方法： ``` // TreeMap.java // subMap 组 public SortedMap<K,V> subMap(K fromKey, K toKey) { return subMap(fromKey, true, toKey, false); } public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { return new AscendingSubMap<>(this, false, fromKey, fromInclusive, false, toKey, toInclusive); } // headMap 组 public SortedMap<K,V> headMap(K toKey) { return headMap(toKey, false); } public NavigableMap<K,V> headMap(K toKey, boolean inclusive) { return new AscendingSubMap<>(this, true, null, true, false, toKey, inclusive); } // tailMap 组 public SortedMap<K,V> tailMap(K fromKey) { return tailMap(fromKey, true); } public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) { return new AscendingSubMap<>(this, false, fromKey, inclusive, true, null, true); } ``` - 返回的都是 AscendingSubMap 对象。所以，我们在 [「XX. AscendingSubMap」](http://svip.iocoder.cn/JDK/Collection-TreeMap/#) 来看。 ### 16.1 NavigableSubMap NavigableSubMap ，实现 NavigableMap、Serializable 接口，继承 AbstractMap 抽象类，**子 NavigableMap 的抽象类**。 后续，我们会看到 NavigableSubMap 的两个子类： - AscendingSubMap ，**正序**的 子 NavigableMap 的实现类。 - DescendingSubMap ，**倒序**的 子 NavigableMap 的实现类。 #### 16.1.1 构造方法 NavigableSubMap 仅有一个构造方法，代码如下： ``` // TreeMap.java#NavigableSubMap.java /** * The backing map. */ final TreeMap<K,V> m; /** * lo - 开始位置 * hi - 结束位置 */ final K lo, hi; /** * fromStart - 是否从 TreeMap 开头开始。如果是的话，{@link #lo} 可以不传 * toEnd - 是否从 TreeMap 结尾结束。如果是的话，{@link #hi} 可以不传 */ final boolean fromStart, toEnd; /** * loInclusive - 是否包含 key 为 {@link #lo} 的元素 * hiInclusive - 是否包含 key 为 {@link #hi} 的元素 */ final boolean loInclusive, hiInclusive; NavigableSubMap(TreeMap<K,V> m, boolean fromStart, K lo, boolean loInclusive, boolean toEnd, K hi, boolean hiInclusive) { // 如果既不从开头开始，又不从结尾结束，那么就要校验 lo 小于 hi ，否则抛出 IllegalArgumentException 异常 if (!fromStart && !toEnd) { if (m.compare(lo, hi) > 0) throw new IllegalArgumentException("fromKey > toKey"); } else { // 如果不从开头开始，则进行 lo 的类型校验 if (!fromStart) // type check m.compare(lo, lo); // 如果不从结尾结束，则进行 hi 的类型校验 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; } ``` - 每个属性，胖友自己看代码上的注释。 #### 16.1.2 范围校验 因为 NavigableSubMap 是 TreeMap 的**子** NavigableMap ，所以其所有的操作，不能超过其**子范围**，既我们在创建 NavigableSubMap 时，锁设置的开始和结束的 key 位置。 `#inRange(Object key)` 方法，校验传入的 `key` 是否在子范围中。代码如下： ``` // TreeMap.java#NavigableSubMap.java final boolean inRange(Object key) { return !tooLow(key) && !tooHigh(key); } ``` - 调用 `#tooLow(Object key)` 方法，判断 `key` 是否小于 NavigableSubMap 的开始位置的 key 。代码如下： ``` // TreeMap.java#NavigableSubMap.java final boolean tooLow(Object key) { if (!fromStart) { // 比较 key int c = m.compare(key, lo); if (c < 0 // 如果小于，则肯定过小 || (c == 0 && !loInclusive)) // 如果相等，则进一步判断是否 !loInclusive ，不包含 lo 的情况 return true; } return false; } ``` - 调用 `#tooHigh(Object key)` 方法，判断 `key` 是否大于 NavigableSubMap 的结束位置的 key 。代码如下： ``` // TreeMap.java#NavigableSubMap.java final boolean tooHigh(Object key) { if (!toEnd) { // 比较 key int c = m.compare(key, hi); if (c > 0 // 如果大于，则肯定过大 || (c == 0 && !hiInclusive)) // 如果相等，则进一步判断是否 !hiInclusive ，不包含 high 的情况 return true; } return false; } ``` - 通过这样两个判断，不过大，且不过小，那么就在范围之内了。 `#inClosedRange(Object key)` 方法，判断是否在闭合的范围内。代码如下： ``` // TreeMap.java#NavigableSubMap.java final boolean inClosedRange(Object key) { return (fromStart || m.compare(key, lo) >= 0) && (toEnd || m.compare(hi, key) >= 0); } ``` - 也就是说，不包含包含边界的情况。 `#inRange(Object key, boolean inclusive)` 方法，根据传入的 `inclusive` 参数，调用上述的两种范围判断的方法。代码如下： ``` // TreeMap.java#NavigableSubMap.java final boolean inRange(Object key, boolean inclusive) { return inclusive ? inRange(key) : inClosedRange(key); } ``` #### 16.1.3 添加单个元素 `#put(K key, V value)` 方法，添加单个元素。代码如下： ``` // TreeMap.java#NavigableSubMap.java public final V put(K key, V value) { // 校验 key 的范围，如果不在，则抛出 IllegalArgumentException 异常 if (!inRange(key)) throw new IllegalArgumentException("key out of range"); // 执行添加单个元素 return m.put(key, value); } ``` #### 16.1.4 获得单个元素 `#get(Object key)` 方法，获得 `key` 对应的 value 值。代码如下： ``` // TreeMap.java#NavigableSubMap.java public final V get(Object key) { return !inRange(key) // 校验 key 的范围 ? null : // 如果不在，则返回 null m.get(key); // 执行获得单个元素 } ``` `#containsKey(Object key)` 方法，判断是否存在指定 key 。代码如下： ``` // TreeMap.java public final boolean containsKey(Object key) { return inRange(key) && m.containsKey(key); } ``` - 基于 `#getEntry(key)` 方法来实现。 #### 16.1.5 删除单个元素 `#remove(Object key)` 方法，移除 `key` 对应的 Entry 节点。代码如下： ``` // TreeMap.java#NavigableSubMap.java public final V remove(Object key) { return !inRange(key) // 校验 key 的范围 ? null : // 如果不在，则返回 null m.remove(key); // 执行移除单个元素 } ``` #### 16.1.6 查找接近的元素 ``` // TreeMap.java#NavigableSubMap.java public final Map.Entry<K,V> ceilingEntry(K key) { return exportEntry(subCeiling(key)); } public final K ceilingKey(K key) { return keyOrNull(subCeiling(key)); } public final Map.Entry<K,V> higherEntry(K key) { return exportEntry(subHigher(key)); } public final K higherKey(K key) { return keyOrNull(subHigher(key)); } public final Map.Entry<K,V> floorEntry(K key) { return exportEntry(subFloor(key)); } public final K floorKey(K key) { return keyOrNull(subFloor(key)); } public final Map.Entry<K,V> lowerEntry(K key) { return exportEntry(subLower(key)); } public final K lowerKey(K key) { return keyOrNull(subLower(key)); } ``` 因为子类的**排序规则不同**，所以 NavigableSubMap 定义了如下抽象方法，交给子类实现。代码如下： ``` // TreeMap.java#NavigableSubMap.java 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); ``` 当然，NavigableSubMap 为了子类实现更方便，提供了如下方法： ``` // TreeMap.java#NavigableSubMap.java final TreeMap.Entry<K,V> absLowest() { // 获得 NavigableSubMap 开始位置的 Entry 节点 TreeMap.Entry<K,V> e = (fromStart ? m.getFirstEntry() : // 如果从 TreeMap 开始，则获得 TreeMap 的首个 Entry 节点 (loInclusive ? m.getCeilingEntry(lo) : // 如果 key 从 lo 开始（包含），则获得 TreeMap 从 lo 开始（>=）最接近的 Entry 节点 m.getHigherEntry(lo))); // 如果 key 从 lo 开始（不包含），则获得 TreeMap 从 lo 开始(>)最接近的 Entry 节点 return (e == null || tooHigh(e.key)) /** 超过 key 过大 **/ ? null : e; } final TreeMap.Entry<K,V> absHighest() { // 获得 NavigableSubMap 结束位置的 Entry 节点 TreeMap.Entry<K,V> e = (toEnd ? m.getLastEntry() : // 如果从 TreeMap 开始，则获得 TreeMap 的尾部 Entry 节点 (hiInclusive ? m.getFloorEntry(hi) : // 如果 key 从 hi 开始（包含），则获得 TreeMap 从 hi 开始（<=）最接近的 Entry 节点 m.getLowerEntry(hi))); // 如果 key 从 lo 开始（不包含），则获得 TreeMap 从 lo 开始(<)最接近的 Entry 节点 return (e == null || tooLow(e.key)) /** 超过 key 过小 **/ ? null : e; } final TreeMap.Entry<K,V> absCeiling(K key) { // 获得 NavigableSubMap >= key 最接近的 Entry 节点 // 如果 key 过小，则只能通过 `#absLowest()` 方法，获得 NavigableSubMap 开始位置的 Entry 节点 if (tooLow(key)) return absLowest(); // 获得 NavigableSubMap >= key 最接近的 Entry 节点 TreeMap.Entry<K,V> e = m.getCeilingEntry(key); return (e == null || tooHigh(e.key)) /** 超过 key 过大 **/ ? null : e; } final TreeMap.Entry<K,V> absHigher(K key) { // 获得 NavigableSubMap > key 最接近的 Entry 节点 // 如果 key 过小，则只能通过 `#absLowest()` 方法，获得 NavigableSubMap 开始位置的 Entry 节点 if (tooLow(key)) return absLowest(); // 获得 NavigableSubMap > key 最接近的 Entry 节点 TreeMap.Entry<K,V> e = m.getHigherEntry(key); return (e == null || tooHigh(e.key)) /** 超过 key 过大 **/ ? null : e; } final TreeMap.Entry<K,V> absFloor(K key) { // 获得 NavigableSubMap <= key 最接近的 Entry 节点 // 如果 key 过大，则只能通过 `#absHighest()` 方法，获得 NavigableSubMap 结束位置的 Entry 节点 if (tooHigh(key)) return absHighest(); // 获得 NavigableSubMap <= key 最接近的 Entry 节点 TreeMap.Entry<K,V> e = m.getFloorEntry(key); return (e == null || tooLow(e.key)) /** 超过 key 过小 **/ ? null : e; } final TreeMap.Entry<K,V> absLower(K key) { // 获得 NavigableSubMap < key 最接近的 Entry 节点 // 如果 key 过大，则只能通过 `#absHighest()` 方法，获得 NavigableSubMap 结束位置的 Entry 节点 if (tooHigh(key)) return absHighest(); // 获得 NavigableSubMap < key 最接近的 Entry 节点 TreeMap.Entry<K,V> e = m.getLowerEntry(key); return (e == null || tooLow(e.key)) /** 超过 key 过小 **/ ? null : e; } /** Returns the absolute high fence for ascending traversal */ final TreeMap.Entry<K,V> absHighFence() { // 获得 TreeMap 最大 key 的 Entry 节点，用于升序遍历的时候。注意，是 TreeMap 。 // toEnd 为真时，意味着无限大，所以返回 null return (toEnd ? null : (hiInclusive ? m.getHigherEntry(hi) : // 获得 TreeMap > hi 最接近的 Entry 节点。 m.getCeilingEntry(hi))); // 获得 TreeMap => hi 最接近的 Entry 节点。 } /** Return the absolute low fence for descending traversal */ final TreeMap.Entry<K,V> absLowFence() { // 获得 TreeMap 最小 key 的 Entry 节点，用于降序遍历的时候。注意，是 TreeMap 。 return (fromStart ? null : (loInclusive ? m.getLowerEntry(lo) : // 获得 TreeMap < lo 最接近的 Entry 节点。 m.getFloorEntry(lo))); // 获得 TreeMap <= lo 最接近的 Entry 节点。 } ``` - 方法有点点小多，不过基本是雷同的。耐心如我~ #### 16.1.7 获得首尾的元素 `#firstEntry()` 方法，获得首个 Entry 节点。代码如下： ``` // TreeMap.java#NavigableSubMap.java public final Map.Entry<K,V> firstEntry() { return exportEntry(subLowest()); } public final K firstKey() { return key(subLowest()); } public final Map.Entry<K,V> pollFirstEntry() { // 获得 NavigableSubMap 的首个 Entry 节点 TreeMap.Entry<K,V> e = subLowest(); Map.Entry<K,V> result = exportEntry(e); // 如果存在，则进行删除。 if (e != null) m.deleteEntry(e); return result; } ``` `#lastEntry()` 方法，获得尾部 Entry 节点。代码如下： ``` // TreeMap.java#NavigableSubMap.java public final Map.Entry<K,V> lastEntry() { return exportEntry(subHighest()); } public final K lastKey() { return key(subHighest()); } public final Map.Entry<K,V> pollLastEntry() { // 获得 NavigableSubMap 的尾部 Entry 节点 TreeMap.Entry<K,V> e = subHighest(); Map.Entry<K,V> result = exportEntry(e); // 如果存在，则进行删除。 if (e != null) m.deleteEntry(e); return result; } ``` #### 16.1.8 清空 直接使用继承自 AbstractMap 的 `#clear()` 方法，仅清空自己范围内的数据。代码如下： ``` // AbstractMap.java public void clear() { entrySet().clear(); } ``` - 而 `#entrySet()` 方法，NavigableSubMap 的子类在实现时，会重写该方法。这样，能够保证仅清空自己范围内的数据。 #### 16.1.9 获得迭代器 SubMapIterator ，实现 Iterator 接口，提供了 NavigableSubMap 的通用实现 Iterator 的抽象类。代码如下： ``` // TreeMap.java#NavigableSubMap.java abstract class SubMapIterator<T> implements Iterator<T> { /** * 最后返回的节点 */ TreeMap.Entry<K,V> lastReturned; /** * 下一个节点 */ TreeMap.Entry<K,V> next; /** * 遍历的上限 key 。 * * 如果遍历到该 key ，说明已经超过范围了 */ final Object fenceKey; /** * 当前的修改次数 */ int expectedModCount; SubMapIterator(TreeMap.Entry<K,V> first, TreeMap.Entry<K,V> fence) { expectedModCount = m.modCount; lastReturned = null; next = first; fenceKey = fence == null ? UNBOUNDED /** 无界限 **/ : fence.key; } public final boolean hasNext() { // 是否还有下一个节点 return next != null && next.key != fenceKey; } final TreeMap.Entry<K,V> nextEntry() { // 获得下一个 Entry 节点 // 记录当前节点 TreeMap.Entry<K,V> e = next; // 如果没有下一个，抛出 NoSuchElementException 异常 if (e == null || e.key == fenceKey) throw new NoSuchElementException(); // 如果发生了修改，抛出 ConcurrentModificationException 异常 if (m.modCount != expectedModCount) throw new ConcurrentModificationException(); // 获得 e 的后继节点，赋值给 next next = successor(e); // 记录最后返回的节点 lastReturned = e; // 返回当前节点 return e; } final TreeMap.Entry<K,V> prevEntry() { // 获得前一个 Entry 节点 // 记录当前节点 TreeMap.Entry<K,V> e = next; // 如果没有下一个，抛出 NoSuchElementException 异常 if (e == null || e.key == fenceKey) throw new NoSuchElementException(); // 如果发生了修改，抛出 ConcurrentModificationException 异常 if (m.modCount != expectedModCount) throw new ConcurrentModificationException(); // 获得 e 的前继节点，赋值给 next next = predecessor(e); // 记录最后返回的节点 lastReturned = e; // 返回当前节点 return e; } final void removeAscending() { // 删除节点（顺序遍历的情况下） // 如果当前返回的节点不存在，则抛出 IllegalStateException 异常 if (lastReturned == null) throw new IllegalStateException(); // 如果发生了修改，抛出 ConcurrentModificationException 异常 if (m.modCount != expectedModCount) throw new ConcurrentModificationException(); // deleted entries are replaced by their successors // 在 lastReturned 左右节点都存在的时候，实际在 deleteEntry 方法中，是将后继节点替换到 lastReturned 中 // 因此，next 需要指向 lastReturned if (lastReturned.left != null && lastReturned.right != null) next = lastReturned; // 删除节点 m.deleteEntry(lastReturned); // 置空 lastReturned lastReturned = null; // 记录新的修改次数 expectedModCount = m.modCount; } final void removeDescending() { // 删除节点倒序遍历的情况下） // 如果当前返回的节点不存在，则抛出 IllegalStateException 异常 if (lastReturned == null) throw new IllegalStateException(); // 如果发生了修改，抛出 ConcurrentModificationException 异常 if (m.modCount != expectedModCount) throw new ConcurrentModificationException(); // 删除节点 m.deleteEntry(lastReturned); // 置空 lastReturned lastReturned = null; // 记录新的修改次数 expectedModCount = m.modCount; } } ``` - 整体代码比较简单，胖友自己看看艿艿写的注释噢。 #### 16.1.9.1 SubMapKeyIterator SubMapKeyIterator ，继承 SubMapIterator 抽象类，key 的**正序**迭代器。代码如下： ``` // TreeMap.java#NavigableSubMap.java final class SubMapKeyIterator extends SubMapIterator<K> implements Spliterator<K> { SubMapKeyIterator(TreeMap.Entry<K,V> first, TreeMap.Entry<K,V> fence) { super(first, fence); } // 实现 next 方法，实现正序 public K next() { return nextEntry().key; } // 实现 remove 方法，实现正序的移除方法 public void remove() { removeAscending(); } public Spliterator<K> trySplit() { return null; } public void forEachRemaining(Consumer<? super K> action) { while (hasNext()) action.accept(next()); } public boolean tryAdvance(Consumer<? super K> action) { if (hasNext()) { action.accept(next()); return true; } return false; } public long estimateSize() { return Long.MAX_VALUE; } public int characteristics() { return Spliterator.DISTINCT | Spliterator.ORDERED | Spliterator.SORTED; } public final Comparator<? super K> getComparator() { return NavigableSubMap.this.comparator(); } } ``` #### 16.1.9.2 DescendingSubMapKeyIterator DescendingSubMapKeyIterator ，继承 SubMapIterator 抽象类，key 的**倒序**迭代器。代码如下： ``` // TreeMap.java#NavigableSubMap.java final class DescendingSubMapKeyIterator extends SubMapIterator<K> implements Spliterator<K> { DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last, TreeMap.Entry<K,V> fence) { super(last, fence); } // 实现 next 方法，实现倒序 public K next() { return prevEntry().key; } // 实现 remove 方法，实现倒序的移除方法 public void remove() { removeDescending(); } public Spliterator<K> trySplit() { return null; } public void forEachRemaining(Consumer<? super K> action) { while (hasNext()) action.accept(next()); } public boolean tryAdvance(Consumer<? super K> action) { if (hasNext()) { action.accept(next()); return true; } return false; } public long estimateSize() { return Long.MAX_VALUE; } public int characteristics() { return Spliterator.DISTINCT | Spliterator.ORDERED; } } ``` #### 16.1.9.3 SubMapEntryIterator SubMapEntryIterator ，继承 SubMapIterator 抽象类，Entry 的**正序**迭代器。代码如下： ``` // TreeMap.java#NavigableSubMap.java final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> { SubMapEntryIterator(TreeMap.Entry<K,V> first, TreeMap.Entry<K,V> fence) { super(first, fence); } // 实现 next 方法，实现正序 public Map.Entry<K,V> next() { return nextEntry(); } // 实现 remove 方法，实现正序的移除方法 public void remove() { removeAscending(); } } ``` #### 16.1.9.4 DescendingSubMapEntryIterator DescendingSubMapEntryIterator ，继承 SubMapIterator 抽象类，Entry 的**倒序**迭代器。代码如下： ``` // TreeMap.java#NavigableSubMap.java final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> { DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last, TreeMap.Entry<K,V> fence) { super(last, fence); } // 实现 next 方法，实现倒序 public Map.Entry<K,V> next() { return prevEntry(); } // 实现 remove 方法，实现倒序的移除方法 public void remove() { removeDescending(); } } ``` #### 16.1.10 转换成 Set/Collection ##### 16.1.10.1 keySet `#keySet()` 方法，获得**正序**的 key Set 。代码如下： ``` // TreeMap.java#NavigableSubMap.java /** * 正序的 KeySet 缓存对象 */ transient KeySet<K> navigableKeySetView; public final Set<K> keySet() { return navigableKeySet(); } public final NavigableSet<K> navigableKeySet() { KeySet<K> nksv = navigableKeySetView; return (nksv != null) ? nksv : (navigableKeySetView = new TreeMap.KeySet<>(this)); } ``` - KeySet 使用的迭代器，就是 [「16.1.9.1 SubMapKeyIterator」](http://svip.iocoder.cn/JDK/Collection-TreeMap/#) 。 ##### 16.1.10.2 navigableKeySet `#navigableKeySet()` 方法，获得**倒序**的 key Set 。代码如下： ``` // TreeMap.java#NavigableSubMap.java /** * 倒序的 KeySet 缓存对象 */ transient NavigableMap<K,V> descendingMapView; public NavigableSet<K> descendingKeySet() { return descendingMap().navigableKeySet(); } ``` - 其中，`#descendingMap()` 方法，子类自己实现。 ##### 16.1.10.3 values 直接使用继承自 AbstractMap 的 `#values()` 方法，代码如下： ``` // AbstractMap.java transient Collection<V> values; public Collection<V> values() { Collection<V> vals = values; if (vals == null) { vals = new AbstractCollection<V>() { public Iterator<V> iterator() { return new Iterator<V>() { private Iterator<Entry<K,V>> i = entrySet().iterator(); public boolean hasNext() { return i.hasNext(); } public V next() { return i.next().getValue(); } public void remove() { i.remove(); } }; } public int size() { return AbstractMap.this.size(); } public boolean isEmpty() { return AbstractMap.this.isEmpty(); } public void clear() { AbstractMap.this.clear(); } public boolean contains(Object v) { return AbstractMap.this.containsValue(v); } }; values = vals; } return vals; } ``` - 也是基于 `#entrySet()` 方法，来实现。 ##### 16.1.10.4 entrySet NavigableSubMap 未提供 `#entrySet()` 方法的实现，不过提供了 EntrySetView 抽象类，它实现了 [`java.util.AbstractSet`](https://github.com/YunaiV/openjdk/blob/master/src/java.base/share/classes/java/util/AbstractSet.java) 抽像类，是 NavigableSubMap 的内部类。比较简单，就不哔哔了。 #### 16.1.11 查找范围的元素 ``` // TreeMap.java#NavigableSubMap.java public final SortedMap<K,V> subMap(K fromKey, K toKey) { return subMap(fromKey, true, toKey, false); } public final SortedMap<K,V> headMap(K toKey) { return headMap(toKey, false); } public final SortedMap<K,V> tailMap(K fromKey) { return tailMap(fromKey, true); } ``` - 每个方法内部调用的方法，都是子类来实现。 ### 16.2 AscendingSubMap AscendingSubMap ，继承 NavigableSubMap 抽象类，**正序**的 子 NavigableMap 的实现类。 #### 16.2.1 查找接近的元素 ``` // TreeMap.java#AscendingSubMap.java TreeMap.Entry<K,V> subLowest() { return absLowest(); } TreeMap.Entry<K,V> subHighest() { return absHighest(); } TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); } TreeMap.Entry<K,V> subHigher(K key) { return absHigher(key); } TreeMap.Entry<K,V> subFloor(K key) { return absFloor(key); } TreeMap.Entry<K,V> subLower(K key) { return absLower(key); } ``` #### 16.2.2 获得迭代器 ``` // TreeMap.java#AscendingSubMap.java Iterator<K> keyIterator() { return new SubMapKeyIterator(absLowest(), absHighFence()); } Iterator<K> descendingKeyIterator() { return new DescendingSubMapKeyIterator(absHighest(), absLowFence()); } ``` #### 16.2.3 转换成 Set/Collection ##### 16.2.3.1 descendingMap `#descendingMap()` 方法，获得**倒序** descendingMap。代码如下： ``` // TreeMap.java#AscendingSubMap.java public NavigableMap<K,V> descendingMap() { NavigableMap<K,V> mv = descendingMapView; return (mv != null) ? mv : (descendingMapView = new DescendingSubMap<>(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive)); } ``` - 该方法，会被 [「16.1.9.2 DescendingSubMapKeyIterator」](http://svip.iocoder.cn/JDK/Collection-TreeMap/#) 调用。 ##### 16.2.3.2 entrySet `#entrySet()` 方法，获得 Entry 集合。代码如下： ``` // TreeMap.java#AscendingSubMap.java public Set<Map.Entry<K,V>> entrySet() { EntrySetView es = entrySetView; return (es != null) ? es : (entrySetView = new AscendingEntrySetView()); } final class AscendingEntrySetView extends EntrySetView { public Iterator<Map.Entry<K,V>> iterator() { return new SubMapEntryIterator(absLowest(), absHighFence()); } } ``` - AscendingEntrySetView 使用的迭代器，就是 [「16.1.9.3 SubMapEntryIterator」](http://svip.iocoder.cn/JDK/Collection-TreeMap/#) 。 #### 16.2.4 查找范围的元素 ``` // TreeMap.java#AscendingSubMap.java public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { // 如果不在范围，抛出 IllegalArgumentException 异常 if (!inRange(fromKey, fromInclusive)) throw new IllegalArgumentException("fromKey out of range"); // 如果不在范围，抛出 IllegalArgumentException 异常 if (!inRange(toKey, toInclusive)) throw new IllegalArgumentException("toKey out of range"); // 创建 AscendingSubMap 对象 return new AscendingSubMap<>(m, false, fromKey, fromInclusive, false, toKey, toInclusive); } public NavigableMap<K,V> headMap(K toKey, boolean inclusive) { // 如果不在范围，抛出 IllegalArgumentException 异常 if (!inRange(toKey, inclusive)) throw new IllegalArgumentException("toKey out of range"); // 创建 AscendingSubMap 对象 return new AscendingSubMap<>(m, fromStart, lo, loInclusive, false, toKey, inclusive); } public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) { // 如果不在范围，抛出 IllegalArgumentException 异常 if (!inRange(fromKey, inclusive)) throw new IllegalArgumentException("fromKey out of range"); // 创建 AscendingSubMap 对象 return new AscendingSubMap<>(m, false, fromKey, inclusive, toEnd, hi, hiInclusive); } ``` #### 16.2.5 获得排序器 `#comparator()` 方法，代码如下： ``` // TreeMap.java#AscendingSubMap.java // 排序器，使用传入的 TreeMap public Comparator<? super K> comparator() { return m.comparator(); } ``` ### 16.3 DescendingSubMap DescendingSubMap ，继承 NavigableSubMap 抽象类，**倒序**的 子 NavigableMap 的实现类。 16.3.1 查找接近的元素 ``` // TreeMap.java#DescendingSubMap.java 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); } ``` - 恰好是反过来。 #### 16.3.2 获得迭代器 ``` // TreeMap.java#DescendingSubMap.java Iterator<K> keyIterator() { return new DescendingSubMapKeyIterator(absHighest(), absLowFence()); } Iterator<K> descendingKeyIterator() { return new SubMapKeyIterator(absLowest(), absHighFence()); } ``` - 恰好是反过来。 #### 16.3.3 转换成 Set/Collection ##### 16.3.3.1 descendingMap `#descendingMap()` 方法，获得**倒序** descendingMap。代码如下： > 负负得正，其实返回的是正序的。 ``` // TreeMap.java#DescendingSubMap.java public NavigableMap<K,V> descendingMap() { NavigableMap<K,V> mv = descendingMapView; return (mv != null) ? mv : (descendingMapView = new AscendingSubMap<>(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive)); } ``` - 该方法，会被 [「16.1.9.2 DescendingSubMapKeyIterator」](http://svip.iocoder.cn/JDK/Collection-TreeMap/#) 调用。 ##### 16.3.3.2 entrySet `#entrySet()` 方法，获得 Entry 集合。代码如下： ``` // TreeMap.java#DescendingSubMap.java public Set<Map.Entry<K,V>> entrySet() { EntrySetView es = entrySetView; return (es != null) ? es : (entrySetView = new DescendingEntrySetView()); } final class DescendingEntrySetView extends EntrySetView { public Iterator<Map.Entry<K,V>> iterator() { return new DescendingSubMapEntryIterator(absHighest(), absLowFence()); } } ``` - AscendingEntrySetView 使用的迭代器，就是 [「16.1.9.4 DescendingSubMapEntryIterator」](http://svip.iocoder.cn/JDK/Collection-TreeMap/#) 。 #### 16.3.4 查找范围的元素 ``` // TreeMap.java#DescendingSubMap.java public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { // 如果不在范围，抛出 IllegalArgumentException 异常 if (!inRange(fromKey, fromInclusive)) throw new IllegalArgumentException("fromKey out of range"); // 如果不在范围，抛出 IllegalArgumentException 异常 if (!inRange(toKey, toInclusive)) throw new IllegalArgumentException("toKey out of range"); // 创建 DescendingSubMap 对象 return new DescendingSubMap<>(m, false, toKey, toInclusive, false, fromKey, fromInclusive); } public NavigableMap<K,V> headMap(K toKey, boolean inclusive) { // 如果不在范围，抛出 IllegalArgumentException 异常 if (!inRange(toKey, inclusive)) throw new IllegalArgumentException("toKey out of range"); // 创建 DescendingSubMap 对象 return new DescendingSubMap<>(m, false, toKey, inclusive, toEnd, hi, hiInclusive); } public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) { // 如果不在范围，抛出 IllegalArgumentException 异常 if (!inRange(fromKey, inclusive)) throw new IllegalArgumentException("fromKey out of range"); // 创建 DescendingSubMap 对象 return new DescendingSubMap<>(m, fromStart, lo, loInclusive, false, fromKey, inclusive); } ``` #### 16.3.5 获得排序器 `#comparator()` 方法，代码如下： ``` // TreeMap.java#DescendingSubMap.java /** * 倒序排序器 */ private final Comparator<? super K> reverseComparator = Collections.reverseOrder(m.comparator); public Comparator<? super K> comparator() { return reverseComparator; } ``` # 彩蛋 抛开红黑树的自平衡的逻辑来说，TreeMap 的实现代码，实际是略简单于 HashMap 的。当然，因为 TreeMap 提供的方法较多，所以导致本文会比 HashMap 写的长一些。 下面，我们来对 TreeMap 做一个简单的小结： - TreeMap 按照 key 的**顺序**的 Map 实现类，底层采用**红黑树**来实现存储。 - TreeMap 因为采用树结构，所以无需初始考虑像 HashMap 考虑**容量**问题，也不存在扩容问题。 - TreeMap 的 **key** 不允许为空( `null` )，可能是因为红黑树是一颗二叉查找树，需要对 key 进行排序。 > 看了下 [《为什么 TreeMap 中不允许使用 null 键？》](https://codeday.me/bug/20190205/621458.html) 文章，也是这个观点。 - TreeMap 的查找、添加、删除 key-value 键值对的**平均**时间复杂度为 `O(logN)` 。原因是，TreeMap 采用红黑树，操作都需要经过二分查找，而二分查找的时间复杂度是 `O(logN)` 。 - 相比 HashMap 来说，TreeMap 不仅仅支持指定 key 的查找，也支持 key **范围**的查找。当然，这也得益于 TreeMap 数据结构能够提供的有序特性。