南瓜慢说知识库

# TreeSet简介

# 1 | 概述

java.util.TreeSet<E> 是 可自动排序、不允许重复元素 的集合，实现了 NavigableSet<E>、Cloneable、Serializable。 核心特点：

特性 说明
有序 元素按 自然顺序（Comparable）或 自定义 Comparator 升序排列
底层结构 红黑树（内部其实是包装了一棵 TreeMap<E,Object>）
操作复杂度 增删查 O(log n)
接口丰富 支持最值、邻近、范围视图、反序视图等导航操作

# 2 | 底层原理 & 数据结构

# 2.1 红黑树 (Red‑Black Tree)

  • 每个节点保存：key、左子/右子、父节点、颜色位

  • 插入/删除后通过 左旋/右旋 + 重新着色 保证：

    1. 根为黑
    2. 所有叶子（NIL）为黑
    3. 红节点的子节点都为黑
    4. 根到每个叶子路径的黑节点数相同

  • 树高 ≤ 2 log2(n + 1) ⇒ 操作最坏 O(log n)

# 2.2 TreeSet = TreeMap ⤴︎

public class TreeSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable {
    private transient NavigableMap<E,Object> m;
    private static final Object PRESENT = new Object();
    ...
    public boolean add(E e) { return m.put(e, PRESENT)==null; }
}

# 3 | 排序规则

  1. 默认：元素必须实现 Comparable<E>，按 compareTo 升序。
  2. 自定义：构造时传入 Comparator<? super E>；允许存储 “不具可比性” 的对象或自定义排序（降序、按长度等）。

⚠️ 无论哪种排序，一旦确定就应“不可变”：比较规则改变或元素自身值变动会破坏树形结构。

# 4 | 常用 API 速览

分类 方法 说明
增删查 add(e) / remove(o) / contains(o)
addAll(c) / clear() / size()
最值 first() / last() 最小 / 最大
邻近 lower(e) / higher(e) <e / >e
floor(e) / ceiling(e) ≤e / ≥e
区间视图 subSet(fromIncl, toExcl) [from, to)
headSet(toExcl) / tailSet(fromIncl)
反序 descendingSet() / descendingIterator()
遍历 iterator() (升序) Fail‑fast
并行流 (8+) stream() / parallelStream()

# 5 | 复杂度与性能

操作 复杂度 说明
add / remove / contains O(log n) 红黑树查找深度
first / last / floor / ceiling O(log n)
遍历 (iterator) O(n) 元素按排序顺序输出

# 5.1 TreeSet vs. 其他集合

需求 首选
唯一性 + 无序快速查找 HashSet (O(1) 平均)
唯一性 + 有序/邻近/区间 TreeSet (O(log n))
并发 + 有序 ConcurrentSkipListSet (跳表)

常数因子：TreeSet 内部节点对象多 1 个引用 + 1 byte 颜色，占用更高，速度略低于 HashSet。

# 6 | 线程安全 & Fail‑fast

  • 非线程安全：多线程并发写需显式加锁或使用 Collections.synchronizedSortedSet(set) 包装，或改用 ConcurrentSkipListSet。
  • Fail‑fast：迭代期间结构若被 其他线程或方法 修改，迭代器抛 ConcurrentModificationException（早期发现 BUG，不保证强一致）。

# 7 | 易踩坑注意事项

⚠️ 事项 说明
禁止 null 元素 若使用自然顺序，插入 null 抛 NullPointerException（JDK ≥ 1.8）；若自定义 Comparator 必须显式处理 null。
元素可变性 将“会变的字段”作为排序关键时，修改后集合顺序被破坏，影响查找——典型 坑。
➜ 元素应当不可变或 删除‑修改‑再插入。
比较器一致性 compare(a,b)==0 必须等价于 a.equals(b)，否则“看似重复”元素会并存。
子视图联动 通过 subSet / headSet 返回的是 实时视图，对其操作会同步影响原集合，反之亦然。

# 8 | 典型使用场景

  1. 最近值 / 最近房价

    int target = 100;
Integer lo = set.floor(target);  // <=100 的最大
Integer hi = set.ceiling(target); // >=100 的最小

  2. 滑动窗口 + 单调有序 统计区间最小/最大值：维护 TreeSet<Integer> 或 TreeMap<Integer, Integer> 计数。

  3. 区间调度 会议室安排、日程冲突检测：用 floor 查看前一场结束时间是否 > 新场开始。

  4. 去重排序 读取大量字符串后按字典序输出且无重复。

  5. 近似搜索 / 前缀索引 subSet("abc", "abd") 获取所有 "abc*" 前缀匹配词。

  6. 合并区间 / 连通块 利用 lower / floor 找相邻区间，快速合并。

# 9 | 示例代码

import java.util.*;

public class TreeSetDemo {
    public static void main(String[] args) {
        // 1⃣️ 价格排行榜（升序）
        TreeSet<Integer> prices = new TreeSet<>(Arrays.asList(105, 98, 120, 110));
        System.out.println("最低价：" + prices.first());   // 98
        System.out.println("最高价：" + prices.last());    // 120

        // 2⃣️ 找最接近 108 的价格
        int target = 108;
        Integer lower = prices.floor(target);   // 105
        Integer higher = prices.ceiling(target); // 110
        System.out.println(lower + ", " + higher);

        // 3⃣️ 区间视图：100~115 的价格
        System.out.println(prices.subSet(100, true, 115, true)); // [105, 110]

        // 4⃣️ 滑动窗口最大值 (k=3)：
        int[] nums = {4, 2, 12, 3, 8, 5};
        int k = 3;
        TreeMap<Integer, Integer> window = new TreeMap<>();
        for (int i = 0; i < nums.length; i++) {
            window.merge(nums[i], 1, Integer::sum);
            if (i >= k) { // 移除窗口左端
                int out = nums[i - k];
                window.merge(out, -1, (old, n) -> old + n == 0 ? null : old + n);
            }
            if (i >= k - 1) System.out.print(window.lastKey() + " "); // 12 12 12 8
        }
    }
}

# 10 | 总结

  • 红黑树实现的有序集合：所有操作 O(log n)，支持最值/邻近/区间检索
  • 应用：最近值查询、窗口最值、日程冲突检测、去重排序
  • 注意：禁止 null、避免“可变键”、多线程需同步
  • 与 HashSet 比：牺牲常数速度，换来 排序 + 导航；与 PriorityQueue 比：支持删除任意元素与邻近搜索
  • 对于并发高读写且需有序，可选 ConcurrentSkipListSet（跳表）。

🌟 如果你需要“唯一 + 排序 + 范围操作”这三件套，TreeSet 基本就是 Java 标准库里最顺手的工具。

← 多线程 →