java TreeSet 和 TreeMap 源码解读

简介: java 集合篇章——TreeSet 和 TreeMap 源码解读。


目录

一、前言

二、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接口的一个实现类,其类图如下 :

image.png

               TreeSet中的元素不能为null,否则会报NullPointerException。                

               与HashSet实现类不同,TreeSet最大的特点是可以进行排序。TreeSet底层是二叉树,可以对对象元素进行排序,但是自定义类需要实现comparable接口,可以使用匿名内部类实现该接口,并在匿名内部类中重写compare方法。

       2.TreeSet的底层实现

               0° 准备工作

               为了通过Debug,结合源码来分析TreeSet的底层,up以TreeSet_Demo类为演示类,代码如下 : (main函数第一行设置断点)

packagecsdn.knowledge.api_tools.gather.set;
importjava.util.Comparator;
importjava.util.TreeSet;
/*** @author : Cyan_RA9* @version : 21.0*/publicclassTreeSet_Demo {
publicstaticvoidmain(String[] args) {
TreeSettreeSet=newTreeSet(newComparator() {
@Overridepublicintcompare(Objecto1, Objecto2) {
return ((String)o1).compareTo((String)o2);
            }
        });
treeSet.add("141");
treeSet.add("5");
treeSet.add("23");
treeSet.add("114514");
System.out.println("treeSet = "+treeSet);
    }
}

image.gif

               1° TreeSet构造器

               进入Debug界面,首先我们跳入TreeSet的带参构造,如下 :

image.png

               可以看到,TreeSet底层的确调用了TreeMap。我们先不急着跳入TreeMap的构造器,先来看看TreeSet带参构造的形参——一个Comparator(比较器)类型的变量,这个Comparator类型其实就是一个接口其源码如下 :

image.png

              2° 匿名内部类实现接口的多态

               而我们一开始传入的这个玩意儿——

newComparator() {
@Overridepublicintcompare(Objecto1, Objecto2) {
return ((String)o1).compareTo((String)o2);
            }
        }

image.gif

               其实就是一个实现了该接口的匿名内部类对象,并在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的带参构造看看,如下图所示 :

image.png

               可以看到,在TreeMap构造器中,又将匿名内部类对象comparator传递给了TreeMap的一个属性comparator

               并且,此时的comparator已经显示为了匿名内部类“TreeSet_Demo$1”的形式。

               接下里我们跳出构造器,逐层返回到演示了中。

               4° add方法

               像TreeSet集合中添加第一个元素"141",跳入add方法,如下所示 :

image.png

               可以看到,底层仍然走的是put方法;注意实参中的PRESENT, 这个PRESENT就和HashSet中PRESENT是一个作用了,仅仅是作为一个空对象,起到占位的作用,其源码如下 :

image.png

               5° put方法和put方法

               继续跳入put方法,如下所示 :

image.png

               经典的“包皮”结构, 继续跳入内层put方法,如下 :

image.png

               内层的put方法代码是非常多并且复杂的,里面涉及到许多数据结构的知识。还好,这是第一次添加元素,直接进入第一个if语句就return出去了😂。

               当然,很明显真正完成添加元素的操作是在addEntryToEmptyMap方法中进行的。我们进去稍微瞅一眼,如下图所示 :

image.png

               可以看到,TreeSet是把数据包装成了Entry类型来进行存放的,这里的root是TreeMap中的一个Entry类型的引用变量。如下 :

image.png

               并且,这里的Entry类型(TreeMap中的)其实和Hashtable中的Entry类型一样,都实现了Map接口中的Entry内部接口,如下图所示 :

image.png

              6° 继续添加元素

               继续添加元素,直接快进到内层put方法,如下 :

image.png

               这时候t显然不为空,不进入第一个if语句。重点是第二个if语句,如下:

image.png

               仔细观察,显然它是根据cmp(匿名内部类中重写的compare方法的返回值)的值来进行比较,从而决定添加元素的相应操作。而且,根据动态绑定机制,这时候如果我们跳入compare方法,一定会跳到之前的匿名内部类, 如下图所示 :

image.png

               好的,多的也不瞎扯了,讲太深也没几个人能看懂。接下里我们回到演示类,并执行完毕剩余语句,输出结果如下 :

image.png

               可以看到,的确是由ASCII码值从小到大进行排列(注意compareTo比较的方式)。  

               7° 修改比较器的比较原则

               除了compareTo方法,我们还可以修改compare方法return语句中的内容,如下所示  :

