Java TreeSet:基于红黑树的排序集合解析

本文涉及的产品
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
简介: Java TreeSet:基于红黑树的排序集合解析

Java集合框架中,TreeSet是一个有序的、不允许元素重复的集合。它基于红黑树(Red-Black Tree)数据结构实现,这种数据结构能够确保元素在插入、删除后仍然保持有序状态。红黑树是一种自平衡的二叉查找树,它通过一系列的旋转和颜色调整来保证树的高度相对较低,从而保证了操作的效率。


一、TreeSet的特点


  1. 有序性TreeSet中的元素按照升序排列。默认情况下,元素按照自然顺序(即Comparable接口定义的顺序)进行排序,也可以通过构造函数提供一个自定义的Comparator来决定元素的排序方式。
  2. 不允许重复:如果试图向TreeSet中添加一个已经存在的元素(根据比较规则判断为相等),则这个操作不会有任何效果,集合保持不变。
  3. 非线程安全TreeSet是非线程安全的,如果多个线程同时修改一个TreeSet实例,并且至少有一个线程修改了该实例的结构,那么它必须保持外部同步。这通常是通过在某个自然封装了该集合的对象上进行同步来完成的。
  4. 性能:由于TreeSet基于红黑树实现,因此它的添加、删除、查找等操作的时间复杂度都接近O(log n)。这比基于哈希表的集合(如HashSet)要慢一些,但是TreeSet提供了有序的特性。


二、使用示例


下面是一个简单的TreeSet使用示例,展示了如何创建一个TreeSet、向其中添加元素以及遍历元素:

import java.util.TreeSet;
import java.util.Set;
public class TreeSetExample {
    public static void main(String[] args) {
        // 创建一个空的TreeSet实例,元素按照自然顺序排序
        Set<Integer> treeSet = new TreeSet<>();
        
        // 向TreeSet中添加元素
        treeSet.add(5);
        treeSet.add(2);
        treeSet.add(8);
        treeSet.add(1);
        treeSet.add(4);
        
        // 试图添加一个已存在的元素,不会有任何效果
        treeSet.add(5); // 重复元素不会被添加
        
        // 遍历TreeSet中的元素(有序)
        for (Integer number : treeSet) {
            System.out.println(number); // 输出顺序:1, 2, 4, 5, 8
        }
        
        // 创建一个自定义排序的TreeSet实例
        Set<String> customSortedSet = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
        customSortedSet.add("Apple");
        customSortedSet.add("banana");
        customSortedSet.add("Orange");
        customSortedSet.add("pear");
        customSortedSet.add("apple"); // 重复元素(不区分大小写)不会被添加
        
        // 遍历自定义排序的TreeSet中的元素(有序且不区分大小写)
        for (String fruit : customSortedSet) {
            System.out.println(fruit); // 输出顺序可能是:Apple, banana, Orange, pear(顺序可能因JVM实现而异)
        }
    }
}

在这个示例中,我们首先创建了一个空的TreeSet实例,并向其中添加了一些整数。由于TreeSet会自动对元素进行排序,因此遍历集合时输出的是有序的元素列表。然后,我们创建了一个自定义排序的TreeSet实例,使用了一个不区分大小写的比较器(String.CASE_INSENSITIVE_ORDER),并向其中添加了一些字符串。同样地,遍历集合时输出的是有序且不区分大小写的元素列表。需要注意的是,由于红黑树的特性,相同元素的添加操作会被忽略。


三、TreeSet的内部实现


TreeSet的内部实现基于红黑树,这是一种自平衡的二叉查找树。在二叉查找树中,每个节点都有一个键(以及相关联的值),任何节点的键都大于其左子树中的所有节点的键,而小于其右子树中的所有节点的键。然而,普通的二叉查找树在最坏的情况下可能会退化成链表(例如,当元素按升序或降序插入时),导致操作的时间复杂度增加到O(n)。

为了解决这个问题,红黑树引入了一些额外的属性来保持树的平衡:

  1. 每个节点要么是红色,要么是黑色。
  2. 根节点是黑色。
  3. 所有叶子节点(NIL或空节点)是黑色。
  4. 如果一个节点是红色的,则它的两个子节点都是黑色的(从每个叶子到根的所有路径上不能有两个连续的红色节点)。
  5. 对于每个节点,从该节点到其所有后代叶子节点的简单路径上,均包含相同数量的黑色节点(称为黑高度)。

这些属性确保了从根到叶子的最长可能路径不会超过最短可能路径的两倍长。由于操作最坏的情况就是找到位于树的最深层的节点,因此这种保证使得在红黑树上进行插入、删除和查找操作的时间复杂度为O(log n)。


四、自定义排序


除了使用元素的自然顺序外,TreeSet还允许通过构造函数提供一个Comparator来定义元素的排序方式。Comparator是一个接口,它定义了一个compare方法,该方法用于比较两个对象并确定它们的顺序。

下面是一个使用自定义Comparator的示例:

