附图：
timg.jpg
前言：
TreeSet是一个有序的集合，它的作用是提供有序的Set集合。底层数据结构是红黑树（是一种自平衡的二叉树），排序效率高效。它继承了AbstractSet抽象类，实现了NavigableSet<E>，Cloneable，Serializable接口。TreeSet是基于TreeMap实现的，TreeSet的元素支持2种排序方式：自然排序或者根据提供的Comparator（比较器）进行排序。
保证有序：红黑树保证有序
保证唯一：set保证唯一，根据比较的返回值是否为0。
（1）自然排序
使用的是无参构造，默认是自然排序。元素所在的类要实现comparable接口，并且要重写compareTo()方法。
（2）比较器排序
有参构造，集合的构造方法接收comparator的实现类对象，实现类需要重写compare()方法。
一： 结构关系
public class TreeSet<E>
extends AbstractSet<E>
implements NavigableSet<E>,Cloneable, Serializable {
TreeSet 是一个有序的集合，它的作用是提供有序的Set集合。它继承于AbstractSet抽象类，实现了NavigableSet<E>, Cloneable, java.io.Serializable接口。
TreeSet 继承于AbstractSet，所以它是一个Set集合，具有Set的属性和方法。
TreeSet 实现了NavigableSet接口，意味着它支持一系列的导航方法。比如查找与指定目标最匹配项。
TreeSet 实现了Cloneable接口，意味着它能被克隆。
TreeSet 实现了java.io.Serializable接口，意味着它支持序列化。
二：重要知识点
（1）：重要属性
（2）：构造方法
（3）：常用功能
（4）：迭代方法
（5）：两种排序（自然排序，比较器排序）
（6）： HashSet，TreeSet，LinkedHashSet之间的区别：http://shmilyaw-hotmail-com.iteye.com/blog/1836431
三：源码浅析
3.1 重要属性
//TreeSet的实现基于TreeMap(TreeMap实现NavigableMap),内部维护一个NavigableMap
private transient NavigableMap<E, Object> m;
//作用是把TreeSet的元素存入TreeMap中时,元素作为键,PRESENT作为值
private static final Object PRESENT = new Object();
我们可以看到它的底层是用TreeMap来实现的，其实跟hashSet一样，真正的数据存在map的key中，儿value只是用一个PRESENT 普通对象填充，这样根据map的key不能重复就保证了其存储元素唯一的特性
3.2 构造方法
//这个构造器不是导出API,在下面构造器有使用这个构造器
TreeSet(NavigableMap<E, Object> m) {
this.m = m;
}
//调用第一个的构造器,创建一个空的TreeSet,不提供比较器,使用元素自然顺序
public TreeSet() {
this(new TreeMap<E, Object>());//相当于执行了一句this.m = new TreeMap<E, Object>();
}
//调用第一个构造器,提供比较器,比较器由TreeMap维护,TreeSet本身没有比较器
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
上边的无参构造又调用的一个有参构造，来new一个TreeMap来承载元素，这也印证了那一句“TreeSet的底层是TreeMap”（hashSet的底层是hashMap）
3.3 添加一个元素
//增加一个元素,可以看到e作为键,PRESENT作为值
public boolean add(E e) {
return m.put(e, PRESENT) == null;
}
我们可以看到，其添加方法就是调用map的put方法进行添加，元素为key，PRESENT为value
3.4 删除元素
//删除一个元素,根据删除返回的结果是否和PRESENT等同来返回是否删除成功
public boolean remove(Object o) {
return m.remove(o) == PRESENT;
}
//清空Set
public void clear() {
m.clear();
}
删除同样是调用map的删除操作
3.5 获取元素
//返回集合的第一个元素
public E first() {
return m.firstKey();
}
//返回集合的最后一个元素
public E last() {
return m.lastKey();
}
// NavigableSet API methods
//返回比e小的最大元素,不包括e
public E lower(E e) {
return m.lowerKey(e);
}
//返回比e小的最大元素,包括e
public E floor(E e) {
return m.floorKey(e);
}
//返回比e大的最小元素,包括e
public E ceiling(E e) {
return m.ceilingKey(e);
}
//返回比e大的最小元素,不包括e
public E higher(E e) {
return m.higherKey(e);
}
//返回并删除第一个元素
public E pollFirst() {
Map.Entry<E, ?> e = m.pollFirstEntry();
return (e == null) ? null : e.getKey();
}
//返回并删除最后一个元素
public E pollLast() {
Map.Entry<E, ?> e = m.pollLastEntry();
return (e == null) ? null : e.getKey();
}
由于TreeSet是有序的，所以他有一系列的获取方法，其本质还是调用map的方法获取key并返回
3.7 升序降序
//默认就是升序的
//返回一个降序的TreeSet
public NavigableSet<E> descendingSet() {
return new TreeSet<>(m.descendingMap());
}
TreeSet有升序降序的功能，默认是升序，所以只提供了一个降序方法，底层调用map将key降序而已
3.8 容量
//Set含有的元素个数
public int size() {
return m.size();
}
//判断是否为空,其实就是size会否为0
public boolean isEmpty() {
return m.isEmpty();
}
3.9 迭代器
//返回升序迭代器
public Iterator<E> iterator() {
return m.navigableKeySet().iterator();
}
//返回降序迭代器
public Iterator<E> descendingIterator() {
return m.descendingKeySet().iterator();
}
3.10唯一性和有序性剖析
http://blog.csdn.net/dch9210/article/details/50951690
四：操作案例
略
五：线程安全问题
线程测试代码：
/**
* ClassName: TestTreeSet
* @author lvfang
* @Desc: TODO
* @date 2017-9-22
*/
public class TestTreeSet implements Runnable {
private TreeSet<Integer> set = null;
public TestTreeSet(TreeSet<Integer> set){
this.set = set;
}
@Override
public void run() {
for(int i=0; i<50;i++) set.add(i);
System.out.println(set.size());
}
public static void main(String[] args) {
TreeSet<Integer> set = new TreeSet<>();
//单线程运行
new Thread(new TestTreeSet(set)).start();
//多线程运行
//开启5个线程，每个向set中存储0-50，由于set是元素唯一的，所以最终只能有50个元素
for(int i=0;i<5;i++){
new Thread(new TestTreeSet(set)).start();
}
}
}
解决方案1：操作方法加同步
解决方案2：SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));
六：总结
七：相关文章
http://www.cnblogs.com/13jhzeng/p/5845845.html
http://www.cnblogs.com/yzf666/p/6473146.html
网友评论