Java集合框架之TreeSet浅析
一、TreeSet综述：
1.1TreeSet简介：
TreeSet是Java集合框架的重要成员，先来看看TreeSet在jdk1.8中的定义吧：
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
-
一种基于
TreeMap的NavigableSet实现。因为TreeSet继承了AbstractSet抽象类，所以它是一个set集合，可以被实例化，且具有set的属性和方法。
TreeSet中的元素支持2种排序方式：自然排序或者根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。
TreeSet的性能比HashSet差但是我们在需要排序的时候可以用TreeSet因为他是自然排序也就是升序
TreeSet是有序的Set集合，因此支持add、remove、get等方法。
TreeSet的本质是一个"有序的，并且没有重复元素"的集合，它是通过TreeMap实现的。TreeSet中含有一个"NavigableMap类型的成员变量"m，而m实际上是"TreeMap的实例"。
1.2TreeSet排序相关：
- TreeSet支持两只排序方法：自然排序与定制排序。如果试图把一个对象添加到TreeSet时，则该对象的类必须实现Comparable接口，否则程序会抛出异常java.lang.ClassCastException。原因是TreeSet集合中添加两个Err对象，添加第一个对象时，TreeSet里没有任何元素，所以不会出现任何问题；当添加第二个Err对象时，TreeSet就会调用该对象的compareTo(Object obj)方法与集合中的其他元素进行比较—如果其对应的类没有实现Comparable 接口，则会引发ClassCastException异常
-
自然排序：
TreeSet会调用集合元素的compareTo(Object o)方法来比较元素之间的大小关系，然后将集合元素按升序排列，这种方式是自然排序。
TreeSet类的add()方法中会把存入的对象提升为Comparable类型
调用对象的compareTo()方法和集合中的对象比较
根据compareTo()方法返回的结果进行存储
-
定制排序：
如果需要实现定制排序，例如以降序排列，则可通过Comparator接口的帮助。该接口里包含一个int compate(T o1,T o2)方法，该方法用于比较o1和o2的大小：如果该方法返回正整数，则表明o1大于o2;如果该方法返回0，则表明o1等于o2；如果该方法返回负整数，则表明o1小于o2。
如果传入了Comparator的子类对象, 那么TreeSet就会按照比较器中的顺序排序
add()方法内部会自动调用Comparator接口中compare()方法排序
调用的对象是compare方法的第一个参数,集合中的对象是compare方法的第二个参数
-
两种方式的区别
TreeSet构造函数什么都不传, 默认按照类中Comparable的顺序(没有就报错ClassCastException)
TreeSet如果传入Comparator, 就优先按照Comparator
-
-
注意：
在实现compareTo(Object o)方法时，都需要将被比较对象obj强制类型转换成相同类型，因为只有相同类的两个示例才会比较大小。 当试图把一个大对象添加到TreeSet集合时，TreeSet会调用该对象的compareTo(Object o)方法与集合中的其他元素进行比较—这就要求集合中的其他元素与该元素是同一类的示例，否则抛出ClassCaseException异常。总之一句话，如果希望TreeSet能够正常运行，TreeSet只能添加同一类型对象。
- 与HashSet类似的是，如果TreeSet中包含了可变对象，当可变对象的示例变量被修改时，TreeSet在处理这些对象时将非常复杂，而且容易出错。为了让程序更加健壮，推荐不要修改放入HashSet和TreeSet集合中元素的关键实例变量。
1.3TreeSet实现原理：
TreeSet是依靠TrreMap实现的： TreeSet底层则采用一个NavigableMap来保存TreeSet集合的元素。但实际上，由于NavigableMap只是一个接口，因底层依然是使用TreeMap来包含Set集合中的所有元素。
TreeSet()是使用二叉树的原理对新add()的对象按照指定的顺序排序（升序、降序），每增加一个对象都会进行排序，将对象插入的二叉树指定的位置。
1.4TreeSet在Set接口中的数据结构：
二、TreeSet方法摘要：
| 构造方法摘要 | |
|---|---|
TreeSet() 构造一个新的空 set，该 set 根据其元素的自然顺序进行排序。 |
|
TreeSet(Collection<? extends E> c)构造一个包含指定 collection 元素的新 TreeSet，它按照其元素的自然顺序进行排序。 |
|
TreeSet(Comparator<? super E> comparator)构造一个新的空 TreeSet，它根据指定比较器进行排序。 |
|
TreeSet(SortedSet<E> s)构造一个与指定有序 set 具有相同映射关系和相同排序的新 TreeSet。 |
|
| 方法摘要 | |
|---|---|
boolean |
add(E e)将指定的元素添加到此 set（如果该元素尚未存在于 set 中）。 |
boolean |
addAll(Collection<? extends E> c)将指定 collection 中的所有元素添加到此 set 中。 |
E |
ceiling(E e)返回此 set 中大于等于给定元素的最小元素；如果不存在这样的元素，则返回 null。 |
void |
clear()移除此 set 中的所有元素。 |
Object |
clone()返回 TreeSet 实例的浅表副本。 |
Comparator<? super E> |
comparator()返回对此 set 中的元素进行排序的比较器；如果此 set 使用其元素的自然顺序，则返回 null。 |
boolean |
contains(Object o)如果此 set 包含指定的元素，则返回 true。 |
Iterator<E> |
descendingIterator()返回在此 set 元素上按降序进行迭代的迭代器。 |
NavigableSet<E> |
descendingSet()返回此 set 中所包含元素的逆序视图。 |
E |
first()返回此 set 中当前第一个（最低）元素。 |
E |
floor(E e)返回此 set 中小于等于给定元素的最大元素；如果不存在这样的元素，则返回 null。 |
SortedSet<E> |
headSet(E toElement) 返回此 set 的部分视图，其元素严格小于 toElement。 |
NavigableSet<E> |
headSet(E toElement, 返回此 set 的部分视图，其元素小于（或等于，如果 inclusive 为 true）toElement。 |
E |
higher(E e)返回此 set 中严格大于给定元素的最小元素；如果不存在这样的元素，则返回 null。 |
boolean |
isEmpty()如果此 set 不包含任何元素，则返回 true。 |
Iterator<E> |
iterator()返回在此 set 中的元素上按升序进行迭代的迭代器。 |
E |
last()返回此 set 中当前最后一个（最高）元素。 |
E |
lower(E e)返回此 set 中严格小于给定元素的最大元素；如果不存在这样的元素，则返回 null。 |
E |
pollFirst()获取并移除第一个（最低）元素；如果此 set 为空，则返回 null。 |
E |
pollLast()获取并移除最后一个（最高）元素；如果此 set 为空，则返回 null。 |
boolean |
remove(Object o)将指定的元素从 set 中移除（如果该元素存在于此 set 中）。 |
int |
size()返回 set 中的元素数（set 的容量）。 |
NavigableSet<E> |
subSet(E fromElement,返回此 set 的部分视图，其元素范围从 fromElement 到toElement。 |
SortedSet<E> |
subSet(E fromElement, E toElement) 返回此 set 的部分视图，其元素从 fromElement（包括）到 toElement（不包括）。 |
SortedSet<E> |
tailSet(E fromElement) 返回此 set 的部分视图，其元素大于等于 fromElement。 |
NavigableSet<E> |
tailSet(E fromElement, 返回此 set 的部分视图，其元素大于（或等于，如果 inclusive 为 true）fromElement。 |
参考文章：
https://www.cnblogs.com/Tony-cheen/p/5681831.html
https://www.cnblogs.com/heyongjun1997/p/5681919.html
http://blog.csdn.net/jinhuoxingkong/article/details/51191106
https://www.cnblogs.com/yzssoft/p/7127894.html
https://www.jianshu.com/p/54d464837a06