---
title: "03-TreeSet"
created: 2025-12-02
tags:
  - Java
---
# TreeSet

> [!note] 定位说明
> Set 系列第 3 篇。红黑树实现：自动排序 + 范围查询。关键差异：**去重依据是 compareTo()/compare() 返回 0，而不是 equals()**——存自定义对象前先想清楚比较逻辑。数据结构基础见 04-Map系列/07-红黑树。

**TreeSet** 是 Java 集合框架中 `NavigableSet` 接口的实现类，基于 **红黑树（Red-Black Tree）** 数据结构实现，支持元素**自然排序**或**定制排序**，并提供高效的范围查询能力。

### **一、核心原理与数据结构**

#### **1. 底层实现**

- **红黑树**：TreeSet 基于 `TreeMap` 实现，元素作为键（Key）存储，值（Value）统一为静态占位符 `PRESENT`。红黑树是一种自平衡二叉搜索树，通过节点颜色标记和旋转操作保证树的高度平衡，确保插入、删除、查询操作的时间复杂度均为 **O(log n)**。
- **排序规则**：
  - **自然排序**：元素需实现 `Comparable` 接口（如 `Integer`、`String`）。
  - **定制排序**：通过构造函数传入 `Comparator` 实现自定义排序逻辑。

[[04-TreeSet源码分析|TreeSet源码分析]]

#### **2. 排序与比较逻辑**

- **元素比较**：

```java
  // 自然排序示例（元素需实现 Comparable）
  TreeSet<Integer> set = new TreeSet<>(); // 按整数自然顺序排序
  set.add(3);
  set.add(1);
  set.add(2);
  System.out.println(set); // 输出 [1, 2, 3]

  // 定制排序示例（通过 Comparator 逆序）
  TreeSet<Integer> reversedSet = new TreeSet<>(Comparator.reverseOrder());
  reversedSet.add(3);
  reversedSet.add(1);
  reversedSet.add(2);
  System.out.println(reversedSet); // 输出 [3, 2, 1]
  ```
- **注意事项**：
  - 元素必须实现 `Comparable` 接口或通过 `Comparator` 指定比较规则，否则抛出 `ClassCastException`。
  - `equals()` **与** `compareTo()` **的一致性**：若元素的 `compareTo()` 方法与 `equals()` 逻辑不一致，可能导致TreeSet 中出现 “逻辑重复” 的元素（`compareTo()` 返回 0 但 `equals()` 返回 `false`）。

### **二、关键特性**

#### **1. 有序性与范围查询**

- **有序遍历**：元素按排序规则升序排列，遍历时按此顺序返回。
- **范围操作**：

```java
  TreeSet<Integer> set = new TreeSet<>(Arrays.asList(1, 3, 5, 7, 9));

  // 范围查询
  SortedSet<Integer> subset = set.subSet(3, 7); // 返回 [3, 5]（左闭右开）
  NavigableSet<Integer> headSet = set.headSet(5, true); // 返回 ≤5 的元素：[1, 3, 5]

  // 边界查询
  Integer lower = set.lower(5); // 返回小于 5 的最大元素：3
  Integer higher = set.higher(5); // 返回大于 5 的最小元素：7
  Integer floor = set.floor(6); // 返回 ≤6 的最大元素：5
  Integer ceiling = set.ceiling(6); // 返回 ≥6 的最小元素：7
  ```

#### **2. 性能表现**

- **时间复杂度**：插入、删除、查询操作均为 **O(log n)**，优于链表（O (n)），但略低于哈希表（O
  (1)）。
- **空间开销**：每个节点需额外存储父节点、左右子节点及颜色标记，内存占用高于 `HashSet` 和 `LinkedHashSet`。

#### **3. 线程安全性**

- **非线程安全**：多线程环境下需手动同步（如使用 `Collections.synchronizedSortedSet()` 包装）。

### **三、适用场景**

#### **1. 需要排序的去重场景**

- **典型场景**：数值统计（如排行榜）、时间戳去重（按时间顺序）。

```java
  TreeSet<Integer> scores = new TreeSet<>();
  scores.addAll(Arrays.asList(85, 92, 78, 92, 88));
  System.out.println(scores); // 输出 [78, 85, 88, 92]（自动去重并排序）
  ```

#### **2. 范围查询与边界查找**

- **范围统计**：如查询年龄在 20~30 岁之间的用户。

```java
  TreeSet<Integer> ages = new TreeSet<>(Arrays.asList(22, 18, 25, 30, 35));
  Set<Integer> youngUsers = ages.subSet(20, 31); // 返回 [22, 25, 30]
  ```

#### **3. 自然排序与定制排序**

- **定制排序规则**：

```java
  // 按字符串长度排序
  TreeSet<String> words = new TreeSet<>(Comparator.comparingInt(String::length));
  words.addAll(Arrays.asList("apple", "banana", "grape", "kiwi"));
  System.out.println(words); // 输出 [kiwi, apple, grape, banana]
  ```

### **四、与其他 Set 实现类对比**

| **维度** | **HashSet** | **LinkedHashSet** | **TreeSet** |
| --- | --- | --- | --- |
| **数据结构** | 哈希表（HashMap） | 哈希表 + 双向链表（LinkedHashMap） | 红黑树（TreeMap） |
| **元素顺序** | 无序（不可预测） | 按插入顺序有序 | 按自然 / 定制顺序排序 |
| **null 支持** | 允许 1 个 null | 允许 1 个 null | 不允许 null（插入抛 NPE） |
| **时间复杂度** | O (1)（插入 / 查询） | O (1)（插入 / 查询） | O (log n)（插入 / 查询） |
| **空间开销** | 低（仅哈希表） | 中（哈希表 + 链表指针） | 高（树节点指针 + 颜色标记） |
| **适用场景** | 快速去重、无需顺序 | 需保留插入顺序的去重 | 需排序或范围查询的场景 |

### **五、注意事项与最佳实践**

1. **元素必须可比较**

   - 自定义类需实现 `Comparable` 接口或通过 `Comparator` 指定比较规则。

```java
   class User implements Comparable<User> {
       private int age;
       @Override
       public int compareTo(User other) {
           return Integer.compare(this.age, other.age); // 按年龄排序
       }
   }
   ```
2. **避免使用 null**

   - TreeSet 不支持 null 元素，插入 null 会抛出 `NullPointerException`。
3. **范围操作的性能**

   - 范围查询（如 `subSet()`）返回视图而非副本，操作效率高，但修改原集合可能影响视图。
4. **合理选择集合类型**

   - 若无需排序，优先用 `HashSet`；若需插入顺序，用 `LinkedHashSet`；仅在需要排序或范围查询时使用 `TreeSet`。

### **总结**

`TreeSet` 通过红黑树实现了有序集合，提供高效的排序和范围查询能力，适用于需要对元素进行自然排序或定制排序的场景。相比 `HashSet` 和 `LinkedHashSet`，其插入、查询性能略低，但支持强大的范围操作（如 `subSet()`、`lower()`、`higher()`）。合理利用
TreeSet 的排序特性，可简化业务逻辑（如排行榜、区间筛选），但需注意元素的可比性及性能开销。
---
⬅️ [[02-LinkedHashSet|LinkedHashSet]] 🏠 [[00-Java|00-Java]] ➡️ [[04-TreeSet源码分析|TreeSet源码分析]]