Java高级集合之TreeSet：什么是它，为什么使用它？

2024-01-25 12:13:36 浏览数 (1)

  咦咦咦，各位小可爱，我是你们的好伙伴——bug菌，今天又来给大家普及Java SE相关知识点了，别躲起来啊，听我讲干货还不快点赞，赞多了我就有动力讲得更嗨啦！所以呀，养成先点赞后阅读的好习惯，别被干货淹没了哦~

代码语言：js复制
环境说明：Windows 10   IntelliJ IDEA 2021.3.2   Jdk 1.8

前言

  在Java编程中，集合是一个非常重要的概念。Java中的集合框架就是在Java 2中引入的。集合框架提供了一组标准接口，可以在处理一组对象时使用。Java提供了许多不同的集合类，每个类都有不同的性能和用途。在这篇文章中，我们将介绍Java中的一个高级集合——TreeSet。

摘要

  TreeSet是Java集合框架中的一个类，属于有序的、可排序的集合类。它实现了Set接口，底层是基于红黑树的数据结构实现的。TreeSet可以确保元素的排序顺序，对于需要排序的场景，十分实用。

TreeSet

概述

TreeSet的特点

  • TreeSet是一个有序的集合类，实现了SortedSet接口。
  • TreeSet中的元素会按照插入顺序进行排序，或者根据指定的Comparator进行排序。
  • TreeSet允许null元素，但在判断元素是否相等时需要依靠Comparator来处理。

TreeSet的底层实现

  在Java中，TreeSet的底层数据结构是基于红黑树的数据结构实现的。红黑树是一种近似于平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会大于二倍。

  在红黑树中，每个节点都被标记为红色或黑色。树的根节点是黑色的。如果一个节点是红色的，则它的子节点必须是黑色的（反之不一定成立）。从根节点出发到任意一个空节点的路径上，所经过的黑色节点数量必须相同。

TreeSet的构造函数

  TreeSet提供了多种构造函数，其中最常用的是无参构造函数和带有Comparator参数的构造函数。

无参构造函数的定义如下：

代码语言：java复制
public TreeSet()

带有Comparator参数的构造函数的定义如下：

代码语言：java复制
    public TreeSet(Comparator<? super E> comparator)

  建议在使用TreeSet时，使用带有Comparator参数的构造函数，可以确保在元素比较时使用指定的比较器。

  如下是部分源码截图：

源代码解析

TreeSet的基本操作

向TreeSet中添加元素的代码如下：

代码语言：java复制
TreeSet<String> set = new TreeSet<>();
set.add("Java");
set.add("Python");
set.add("C  ");

  这段代码会在TreeSet中添加三个元素：Java、Python和C 。由于TreeSet是有序的，因此这些元素将会按照字典序进行排序。

从TreeSet中删除元素的代码如下：

代码语言：java复制
set.remove("Python");

  这段代码将会从TreeSet中删除Python元素。

判断TreeSet中是否存在指定元素的代码如下：

代码语言：java复制
boolean isExist = set.contains("Java");

  这段代码将会判断TreeSet中是否存在Java元素，如果存在，返回true，否则返回false。

获取TreeSet中第一个元素的代码如下：

代码语言：java复制
String first = set.first();

这段代码将会获取TreeSet中的第一个元素。

获取TreeSet中最后一个元素的代码如下：

代码语言：java复制
String last = set.last();

这段代码将会获取TreeSet中的最后一个元素。

  如下是部分源码截图：

TreeSet中的红黑树

  TreeSet底层维护了一个红黑树。在红黑树的插入、删除和查找操作中，时间复杂度都是O(log n)的。

  由于红黑树是一个有序的二叉树，因此TreeSet中的元素也是有序的。在调用TreeSet的add方法时，会调用红黑树的插入方法，在插入过程中，会根据元素的大小，将其插入到正确的位置上。

使用Comparator进行排序

  在上面的代码示例中，我们使用了无参构造函数创建了一个TreeSet对象。这种情况下，TreeSet会使用元素对象的compareTo方法进行比较。如果我们希望使用另一种比较方式，可以使用Comparator进行排序。

  Comparator是一个函数式接口，可以通过Lambda表达式创建。例如，我们想要按照字符串长度进行排序，可以这样写：

代码语言：java复制
TreeSet<String> set = new TreeSet<>((a, b) -> a.length() - b.length());
set.add("Java");
set.add("Python");
set.add("C  ");

  这段代码将会按照字符串长度进行排序，因此TreeSet中的元素顺序为：C 、Java、Python。

应用场景案例