import java.util.Comparator;
import java.util.TreeSet;
import java.util.Set;
public class CustomSortedSetExample {
    public static void main(String[] args) {
        // 创建一个自定义排序的TreeSet实例,使用自定义的Comparator
        Set<String> customSortedSet = new TreeSet<>(new CustomComparator());
        
        // 向TreeSet中添加元素,它们将按照自定义Comparator定义的顺序排序
        customSortedSet.add("Apple");
        customSortedSet.add("banana");
        customSortedSet.add("Orange");
        customSortedSet.add("pear");
        
        // 遍历TreeSet中的元素(按照自定义的顺序)
        for (String fruit : customSortedSet) {
            System.out.println(fruit); // 输出顺序取决于CustomComparator的实现
        }
    }
    
    // 自定义Comparator实现类
    static class CustomComparator implements Comparator<String> {
        @Override
        public int compare(String s1, String s2) {
            // 这里可以根据需要定义比较逻辑,例如按照字符串长度排序
            return Integer.compare(s1.length(), s2.length());
        }
    }
}

在这个示例中,我们创建了一个自定义的Comparator实现类CustomComparator,它按照字符串的长度来比较元素。然后,我们使用这个比较器创建了一个TreeSet实例,并向其中添加了一些字符串。遍历集合时,元素将按照字符串长度的升序排列。

相关文章
|
5天前
|
安全 Java 测试技术
🎉Java零基础:全面解析枚举的强大功能
【10月更文挑战第19天】本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
96 60
|
5天前
|
Java 程序员 开发者
Java中的异常处理机制深度解析####
本文将深入浅出地探讨Java编程语言中异常处理的核心概念与实践策略,旨在帮助开发者更好地理解如何构建健壮的应用程序。通过剖析异常体系结构、掌握有效的异常捕获与处理技巧,以及学习最佳实践,读者能够提升代码质量,减少运行时错误,从而增强软件的稳定性和用户体验。 ####
|
4天前
|
存储 缓存 安全
🌟Java零基础:深入解析Java序列化机制
【10月更文挑战第20天】本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
14 3
|
3天前
|
算法 Java 数据库连接
Java连接池技术,从基础概念出发,解析了连接池的工作原理及其重要性
本文详细介绍了Java连接池技术,从基础概念出发,解析了连接池的工作原理及其重要性。连接池通过复用数据库连接,显著提升了应用的性能和稳定性。文章还展示了使用HikariCP连接池的示例代码,帮助读者更好地理解和应用这一技术。
12 1
|
7天前
|
监控 安全 Java
在 Java 中使用线程池监控以及动态调整线程池时需要注意什么?
【10月更文挑战第22天】在进行线程池的监控和动态调整时,要综合考虑多方面的因素,谨慎操作,以确保线程池能够高效、稳定地运行,满足业务的需求。
77 38
|
4天前
|
安全 Java
java 中 i++ 到底是否线程安全?
本文通过实例探讨了 `i++` 在多线程环境下的线程安全性问题。首先,使用 100 个线程分别执行 10000 次 `i++` 操作,发现最终结果小于预期的 1000000,证明 `i++` 是线程不安全的。接着,介绍了两种解决方法:使用 `synchronized` 关键字加锁和使用 `AtomicInteger` 类。其中,`AtomicInteger` 通过 `CAS` 操作实现了高效的线程安全。最后,通过分析字节码和源码,解释了 `i++` 为何线程不安全以及 `AtomicInteger` 如何保证线程安全。
java 中 i++ 到底是否线程安全?
|
8天前
|
Java 调度
[Java]线程生命周期与线程通信
本文详细探讨了线程生命周期与线程通信。文章首先分析了线程的五个基本状态及其转换过程,结合JDK1.8版本的特点进行了深入讲解。接着,通过多个实例介绍了线程通信的几种实现方式,包括使用`volatile`关键字、`Object`类的`wait()`和`notify()`方法、`CountDownLatch`、`ReentrantLock`结合`Condition`以及`LockSupport`等工具。全文旨在帮助读者理解线程管理的核心概念和技术细节。
23 1
[Java]线程生命周期与线程通信
|
6天前
|
安全 Java
在 Java 中使用实现 Runnable 接口的方式创建线程
【10月更文挑战第22天】通过以上内容的介绍,相信你已经对在 Java 中如何使用实现 Runnable 接口的方式创建线程有了更深入的了解。在实际应用中,需要根据具体的需求和场景,合理选择线程创建方式,并注意线程安全、同步、通信等相关问题,以确保程序的正确性和稳定性。
|
4天前
|
缓存 Java 调度
Java中的多线程编程:从基础到实践
【10月更文挑战第24天】 本文旨在为读者提供一个关于Java多线程编程的全面指南。我们将从多线程的基本概念开始,逐步深入到Java中实现多线程的方法,包括继承Thread类、实现Runnable接口以及使用Executor框架。此外,我们还将探讨多线程编程中的常见问题和最佳实践,帮助读者在实际项目中更好地应用多线程技术。
11 3

推荐镜像

更多