【JavaSE专栏52】Java集合类TreeSet解析，基于红黑树实现的有序非重集合

曾经终败给现在 2023-10-13 22:24 7阅读 0赞

> **作者主页**：[Designer 小郑][Designer]  
> **作者简介**：3年JAVA全栈开发经验，专注JAVA技术、系统定制、远程指导，致力于企业数字化转型，CSDN学院、蓝桥云课认证讲师。  
> **主打方向**：Vue、SpringBoot、微信小程序

本文讲解了 Java 中集合类 TreeSet 的语法、使用说明和应用场景，并给出了样例代码。

#### 目录 ####

*  一、什么是TreeSet
 *  二、TreeSet类的使用
 *  三、TreeSet类的应用场景
 *  四、TreeSet面试题
 *  五、总结

![在这里插入图片描述][7f5ed622bebb42ab9b0a90657401197f.png_pic_center]

## 一、什么是TreeSet ##

在 Java 中，TreeSet 是基于红黑树实现的有序集合，它实现了 SortedSet 接口。TreeSet 中的元素按照自然顺序（或者根据自定义的比较器）进行排序，并且不允许存储重复元素。

TreeSet 的特点有如下  6 6 6 点，请同学们认真学习。

1.  **有序性**：TreeSet 中的元素是有序的，默认按照元素的自然顺序进行排序。也可以在创建 TreeSet 时传入自定义的比较器来进行排序。
2.  **唯一性**：TreeSet 不允许存储重复元素。当尝试添加重复元素时，新元素不会被添加到集合中。
3.  **查询效率**：由于底层红黑树的特性，TreeSet 可以快速地进行插入、删除和查询操作。这使得TreeSet在需要有序集合且频繁进行查找操作的场景中非常适用。
4.  **不是线程安全的**：TreeSet 不是线程安全的，如果多个线程同时访问一个 TreeSet，并且至少有一个线程对其进行了修改，则必须通过外部同步手段来保证线程安全。
5.  **存储对象要实现 Comparable 接口或传入自定义比较器**：为了进行元素的排序和去重，TreeSet 中存储的元素要么实现 `Comparable` 接口来定义自然排序规则，要么在创建 TreeSet 时传入自定义的 Comparator 来定义排序规则。
6.  **迭代顺序**：TreeSet 的迭代顺序按照元素的排序顺序进行，这是由底层红黑树的结构决定的。

下面是一个示例代码，演示了 TreeSet 的基本用法。

import java.util.TreeSet;
    
    public class TreeSetExample {
        
        public static void main(String[] args) {
        
            TreeSet<Integer> set = new TreeSet<>();
            set.add(5);
            set.add(2);
            set.add(8);
            set.add(3);
            set.add(1);
    
            System.out.println(set); // 输出: [1, 2, 3, 5, 8]
            System.out.println(set.contains(3)); // 输出: true
            System.out.println(set.size()); // 输出: 5
    
            set.remove(2);
            System.out.println(set); // 输出: [1, 3, 5, 8]
    
            for (Integer element : set) {
        
                System.out.println(element);
            }
        }
    }

以上代码演示了 TreeSet 的基本用法，包括元素的添加、删除、查询和迭代遍历。

同学们可以根据自己的需求和实际情况，灵活地使用 TreeSet 来实现有序集合的功能。

![在这里插入图片描述][0fcfa9571ea54915bba275ad098e3a37.png_pic_center]

--------------------

## 二、TreeSet类的使用 ##

当使用 TreeSet 类时，同学们需要注意以下  2 2 2 点。

1.  在创建 TreeSet 对象时，可以选择传入一个实现了 `Comparator` 接口的比较器来定义元素的排序规则。如果没有传入比较器，则元素需要实现 `Comparable` 接口来定义自然排序规则。
2.  TreeSet 中的元素必须是可比较的，即要么实现了 `Comparable` 接口，要么在创建 TreeSet 对象时传入了比较器。

下面是一个具体的 Java 代码示例，展示了 TreeSet 类的使用方式，请同学们复制到本地执行。

import java.util.Comparator;
    import java.util.TreeSet;
    
    // 定义一个自定义的比较器，按照字符串长度进行排序
    class LengthComparator implements Comparator<String> {
        
        @Override
        public int compare(String s1, String s2) {
        
            return s1.length() - s2.length();
        }
    }
    
    public class TreeSetExample {
        
        public static void main(String[] args) {
        
            // 创建一个TreeSet对象，默认按照元素的自然顺序进行排序
            TreeSet<Integer> set1 = new TreeSet<>();
            set1.add(5);
            set1.add(2);
            set1.add(8);
            set1.add(3);
            set1.add(1);
            System.out.println(set1); // 输出: [1, 2, 3, 5, 8]
    
            // 创建一个TreeSet对象，传入自定义的比较器进行排序
            TreeSet<String> set2 = new TreeSet<>(new LengthComparator());
            set2.add("apple");
            set2.add("banana");
            set2.add("orange");
            set2.add("kiwi");
            System.out.println(set2); // 输出: [kiwi, apple, orange, banana]
        }
    }

以上代码演示了两种使用方式，分别是**默认按照元素的自然顺序排序**和**使用自定义比较器按照字符串长度排序**，同学们可以根据实际需求自由选择适合的方式来使用 TreeSet 类。

![在这里插入图片描述][cdaffc7f76a8480683e8373b05f25af3.png_pic_center]

--------------------

## 三、TreeSet类的应用场景 ##

TreeSet 类的应用场景如下  5 5 5 点，请同学们认真学习。

