java TreeSet 和 TreeMap 源码解读
目录
一、前言
大家好，本篇博文将通过Debug流程分析，带大家仔细剖析一下TreeSet以及TreeMap的底层实现。TreeSet的底层其实就是TreeMap，见名知意，与树有关，鉴于二者的底层都涉及到了较多数据结构的内容，目前在过渡阶段，up就“详略得当”（bushi），给大家把重点内容过一下就行，当然还是比一般地方讲得要细的。
注意 : ①解读源码需要扎实的基础，比较适合希望深究的同学； ②不要眼高手低，看会了不代表你会了，自己动手跟着过一遍才算有收获； ③点击文章的侧边栏目录或者前面的目录可以进行跳转。 良工不示人以朴，up所有文章都会适时进行补充完善。大家有问题都可以在评论区讨论交流，或者私信up。 感谢阅读！
二、TreeSet详解
1.TreeSet简介
①TreeSet是Set接口的一个实现类，其类图如下 :
②TreeSet中的元素不能为null，否则会报NullPointerException。
③与HashSet实现类不同，TreeSet最大的特点是可以进行排序。TreeSet底层是二叉树，可以对对象元素进行排序，但是自定义类需要实现comparable接口，可以使用匿名内部类实现该接口，并在匿名内部类中重写compare方法。
2.TreeSet的底层实现
0° 准备工作
为了通过Debug，结合源码来分析TreeSet的底层，up以TreeSet_Demo类为演示类，代码如下 : （main函数第一行设置断点）
package csdn.knowledge.api_tools.gather.set;
import java.util.Comparator;
import java.util.TreeSet;
/**
* @author : Cyan_RA9
* @version : 21.0
*/
public class TreeSet_Demo {
public static void main(String[] args) {
TreeSet treeSet = new TreeSet(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return ((String)o1).compareTo((String)o2);
}
});
treeSet.add("141");
treeSet.add("5");
treeSet.add("23");
treeSet.add("114514");
System.out.println("treeSet = " + treeSet);
}
}
1° TreeSet构造器
进入Debug界面，首先我们跳入TreeSet的带参构造，如下 :
可以看到，TreeSet底层的确调用了TreeMap。我们先不急着跳入TreeMap的构造器，先来看看TreeSet带参构造的形参——一个Comparator（比较器）类型的变量，这个Comparator类型其实就是一个接口，其源码如下 :
2° 匿名内部类实现接口的多态
而我们一开始传入的这个玩意儿——
new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return ((String)o1).compareTo((String)o2);
}
}
其实就是一个实现了该接口的匿名内部类对象，并在TreeSet带参构造中形成了多态。而在TreeSet带参构造中，又将匿名内部类对象comparator传递给了TreeMap的一个带参构造。
匿名内部类中实现了Comparator()接口中的compare方法，该方法决定了TreeSet集合中元素排序的原则。此时，排序的规则是由String类的compareTo方法决定的，我们来简单回顾一下String类的compareTo方法，如下——
int compareTo(String anotherString)——
返回两个字符串对象的比较结果——若相等，返回0；若不相等，从两个字符串的第一个字符开始比较，返回第一个不相等的字符的ASCII码差值。当较长字符串的前面部分恰巧是较短的字符串时，返回两个字符串的长度差。
因此，根据此规则，当前TreeSet集合中的元素应该是按字母表顺序来排列的，比方说我现在传入了两个字符串o1和o2，分别为"ABC"和"BBC"，那么此时compareTo方法的返回值就是A的ASCII码值 - B的ASCII码值 = 65 - 66 = -1，而-1是小于0的；那么在使用add方法添加元素时，compareTo方法的这个返回值就决定了添加元素时的排列顺序，关于这一点，在下面的add方法中可以体现。
3° TreeMap构造器
好的，我们接下来再追入TreeMap的带参构造看看，如下图所示 :
可以看到，在TreeMap构造器中，又将匿名内部类对象comparator传递给了TreeMap的一个属性comparator。
并且，此时的comparator已经显示为了匿名内部类“TreeSet_Demo$1”的形式。
接下里我们跳出构造器，逐层返回到演示了中。
4° add方法
像TreeSet集合中添加第一个元素"141"，跳入add方法，如下所示 :
可以看到，底层仍然走的是put方法；注意实参中的PRESENT， 这个PRESENT就和HashSet中PRESENT是一个作用了，仅仅是作为一个空对象，起到占位的作用，其源码如下 :
5° put方法和put方法
继续跳入put方法，如下所示 :
经典的“包皮”结构， 继续跳入内层put方法，如下 :
内层的put方法代码是非常多并且复杂的，里面涉及到许多数据结构的知识。还好，这是第一次添加元素，直接进入第一个if语句就return出去了😂。
当然，很明显真正完成添加元素的操作是在addEntryToEmptyMap方法中进行的。我们进去稍微瞅一眼，如下图所示 :
可以看到，TreeSet是把数据包装成了Entry类型来进行存放的，这里的root是TreeMap中的一个Entry类型的引用变量。如下 :
并且，这里的Entry类型（TreeMap中的）其实和Hashtable中的Entry类型一样，都实现了Map接口中的Entry内部接口，如下图所示 :
6° 继续添加元素
继续添加元素，直接快进到内层put方法，如下 :
这时候t显然不为空，不进入第一个if语句。重点是第二个if语句，如下:
仔细观察，显然它是根据cmp（匿名内部类中重写的compare方法的返回值）的值来进行比较，从而决定添加元素的相应操作。而且，根据动态绑定机制，这时候如果我们跳入compare方法，一定会跳到之前的匿名内部类, 如下图所示 :
好的，多的也不瞎扯了，讲太深也没几个人能看懂。接下里我们回到演示类，并执行完毕剩余语句，输出结果如下 :
可以看到，的确是由ASCII码值从小到大进行排列（注意compareTo比较的方式）。
7° 修改比较器的比较原则
除了compareTo方法，我们还可以修改compare方法return语句中的内容，如下所示 :
TreeSet treeSet = new TreeSet(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return ((String)o1).length() - ((String)o2).length();
}
});
如此一来， 判断的条件就改成了“两字符串的长度是否相同”，如果相同则无法添加。为进行对比，我们先在之前的判断条件（compareTo方法的判断）下修改add方法的实参，如下 :
输出结果 :
然后，我们再以新的判断条件运行，运行结果如下 :
可以看到，与"5"长度相同的"3"，"2"；与"141"长度相同的"233"都没法添加到集合中。
这时候，我们查看Debug界面，可以看到"5"和"141"都已经挂载到了root下面，如下图所示 :
3.TreeSet去重机制 :
如果使用TreeSet的带参构造时传入了一个实现Comparable接口的匿名内部类对象，就使用已经重写的compare方法进行去重，如果该方法返回0，就认为是相同的元素或数据，不进行添加；如果使用TreeSet的无参构造创建TreeSet类对象，则使用添加的元素类型中实现的Comparable接口的compareTo方法进行去重；
PS : 如果既没有在创建TreeSet对象时传入实现Comparable接口的匿名内部类对象，也没有在所添加的元素的类中重写Comparable接口的compareTo方法，那么在添加元素时IDEA会报类型转换异常。
eg : 代码如下 :
import java.util.TreeSet;
/*
Test everything!
*/
public class NewCareer {
public static void main(String[] args) {
System.out.println("Let get in a new career!");
TreeSet treeSet = new TreeSet();
treeSet.add(new Cat());
}
}
class Cat {
//none
}
运行结果 :
三、TreeMap详解
1.TreeMap简介
1° TreeMap作为Map接口的一个实现类，也是保存和记录key-value的映射关系——键值对的，其类图如下 :
2° TreeMap中，key不可以为null，否则会报NullPointerException；但是value可以为null。
3° TreeMap也可以对元素进行自定义排序，实现方式与TreeSet一致。
2.TreeMap的底层实现
0° 准备工作
up仍是结合源码给大家分析一下，以TreeMap_Demo类为演示类，代码如下 : （main函数第一行设置断点）
package csdn.knowledge.api_tools.gather.map;
import java.util.Comparator;
import java.util.TreeMap;
/**
* @author : Cyan_RA9
* @version : 21.0
*/
public class TreeMap_Demo {
public static void main(String[] args) {
TreeMap treeMap = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return ((String)o1).compareTo((String)o2);
}
});
treeMap.put("Alice", "girl");
treeMap.put("Bob", "boy");
treeMap.put("Cyan", "boy");
System.out.println("treeMap = " + treeMap);
}
}
1° TreeMap构造器
同样地，先跳入 TreeMap的构造器看看，如下 :
还是那老一套，将实现了Comparator接口的匿名内部类对象传递给TreeMap的comparator属性。
2° add方法。
向集合添加第一个元素，跳入add方法，如下 :
可以看到，此时的value值已经不是PRESENT了，而是传入的实参girl。
3° 外层put和内层put
跳入外层put，如下 :
继续，跳入内层put方法 :
可以看到，和TreeSet基本就一套，没啥讲得😂。
仍然是在addEntryToEmptyMap方法中完成了对第一个元素的添加。
4° 向集合添加第二个元素
仍然是进入内层put方法中进行比较，如下图所示 :
这时候，我们跳入compare方法，根据动态绑定机制，一定会跳到匿名内部类中，如下图所示 :
OK，接下来还是会根据compare方法的返回值进行判断，执行对应的添加操作。这里就不再演示了，我们将三个元素全部添加进去，如下图所示 :
可以看到，三个键值对全部成功挂载到了root下。
5° 改变判断元素的条件
同样地，可以通过修改compare方法return语句中的内容来改变添加元素时的判断条件，如下所示 :
TreeMap treeMap = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
//return ((String)o1).compareTo((String)o2);
return ((String)o1).length() - ((String)o2).length();
}
});
同时，我们将添加的第二个元素的key由"Bob" 改为"Peter"，这时候，由于"Peter"与"Alice"的长度一样，所以第二个元素是无法成功加入集合的，如下图所示 : 
四、完结撒❀
🆗，以上就是TreeSet和TreeMap的源码解读了，其实就是把TreeMap讲了两遍😂。当然，up尽量避重就轻，源码中涉及到数据结构的部分基本都没讲，关于红黑树，或者其他数据结构与算法的知识，up将来会单独出一个专栏，用Java语言来描述讲解，大家敬请期待。感谢阅读！
System.out.println("END-----------------------------------------------------------------------------");
- 点赞
- 收藏
- 关注作者
评论（0）