TreeSettreeSet=newTreeSet(newComparator() {
@Overridepublicintcompare(Objecto1, Objecto2) {
return ((String)o1).length() - ((String)o2).length();
            }
        });

image.gif

               如此一来, 判断的条件就改成了“两字符串的长度是否相同”,如果相同则无法添加。为进行对比,我们先在之前的判断条件(compareTo方法的判断)下修改add方法的实参,如下 :

image.png

              输出结果 :

image.png

               然后,我们再以新的判断条件运行,运行结果如下 :

image.png

               可以看到,与"5"长度相同的"3","2";与"141"长度相同的"233"都没法添加到集合中。

               这时候,我们查看Debug界面,可以看到"5"和"141"都已经挂载到了root下面,如下图所示 :

image.png

       3.TreeSet去重机制 :

                如果使用TreeSet的带参构造时传入了一个实现Comparable接口的匿名内部类对象,就使用已经重写的compare方法进行去重,如果该方法返回0,就认为是相同的元素或数据,不进行添加如果使用TreeSet的无参构造创建TreeSet类对象,则使用添加的元素类型中实现的Comparable接口的compareTo方法进行去重

               PS :如果既没有在创建TreeSet对象时传入实现Comparable接口的匿名内部类对象,也没有在所添加的元素的类中重写Comparable接口的compareTo方法,那么在添加元素时IDEA会报类型转换异常

               eg : 代码如下 :

