目录
一、前言
二、TreeSet详解
1.TreeSet简介
2.TreeSet的底层实现
0° 准备工作
1° TreeSet构造器
2° 匿名内部类实现接口的多态
3° TreeMap构造器
4° add方法
5° put方法和put方法
6° 继续添加元素
7° 修改比较器的比较原则
3.TreeSet去重机制 :
三、TreeMap详解
1.TreeMap简介
2.TreeMap的底层实现
0° 准备工作
1° TreeMap构造器
2° add方法。
3° 外层put和内层put
4° 向集合添加第二个元素
5° 改变判断元素的条件
四、完结撒❀
一、前言
大家好,本篇博文将通过Debug流程分析,带大家仔细剖析一下TreeSet以及TreeMap的底层实现。TreeSet的底层其实就是TreeMap,见名知意,与树有关,鉴于二者的底层都涉及到了较多数据结构的内容,目前在过渡阶段,up就“详略得当”(bushi),给大家把重点内容过一下就行,当然还是比一般地方讲得要细的。
注意 : ①解读源码需要扎实的基础,比较适合希望深究的同学; ②不要眼高手低,看会了不代表你会了,自己动手跟着过一遍才算有收获; ③点击文章的侧边栏目录或者前面的目录可以进行跳转。 良工不示人以朴,up所有文章都会适时进行补充完善。大家有问题都可以在评论区讨论交流,或者私信up。 感谢阅读!
二、TreeSet详解
1.TreeSet简介
①TreeSet是Set接口的一个实现类,其类图如下 :
②TreeSet中的元素不能为null,否则会报NullPointerException。
③与HashSet实现类不同,TreeSet最大的特点是可以进行排序。TreeSet底层是二叉树,可以对对象元素进行排序,但是自定义类需要实现comparator接口,可以使用匿名内部类实现该接口,并在匿名内部类中重写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出去了
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)