Java TreeSet-马育民老师

# 介绍

`TreeSet` 是 Java 集合框架中基于 **红黑树（自平衡二叉查找树）** 实现的 `Set` 接口实现类，其核心特性是 **元素有序且唯一**，支持高效的插入、查询和删除操作（时间复杂度均为 `O(log n)`）。以下是 `TreeSet` 的详细用法解析：

### 特点

TreeSet，无序不重复，可以 **指定排序**

线程不安全（不同步）。底层基于TreeMap实现。

# 一、核心特性

1. **有序性**：元素默认按 **自然排序**（需实现 `Comparable` 接口），或通过 `Comparator` 自定义排序规则。
2. **唯一性**：通过排序规则判断元素是否重复（`compareTo` 或 `compare` 返回 0 则视为重复，会被忽略）。
3. **非线程安全**：多线程环境下需手动同步（如 `Collections.synchronizedSet(new TreeSet<>())`）。
4. **无 `null` 元素**：自然排序时不允许 `null`（会抛 `NullPointerException`）；自定义比较器若支持 `null` 则可添加。

# 二、初始化方式

`TreeSet` 有两种常见初始化方式，分别对应自然排序和自定义排序：

### 1. 自然排序（元素实现 `Comparable`）

适用于元素本身实现了 `Comparable` 接口的场景（如 `String`、`Integer` 等）：
```java
import java.util.TreeSet;

// 自然排序：Integer 实现了 Comparable，默认按升序排列
TreeSet<Integer> numSet = new TreeSet<>();

// 自然排序：String 实现了 Comparable，默认按字典序排列
TreeSet<String> strSet = new TreeSet<>();
```

### 2. 自定义排序（通过 `Comparator`）
适用于元素未实现 `Comparable`，或需要自定义排序规则的场景：
```java
import java.util.Comparator;
import java.util.TreeSet;

// 示例1：整数降序排序
TreeSet<Integer> descNumSet = new TreeSet<>(Comparator.reverseOrder());

// 示例2：字符串按长度排序（长度相同则按字典序）
TreeSet<String> lenStrSet = new TreeSet<>(
    Comparator.comparingInt(String::length)  // 主排序：长度
              .thenComparing(Comparator.naturalOrder())  // 副排序：字典序
);
```

# 三、常用方法详解

### 1. 基本操作（CRUD）
| 方法         | 说明                                  | 示例                                  |
|--------------|---------------------------------------|---------------------------------------|
| `add(E e)`   | 添加元素（重复元素被忽略）            | `numSet.add(3);`                      |
| `remove(E e)`| 移除指定元素                          | `numSet.remove(3);`                   |
| `contains(E e)` | 判断元素是否存在                     | `numSet.contains(3); // true/false`   |
| `clear()`    | 清空集合                              | `numSet.clear();`                     |
| `size()`     | 返回元素个数                          | `int size = numSet.size();`           |

### 2. 有序性相关方法（核心优势）

`TreeSet` 提供了一系列基于元素有序性的特殊方法，适合范围查询和边界操作：

| 方法                | 说明                                  | 示例（元素：2,3,5,7）                 |
|---------------------|---------------------------------------|---------------------------------------|
| `first()`           | 返回最小元素                          | `numSet.first(); // 2`                |
| `last()`            | 返回最大元素                          | `numSet.last(); // 7`                 |
| `lower(E e)`        | 返回小于 `e` 的最大元素               | `numSet.lower(5); // 3`               |
| `higher(E e)`       | 返回大于 `e` 的最小元素               | `numSet.higher(5); // 7`              |
| `floor(E e)`        | 返回小于等于 `e` 的最大元素           | `numSet.floor(6); // 5`               |
| `ceiling(E e)`      | 返回大于等于 `e` 的最小元素           | `numSet.ceiling(4); // 5`             |
| `headSet(E e)`      | 返回小于 `e` 的子集合（视图）         | `numSet.headSet(5); // [2,3]`         |
| `headSet(E e, boolean inclusive)`      | 返回小于 `e` 的子集合（视图）。inclusive为true表示包含 `e`       | `numSet.headSet(5,true); // [2,3,5]`         |
| `tailSet(E e)`      | 返回大于等于 `e` 的子集合（视图）     | `numSet.tailSet(5); // [5,7]`         |
| `tailSet(E e, boolean inclusive)`      | 返回大于等于 `e` 的子集合（视图） 。inclusive为false表示不包含 `e`    | `numSet.tailSet(5,false); // [7]`         |
| `subSet(E from, E to)` | 返回 `[from, to)` 区间的子集合     | `numSet.subSet(3,7); // [3,5]`        |
| `subSet(E from,boolean fromInclusive, E to,boolean toInclusive)` | 返回 `from - to` 区间的子集合,true表示包含，false表示不包含     | `numSet.subSet(3,true,7,true); // [3,7]`        |

### 示例：范围查询
```java
TreeSet<Integer> set = new TreeSet<>();
set.add(2);
set.add(3);
set.add(5);
set.add(7);

// 获取所有小于 5 的元素
System.out.println(set.headSet(5)); // [2, 3]

// 获取 3 到 7 之间（含3，不含7）的元素
System.out.println(set.subSet(3, 7)); // [3, 5]

// 获取大于等于 5 的最小元素
System.out.println(set.ceiling(5)); // 5
```

