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

本文涉及的产品
云解析 DNS,旗舰版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
全局流量管理 GTM,标准版 1个月
简介: 【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 类的知识。



相关文章
|
2月前
|
存储 安全 Java
Java 集合框架中的老炮与新秀:HashTable 和 HashMap 谁更胜一筹?
嗨,大家好,我是技术伙伴小米。今天通过讲故事的方式,详细介绍 Java 中 HashMap 和 HashTable 的区别。从版本、线程安全、null 值支持、性能及迭代器行为等方面对比,帮助你轻松应对面试中的经典问题。HashMap 更高效灵活,适合单线程或需手动处理线程安全的场景;HashTable 较古老,线程安全但性能不佳。现代项目推荐使用 ConcurrentHashMap。关注我的公众号“软件求生”,获取更多技术干货!
51 3
|
2月前
|
存储 缓存 安全
Java 集合江湖:底层数据结构的大揭秘!
小米是一位热爱技术分享的程序员,本文详细解析了Java面试中常见的List、Set、Map的区别。不仅介绍了它们的基本特性和实现类,还深入探讨了各自的使用场景和面试技巧,帮助读者更好地理解和应对相关问题。
58 5
|
3月前
|
存储 缓存 安全
Java 集合框架优化:从基础到高级应用
《Java集合框架优化:从基础到高级应用》深入解析Java集合框架的核心原理与优化技巧,涵盖列表、集合、映射等常用数据结构,结合实际案例,指导开发者高效使用和优化Java集合。
72 4
|
3月前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
130 2
|
4月前
|
缓存 Java 程序员
Map - LinkedHashSet&Map源码解析
Map - LinkedHashSet&Map源码解析
99 1
|
4月前
|
算法 Java 容器
Map - HashSet & HashMap 源码解析
Map - HashSet & HashMap 源码解析
85 0
|
4月前
|
存储 Java C++
Collection-PriorityQueue源码解析
Collection-PriorityQueue源码解析
86 0
|
2月前
|
设计模式 存储 安全
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
创建型模式的主要关注点是“怎样创建对象?”,它的主要特点是"将对象的创建与使用分离”。这样可以降低系统的耦合度,使用者不需要关注对象的创建细节。创建型模式分为5种:单例模式、工厂方法模式抽象工厂式、原型模式、建造者模式。
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
|
2月前
|
存储 设计模式 算法
【23种设计模式·全精解析 | 行为型模式篇】11种行为型模式的结构概述、案例实现、优缺点、扩展对比、使用场景、源码解析
行为型模式用于描述程序在运行时复杂的流程控制,即描述多个类或对象之间怎样相互协作共同完成单个对象都无法单独完成的任务,它涉及算法与对象间职责的分配。行为型模式分为类行为模式和对象行为模式,前者采用继承机制来在类间分派行为,后者采用组合或聚合在对象间分配行为。由于组合关系或聚合关系比继承关系耦合度低,满足“合成复用原则”,所以对象行为模式比类行为模式具有更大的灵活性。 行为型模式分为: • 模板方法模式 • 策略模式 • 命令模式 • 职责链模式 • 状态模式 • 观察者模式 • 中介者模式 • 迭代器模式 • 访问者模式 • 备忘录模式 • 解释器模式
【23种设计模式·全精解析 | 行为型模式篇】11种行为型模式的结构概述、案例实现、优缺点、扩展对比、使用场景、源码解析
|
2月前
|
设计模式 存储 安全
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
结构型模式描述如何将类或对象按某种布局组成更大的结构。它分为类结构型模式和对象结构型模式,前者采用继承机制来组织接口和类,后者釆用组合或聚合来组合对象。由于组合关系或聚合关系比继承关系耦合度低,满足“合成复用原则”,所以对象结构型模式比类结构型模式具有更大的灵活性。 结构型模式分为以下 7 种: • 代理模式 • 适配器模式 • 装饰者模式 • 桥接模式 • 外观模式 • 组合模式 • 享元模式
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析

热门文章

最新文章