基本介绍

TreeSet位于java.util包，于JDK1.2引入，实现了Set接口和SortedSet接口，这也就意味着TreeSet可以自定义排序规则。其中的NavigableSet是在JDK1.6引入的对SortedSet增强的导航Set，便于返回给定搜索目标的最接近匹配的结果。
TreeSet.png
TreeSet的底层基于TreeMap（维护了一个有序二叉树）的NavigableSet实现。根据使用的构造函数，元素使用其自然顺序或在集合创建时提供的Comparator进行排序。
TreeSet包含了两个重要的成员变量

  1. // 用于数据存储的NavigableMap的引用
  2. private transient NavigableMap<E,Object> m;
  4. // 构造Map的统一value指向
  5. private static final Object PRESENT = new Object();

构造方法

  1. // TreeSet默认构造方法，其余public修饰的外部可访问构造方法指向于此
  2. // TreeSet基于Map实现，Map的实现类需为NavigableMap接口的实现类
  3. TreeSet(NavigableMap<E,Object> m) {
  4.     this.m = m;
  5. }
  7. // TreeSet默认构造方法，TreeMap实现了NavigableMap接口
  8. // 同时NavigableMap接口继承自SortedMap，NavigableMap为SortedMap的增强扩展接口
  9. // SortedMap于JDK1.2引入，SortedMap继承自顶层Map接口
  10. public TreeSet() {
  11.     this(new TreeMap<E,Object>());
  12. }
  14. // 指定一个用户默认排序规则的TreeSet
  15. public TreeSet(Comparator<? super E> comparator) {
  16.     this(new TreeMap<>(comparator));
  17. }
  19. // 指定一个包含若干元素的Collection入参的TreeSet构造方法，采用默认排序规则
  20. public TreeSet(Collection<? extends E> c) {
  21.     this();
  22.     addAll(c);
  23. }
  25. // 指定一个入参为SortedSet的构造方法，采用传入SortedSet的排序规则
  26. public TreeSet(SortedSet<E> s) {
  27.     this(s.comparator());
  28.     addAll(s);
  29. }

常用方法

使用TreeSet自定义排序规则的时候，需要注意，TreeSet基于TreeMap实现，如果自定义排序规则，返回的值为固定值，则视为同一元素，不会再往集合中继续添加元素。
示例：

  1. public class TestTreeSet {
  2.     public static void main(String[] args) {
  3.         TreeSet<String> treeSet = new TreeSet<>(Comparator.comparingInt(x -> 0));
  4.         treeSet.add("1");
  5.         treeSet.add("2");
  6.         treeSet.add("3");
  7.         System.out.println("TreeSet =" + treeSet);
  8.     }
  9. }

输出结果：

  1. TreeSet =[1]

如果想按照字符串的长度进行排序

  1. public static void main(String[] args) {
  2.     TreeSet<String> treeSet = new TreeSet<>(Comparator.comparing(String::length));
  3.     treeSet.add("-");
  4.     treeSet.add("---");
  5.     treeSet.add("---");
  6.     treeSet.add("--");
  7.     System.out.println("TreeSet =" + treeSet);
  8. }

输出结果：

  1. # 实现了排序和去重的目的
  2. TreeSet =[-, --, ---]

总结

  • TreeSet不是线程安全的，如果需要保证线程安全，应该使用Collections.synchronizedSortedSet对该Set进行包装。
  • TreeSet的排序基于TreeMap中的静态内部类KeySet实现，且KeySet实现了NavigableSet接口，TreeSet的基本操作（ add 、 remove和contains ）时间成本为 log(n) 。
  • TreeSet是集合框架中SortedSet最常用的实现类，默认排序规则为自然排序（升序），也可以基于用户自定义排序规则排序。
  • 相比于HashSet、LinkedHashSet，TreeSet在数据量较大时性能低于前面两者，优势是有序，因此可根据具体的场景进行选择。