# 四、遍历方式
`TreeSet` 的遍历结果**严格按排序规则输出**，常用遍历方式：

### 1. 增强 for 循环（最简洁）
```java
for (String s : strSet) {
    System.out.println(s);
}
```

### 2. 迭代器（支持边遍历边删除）
```java
Iterator<Integer> iterator = numSet.iterator();
while (iterator.hasNext()) {
    Integer num = iterator.next();
    if (num < 3) {
        iterator.remove(); // 安全删除（避免 ConcurrentModificationException）
    }
}
```

### 3. 流操作（Java 8+）
```java
// 过滤并打印所有长度大于 3 的字符串
strSet.stream()
      .filter(s -> s.length() > 3)
      .forEach(System.out::println);
```

# 五、自定义对象排序

当存储自定义对象时，需通过 **实现 `Comparable` 接口** 或 **提供 `Comparator`** 定义排序规则，否则会抛出 `ClassCastException`。

### 示例1：实现 `Comparable` 接口
```java
class Student implements Comparable<Student> {
    String name;
    int age;

public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

// 按年龄升序排序（年龄相同则按姓名字典序）
    @Override
    public int compareTo(Student o) {
        if (this.age != o.age) {
            return Integer.compare(this.age, o.age);
        }
        return this.name.compareTo(o.name);
    }

@Override
    public String toString() {
        return name + "(" + age + ")";
    }
}

// 使用：
TreeSet<Student> students = new TreeSet<>();
students.add(new Student("Bob", 22));
students.add(new Student("Alice", 20));
students.add(new Student("Charlie", 21));

System.out.println(students); 
// 输出：[Alice(20), Charlie(21), Bob(22)]（按年龄升序）
```

#### 另一种写法

元素类

```
package day18;

public class Student implements Comparable<Student>{

private String name;
	private int age;
	
	public Student(String name, int age) {
		this.name = name;
		this.age = age;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public int getAge() {
		return age;
	}
	public void setAge(int age) {
		this.age = age;
	}
	@Override
	public String toString() {
		return "Student [name=" + name + ", age=" + age + "]";
	}
	/**
	 * 根据年龄正序排序，年龄小的在前，年龄大的在后
	 */
	@Override
	public int compareTo(Student o) {
		
		if( this.age > o.getAge()){ // 下一个元素中的年龄  >  上一个元素的年龄
			return 1; 
		}else if( this.age < o.getAge() ){ // 下一个元素中的年龄  <  上一个元素的年龄
			return -1;
		}else{ 
			// 两个元素的年龄相等时，再比较名字
			// 如果返回0，就说明这2个对象内容相同，就会保留一个
			return this.name.compareTo(o.getName()) ;
		}
		
	}
	
	
}

```

测试类

```
package day18;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

public class S4TreeSet {

public static void main(String[] args) {
		
		Set<Student> set = new TreeSet<>();
		
		Student lilei = new Student("李雷", 20);
		Student lucy = new Student("lucy", 16);
		Student lili = new Student("lili", 16);
		Student hmm = new Student("韩梅梅", 25);
		Student zhangsan = new Student("张三", 16);
		
		Student lucy2 = new Student("lucy", 16);
		
		set.add(lilei);
		set.add(lucy);
		set.add(lili);
		set.add(hmm);
		set.add(zhangsan);
		set.add(lucy2);
		
		
		for( Student item : set){
			System.out.println(item);
		}
		
		
	}
}
```

### 示例2：使用 `Comparator` 自定义排序
```java
// 按姓名长度降序排序（不修改 Student 类）
TreeSet<Student> students = new TreeSet<>(
    Comparator.comparingInt((Student s) -> s.name.length()).reversed()
);

students.add(new Student("Bob", 22));       // 姓名长度 3
students.add(new Student("Alice", 20));     // 姓名长度 5
students.add(new Student("Charlie", 21));   // 姓名长度 7

System.out.println(students); 
// 输出：[Charlie(21), Alice(20), Bob(22)]（按姓名长度降序）
```

# 六、注意事项

1. **排序与 `equals` 的一致性**  
   `TreeSet` 判断元素是否重复依赖 `compareTo`/`compare` 方法（返回 0 则视为重复），而非 `equals`。因此，若 `a.equals(b)` 为 `true`，则 `a.compareTo(b)` 必须返回 0，否则会导致逻辑矛盾（如 `contains` 方法判断不准确）。

2. **性能对比**  
   - 与 `HashSet` 相比：`TreeSet` 插入/查询效率略低（`O(log n)` vs `O(1)`），但支持有序操作。  
   - 与 `LinkedHashSet` 相比：`TreeSet` 按**元素排序**，`LinkedHashSet` 按**插入顺序**。

3. **子集合视图的特性**  
   `headSet`、`tailSet`、`subSet` 返回的是原集合的**视图**，而非新集合。对视图的修改会同步到原集合，反之亦然。

# 总结
`TreeSet` 适合需要**元素有序且唯一**的场景（如排行榜、去重排序、范围筛选等）。其核心优势在于基于红黑树的高效有序操作，使用时需注意排序规则的定义（自然排序或自定义比较器），并合理利用范围查询方法提升效率。

原文出处：http://malaoshi.top/show_1IX3aMuf5Fu7.html