Set实现（3）| TreeSet

在Java集合框架中，TreeSet是一个用于存储不重复元素的有序集合。它实现了Set接口，并提供了元素按照自然顺序或者自定义顺序的排序。TreeSet的主要优点是它不允许存储重复元素，并且能够提供快速的插入、删除和查询操作。

1. TreeSet的适用范围

• 去重并保持排序：当你需要存储不重复的元素，并且希望它们按照一定的顺序排列时，如排行榜、有序列表等。
• 有序集合：如果元素的顺序很重要，可以使用TreeSet。
• 快速访问：如果你需要频繁地进行添加、删除和检查操作，TreeSet是一个很好的选择。

2. 源码分析与实例

2.1 内部结构

TreeSet的内部是基于一个TreeMap实例。所有的元素实际上是作为TreeMap的键来存储的，而TreeMap则通过红黑树数据结构来维护元素的排序和唯一性。

private transient HashMap<E,Object> map;

2.2 添加元素

add方法通过调用内部的TreeMap的put方法来添加元素。如果put返回null，则说明之前没有这个元素，因此添加成功。同时，新元素会被添加到红黑树中适当的位置以保持排序。

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

2.3 删除元素

remove方法首先检查传入的对象是否为null，然后调用TreeMap的remove方法来删除元素。

public boolean remove(Object o) {
    if (o==null) return false;
    return map.remove(o)!=null;
}

2.4 检查元素

contains方法根据传入的对象是否为null，分别调用TreeMap的containsValue和containsKey方法。

public boolean contains(Object o) {
    if (o==null) return false;
    return map.containsKey(o);
}

2.5 示例

import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        // 创建一个TreeSet实例
        TreeSet<String> set = new TreeSet<>();

        // 添加元素
        set.add("Alice");
        set.add("Bob");
        set.add("Charlie");
        set.add(null); // 允许添加null元素，但只能有一个

        // 检查元素
        System.out.println("Contains 'Alice': " + set.contains("Alice")); // true
        System.out.println("Contains 'David': " + set.contains("David")); // false

        // 删除元素
        set.remove("Alice");
        System.out.println("After removing 'Alice': " + set); // [Bob, Charlie]

        // 遍历元素
        for (String name : set) {
            System.out.println(name);
        }
    }
}

3. 总结

TreeSet是Java集合框架中的一个非常有用的类，它通过内部的TreeMap和红黑树实现了快速的添加、删除和查询操作。在使用TreeSet时，需要注意其不保证元素的顺序，并且不能存储重复的元素。在需要去除重复元素且关心元素顺序的场景下，TreeSet是一个很好的选择。