1.  **需要对元素进行排序**：TreeSet 能够按照元素的自然顺序或者自定义的比较器顺序对元素进行排序。因此，当需要对元素进行排序的时候，可以使用 TreeSet 来存储元素。
2.  **去重**：TreeSet 不允许存储重复的元素，因为它是基于红黑树实现的，保证了元素的唯一性。因此，当需要存储一组元素并去除其中的重复值时，可以使用 TreeSet。
3.  **快速的插入**、删除和查找操作：TreeSet 基于红黑树的数据结构，它通过保持树的平衡来保证较快的插入、删除和查找操作。因此，当需要频繁地进行这些操作，并且希望维持有序性时，可以选择使用 TreeSet。
4.  **需要迭代遍历有序元素**：TreeSet 内部的元素是有序的，因此可以通过迭代器按照顺序遍历元素。这在需要按照一定顺序处理元素的场景下非常有用。
5.  **实现范围查询**：TreeSet 提供了一些方法用于范围查询，比如 `headSet()`,`tailSet()`,`subSet()` 等。这些方法可以返回满足指定范围的子集合，非常方便地进行范围查询操作。

总的来说，TreeSet 适用于需要对元素进行排序、去重、快速插入删除查找操作以及范围查询的场景。

> 但是需要注意的是，由于底层使用红黑树实现，TreeSet 并不是线程安全的。如果需要在多线程环境中使用，需要通过外部同步手段来保证线程安全。

![在这里插入图片描述][afcb63925c72466f9228dddbc6058924.png_pic_center]

--------------------

## 四、TreeSet面试题 ##

> 一、TreeSet 是如何保持元素有序性的？

答：TreeSet 内部使用红黑树（自平衡二叉查找树）来存储元素。红黑树是一种自平衡的二叉树，通过调整节点的颜色和旋转操作来保持树的平衡。具体而言，红黑树通过比较元素的值进行插入、删除和查找操作，并按照元素的大小进行排序，从而保持元素的有序性。

> 二、TreeSet 如何去重？

答：TreeSet 内部使用红黑树来存储元素，并且红黑树的特性决定了它不允许存储重复的元素。当尝试向 TreeSet 中插入重复的元素时，新元素不会被添加到集合中。

> 三、TreeSet 和 HashSet 有什么区别？

答：TreeSet 和 HashSet 都是 Java 集合框架中的集合类，但它们有以下几点区别：

*  TreeSet 是有序集合，它可以按照元素的自然顺序或者自定义的比较器顺序进行排序，而 HashSet 是无序集合，元素的存储顺序是不确定的。
 *  TreeSet 不允许存储重复的元素，而 HashSet 可以存储重复元素，但是重复元素只会保留一个。
 *  TreeSet 是基于红黑树实现的，插入、删除和查找操作的时间复杂度是 `O(logn)`，而 HashSet 是基于哈希表实现的，这些操作的时间复杂度是 `O(1)`。
 *  TreeSet 的迭代顺序是有序的，而 HashSet 的迭代顺序是不确定的。

> 四、如何在 TreeSet 中使用自定义的比较器？

答：在创建 TreeSet 对象时，可以传入一个实现了 Comparator 接口的比较器来定义元素的排序规则。比较器可以根据元素的属性或者其他规则进行比较，并返回比较结果。然后 TreeSet 会根据比较器的结果来进行元素的排序和去重。示例代码如下：

import java.util.Comparator;
    import java.util.TreeSet;
    
    class MyComparator implements Comparator<Integer> {
        
        @Override
        public int compare(Integer o1, Integer o2) {
        
            // 自定义比较规则
            return o2 - o1;
        }
    }
    
    public class TreeSetExample {
        
        public static void main(String[] args) {
        
            TreeSet<Integer> set = new TreeSet<>(new MyComparator());
            set.add(5);
            set.add(2);
            set.add(8);
            set.add(3);
            set.add(1);
            System.out.println(set); // 输出: [8, 5, 3, 2, 1]
        }
    }

在上述代码中，通过传入自定义的比较器 MyComparator，在 TreeSet 中按照降序排序元素。

![在这里插入图片描述][bcc897a165b740dfa3deacd635cc704c.png_pic_center]

--------------------

## 五、总结 ##

本文讲解了 Java 中集合类 TreeSet 的语法、使用说明和应用场景，并给出了样例代码。在下一篇博客中，将讲解 Java 中 HashMap 类的知识。  
![在这里插入图片描述][3a01dc60e62c415b812015851343f1c0.png_pic_center]

[Designer]: https://blog.csdn.net/qq_41464123
[7f5ed622bebb42ab9b0a90657401197f.png_pic_center]: https://img-blog.csdnimg.cn/7f5ed622bebb42ab9b0a90657401197f.png#pic_center
[0fcfa9571ea54915bba275ad098e3a37.png_pic_center]: https://img-blog.csdnimg.cn/0fcfa9571ea54915bba275ad098e3a37.png#pic_center
[cdaffc7f76a8480683e8373b05f25af3.png_pic_center]: https://img-blog.csdnimg.cn/cdaffc7f76a8480683e8373b05f25af3.png#pic_center
[afcb63925c72466f9228dddbc6058924.png_pic_center]: https://img-blog.csdnimg.cn/afcb63925c72466f9228dddbc6058924.png#pic_center
[bcc897a165b740dfa3deacd635cc704c.png_pic_center]: https://img-blog.csdnimg.cn/bcc897a165b740dfa3deacd635cc704c.png#pic_center
[3a01dc60e62c415b812015851343f1c0.png_pic_center]: https://img-blog.csdnimg.cn/3a01dc60e62c415b812015851343f1c0.png#pic_center