importjava.util.TreeSet;
/*Test everything!*/publicclassNewCareer {
publicstaticvoidmain(String[] args) {
System.out.println("Let get in a new career!");
TreeSettreeSet=newTreeSet();
treeSet.add(newCat());
    }
}
classCat {
//none}

image.gif

               运行结果 :

image.png


三、TreeMap详解

       1.TreeMap简介

               TreeMap作为Map接口的一个实现类,也是保存和记录key-value的映射关系——键值对的,其类图如下 :

image.png

               TreeMap中,key不可以为null,否则会报NullPointerException但是value可以为null

               TreeMap也可以对元素进行自定义排序,实现方式与TreeSet一致

       2.TreeMap的底层实现

              0° 准备工作

               up仍是结合源码给大家分析一下,以TreeMap_Demo类为演示类代码如下 : (main函数第一行设置断点)

packagecsdn.knowledge.api_tools.gather.map;
importjava.util.Comparator;
importjava.util.TreeMap;
/*** @author : Cyan_RA9* @version : 21.0*/publicclassTreeMap_Demo {
publicstaticvoidmain(String[] args) {
TreeMaptreeMap=newTreeMap(newComparator() {
@Overridepublicintcompare(Objecto1, Objecto2) {
return ((String)o1).compareTo((String)o2);
            }
        });
treeMap.put("Alice", "girl");
treeMap.put("Bob", "boy");
treeMap.put("Cyan", "boy");
System.out.println("treeMap = "+treeMap);
    }
}

image.gif

               1° TreeMap构造器            

               同样地,先跳入 TreeMap的构造器看看,如下 :

image.png

               还是那老一套,将实现了Comparator接口的匿名内部类对象传递给TreeMap的comparator属性

               2° add方法。

               向集合添加第一个元素,跳入add方法,如下 :

image.png

               可以看到,此时的value值已经不是PRESENT了,而是传入的实参girl

               3° 外层put和内层put

               跳入外层put,如下 :

image.png

               继续,跳入内层put方法 :

image.png

               可以看到,和TreeSet基本就一套,没啥讲得😂。

image.png

               仍然是在addEntryToEmptyMap方法中完成了对第一个元素的添加。        

               4° 向集合添加第二个元素

               仍然是进入内层put方法中进行比较,如下图所示 :

image.png

               这时候,我们跳入compare方法,根据动态绑定机制,一定会跳到匿名内部类中,如下图所示 :

image.png

               OK,接下来还是会根据compare方法的返回值进行判断,执行对应的添加操作。这里就不再演示了,我们将三个元素全部添加进去,如下图所示 :

image.png

               可以看到,三个键值对全部成功挂载到了root下。

               5° 改变判断元素的条件

               同样地,可以通过修改compare方法return语句中的内容来改变添加元素时的判断条件,如下所示 :

TreeMaptreeMap=newTreeMap(newComparator() {
@Overridepublicintcompare(Objecto1, Objecto2) {
//return ((String)o1).compareTo((String)o2);return ((String)o1).length() - ((String)o2).length();
            }
        });

image.gif

               同时,我们将添加的第二个元素的key由"Bob" 改为"Peter",这时候,由于"Peter"与"Alice"的长度一样,所以第二个元素是无法成功加入集合的,如下图所示 : image.png

image.png


四、完结撒❀

       🆗,以上就是TreeSet和TreeMap的源码解读了,其实就是把TreeMap讲了两遍😂。当然,up尽量避重就轻,源码中涉及到数据结构的部分基本都没讲,关于红黑树,或者其他数据结构与算法的知识,up将来会单独出一个专栏,用Java语言来描述讲解,大家敬请期待。感谢阅读!

       System.out.println("END-----------------------------------------------------------------------------");

目录
相关文章
|
5天前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
18 2
|
26天前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
42 1
|
28天前
|
存储 安全 Java
Java Map新玩法:探索HashMap和TreeMap的高级特性,让你的代码更强大!
【10月更文挑战第17天】Java Map新玩法:探索HashMap和TreeMap的高级特性,让你的代码更强大!
57 2
|
10天前
|
人工智能 监控 数据可视化
Java智慧工地信息管理平台源码 智慧工地信息化解决方案SaaS源码 支持二次开发
智慧工地系统是依托物联网、互联网、AI、可视化建立的大数据管理平台,是一种全新的管理模式,能够实现劳务管理、安全施工、绿色施工的智能化和互联网化。围绕施工现场管理的人、机、料、法、环五大维度,以及施工过程管理的进度、质量、安全三大体系为基础应用,实现全面高效的工程管理需求,满足工地多角色、多视角的有效监管,实现工程建设管理的降本增效,为监管平台提供数据支撑。
26 3
|
15天前
|
运维 自然语言处理 供应链
Java云HIS医院管理系统源码 病案管理、医保业务、门诊、住院、电子病历编辑器
通过门诊的申请,或者直接住院登记,通过”护士工作站“分配患者,完成后,进入医生患者列表,医生对应开具”长期医嘱“和”临时医嘱“,并在电子病历中,记录病情。病人出院时,停止长期医嘱,开具出院医嘱。进入出院审核,审核医嘱与住院通过后,病人结清缴费,完成出院。
47 3
|
20天前
|
JavaScript Java 项目管理
Java毕设学习 基于SpringBoot + Vue 的医院管理系统 持续给大家寻找Java毕设学习项目(附源码)
基于SpringBoot + Vue的医院管理系统,涵盖医院、患者、挂号、药物、检查、病床、排班管理和数据分析等功能。开发工具为IDEA和HBuilder X,环境需配置jdk8、Node.js14、MySQL8。文末提供源码下载链接。
|
24天前
|
移动开发 前端开发 JavaScript
java家政系统成品源码的关键特点和技术应用
家政系统成品源码是已开发完成的家政服务管理软件,支持用户注册、登录、管理个人资料,家政人员信息管理,服务项目分类,订单与预约管理,支付集成,评价与反馈,地图定位等功能。适用于各种规模的家政服务公司,采用uniapp、SpringBoot、MySQL等技术栈,确保高效管理和优质用户体验。
|
26天前
|
存储 Java API
详细解析HashMap、TreeMap、LinkedHashMap等实现类,帮助您更好地理解和应用Java Map。
【10月更文挑战第19天】深入剖析Java Map:不仅是高效存储键值对的数据结构,更是展现设计艺术的典范。本文从基本概念、设计艺术和使用技巧三个方面,详细解析HashMap、TreeMap、LinkedHashMap等实现类,帮助您更好地理解和应用Java Map。
41 3
|
26天前
|
存储 缓存 安全
在Java的Map家族中,HashMap和TreeMap各具特色
【10月更文挑战第19天】在Java的Map家族中,HashMap和TreeMap各具特色。HashMap基于哈希表实现,提供O(1)时间复杂度的高效操作,适合性能要求高的场景;TreeMap基于红黑树,提供O(log n)时间复杂度的有序操作,适合需要排序和范围查询的场景。两者在不同需求下各有优势,选择时需根据具体应用场景权衡。
29 2
|
26天前
|
存储 安全 Java
Java Map新玩法:深入探讨HashMap和TreeMap的高级特性
【10月更文挑战第19天】Java Map新玩法:深入探讨HashMap和TreeMap的高级特性,包括初始容量与加载因子的优化、高效的遍历方法、线程安全性处理以及TreeMap的自然排序、自定义排序、范围查询等功能,助你提升代码性能与灵活性。
24 2