TreeSet的场景

  当我们需要维护一个有序的集合，并且希望能够高效地进行插入、删除和查找操作时，可以使用TreeSet。TreeSet在实现Set接口的同时，还实现了SortedSet接口，因此可以保证元素的有序性。

TreeSet的优点

  • TreeSet是有序的，可以确保元素的排序顺序。
  • TreeSet底层使用红黑树实现，插入、删除和查找操作的时间复杂度都是O(log n)的。
  • TreeSet允许null元素。

TreeSet的缺点

  • 在判断元素相等时，需要使用Comparator进行处理。
  • TreeSet的底层是一个红黑树，因此对于插入、删除和查找等操作，需要使用树的相关知识进行理解和处理。

类代码方法介绍

下面是TreeSet类中部分重要的方法介绍。

构造函数

代码语言：java复制
public TreeSet()

无参构造函数，创建一个空的TreeSet对象。

代码语言：java复制
public TreeSet(Comparator<? extends E> comparator)

带有Comparator参数的构造函数，创建一个空的TreeSet对象，并使用指定的Comparator进行排序。

添加元素

代码语言：java复制
public boolean add(E e)

向TreeSet中添加元素。

删除元素

代码语言：java复制
public boolean remove(Object o)

从TreeSet中删除指定元素。

查找元素

代码语言：java复制
public boolean contains(Object o)

判断TreeSet中是否包含指定元素。

代码语言：java复制
public E first()

获取TreeSet中的第一个元素。

代码语言：java复制
public E last()

获取TreeSet中的最后一个元素。

测试用例

下面是一个简单的测试用例，用于测试TreeSet的基本功能。

代码语言：java复制
package com.demo.javase.day63;

import java.util.TreeSet;

/**
 * @Author bug菌
 * @Date 2023-11-06 11:01
 */
public class TreeSetTest {

    public static void main(String[] args) {
        TreeSet<String> set = new TreeSet<>();
        set.add("Java");
        set.add("Python");
        set.add("C  ");

        System.out.println(set.contains("Java")); // true
        System.out.println(set.contains("Ruby")); // false

        System.out.println(set.first()); // C  
        System.out.println(set.last()); // Python

        set.remove("Python");
        System.out.println(set.contains("Python")); // false
    }
}

测试结果

  根据如上测试用例，本地测试结果如下，仅供参考，你们也可以自行修改测试用例或者添加更多的测试数据或测试方法，进行熟练学习以此加深理解。

测试代码分析

  根据如上测试用例，在此我给大家进行深入详细的解读一下测试代码，以便于更多的同学能够理解并加深印象。

  该代码是一个 Java 程序，主要演示了使用 TreeSet 类来创建一个可排序的集合，并对集合进行添加、查询、删除等操作。具体分析如下：

  1. 导入 java.util.TreeSet 类。
  2. 在 main 方法中，创建一个 TreeSet 实例对象，并添加三个字符串类型的元素："Java"、"Python"、"C "。
  3. 使用 contains 方法查询该集合是否包含某个元素，输出查询结果。例如，查询集合是否包含字符串 "Java" 和 "Ruby"，输出结果分别为 true 和 false。
  4. 使用 first 和 last 方法，分别输出集合中的第一个元素和最后一个元素。例如，输出结果分别为："C " 和 "Python"。
  5. 使用 remove 方法，删除集合中的某个元素，并使用 contains 方法查询该元素是否还在集合中。例如，删除元素 "Python" 后，再次查询该元素是否在集合中，输出结果为 false。

全文小结

  在本文中，我们介绍了Java高级集合之TreeSet。我们先对TreeSet的特点、底层实现方式进行了介绍，然后介绍了TreeSet的基本操作和使用Comparator进行排序的方法。接着，我们介绍了TreeSet的应用场景及其优缺点，并对TreeSet类的部分重要方法进行了介绍。最后，我们还编写了一个简单的测试用例，对TreeSet进行了测试。

总结

  本文介绍了Java高级集合之TreeSet，它是一种有序的、可排序的集合类。TreeSet底层使用红黑树数据结构实现，能够快速进行插入、删除和查找操作，且能保证元素的有序性。我们可以使用无参构造函数或带有Comparator参数的构造函数创建TreeSet对象，并使用相关方法进行添加、删除和查找操作。此外，本文还简述了TreeSet的应用场景、优缺点和重要方法，并提供了一个简单的测试用例进行演示。

  ...

  好啦，这期的内容就基本接近尾声啦，若你想学习更多，可以参考这篇专栏总结《「滚雪球学Java」教程导航帖》，本专栏致力打造最硬核 Java 零基础系列学习内容，

java8 2024腾讯·技术创作特训营第五期

0 人点赞