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

一、什么是TreeSet

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

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

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 来实现有序集合的功能。

二、TreeSet类的使用

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

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 类。

三、TreeSet类的应用场景

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

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

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

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

四、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 中按照降序排序元素。

五、总结

本文讲解了 Java 中集合类 TreeSet 的语法、使用说明和应用场景，并给出了样例代码。在下一篇博客中，将讲解 Java 中 HashMap 类的知识。