1. TreeSet 概念

TreeSet 类同时实现了 Set 接口和 SortedSet 接口。SortedSet 接口是 Set 接口的子接口，可以实现对集合进行自然排序，因此使用 TreeSet 类实现的 Set 接口默认情况下是自然排序的，这里的自然排序指的是升序排序。
TreeSet 只能对实现了 Comparable 接口的类对象进行排序，因为 Comparable 接口中有一个 compareTo(Object o) 方法用于比较两个对象的大小。例如 a.compareTo(b)，如果 a 和 b 相等，则该方法返回 0；如果 a 大于 b，则该方法返回大于 0 的值；如果 a 小于 b，则该方法返回小于 0 的值。

2. 实现原理

TreeSet的底层是TreeMap，添加的数据存入了map的key的位置，而value则固定是PRESENT。TreeSet中的元素是有序且不重复的，因为TreeMap中的key是有序且不重复的。

2.1 私有属性

  1.     private transient NavigableMap<E,Object> m;
  2.     // 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。
  3.     private static final Object PRESENT = new Object();

NavigableMap 继承自 SortedMap，所以它的元素是有序的。
在 SortedMap 基础上，支持快速搜索符合条件的最近的元素。这里条件主要是指 lower(>), floor(>=)， ceiling(<)，higher(>)。
支持逆序访问。 descendingKeySet / descendingMap。
支持获取子集合，集合边界元素是否包含是可配的。

2.2 构造函数

  1. TreeSet(NavigableMap<E,Object> m) {
  2.         this.m = m;
  3.     }
  5.     /**
  6.      * 构造一个新的空树集，根据其元素的自然顺序进行排序。插入到集合中的所有元素必须实现可比较的接口。
  7.      * 此外，所有这些元素必须是相互可比的：e1.compareTo（e2）不能为集合中的任何元素e1和e2抛出ClassCastException。
  8.      * 如果用户尝试向违反此约束的集合添加元素（例如，用户尝试向元素为整数的集合添加字符串元素），则add调用将抛出ClassCastException。
  9.      */
  10.     public TreeSet() {
  11.         this(new TreeMap<E,Object>());
  12.     }
  14.     /**
  15.      *构造一个新的空树集，根据指定的比较器进行排序。
  16.      */
  17.     public TreeSet(Comparator<? super E> comparator) {
  18.         this(new TreeMap<>(comparator));
  19.     }
  21.     /**
  22.      *构造包含指定集合中元素的新树集，并根据其元素的自然顺序进行排序。
  23.      */
  24.     public TreeSet(Collection<? extends E> c) {
  25.         this();
  26.         addAll(c);
  27.     }
  29.     /**
  30.      * 构造一个新的树集，该树集包含相同的元素，并使用与指定排序集相同的顺序。
  31.      */
  32.     public TreeSet(SortedSet<E> s) {
  33.         this(s.comparator());
  34.         addAll(s);
  35.     }

2.3 add

  1.  public boolean add(E e) {
  2.         return m.put(e, PRESENT)==null;
  3.     }

如果指定的元素尚未存在，则将其添加到此集合。更正式地说，如果集合中不包含元素e2，则将指定的元素e添加到此集合中（e==null？e2==null:e.equals（e2））。如果此集合已经包含元素，则调用将保持集合不变并返回false。

2.4 remove

  1. public boolean remove(Object o) {
  2.         return m.remove(o)==PRESENT;
  3.     }

从该集合中删除指定的元素（如果存在）。更正式地说，如果这个集合包含这样一个元素，那么移除一个元素e，使得（o==null？e==null:o.equals（e））。如果此集合包含元素，则返回true（如果此集合因调用而更改，则返回等效值）(一旦调用返回，此集合将不包含元素。）