------Java培训、Android培训、iOS培训、.Net培训、期待与您交流！ -------
TreeSet集合储存的元素特点是唯一和自动排序，它是如何实现的呢？
class TreeSet implements Set {
private transient NavigableMap<E,Object> m;
public TreeSet() {
this(new TreeMap<E,Object>());
}
//无参构造执行了new TreeMap<E,Object>,其实是NavigableMap<E,Object> m = new TreeMap<E,Object>
//相当于对m进行了初始化，其实这里是多态！
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
}
1.查看add方法
public boolean add(E e) {
return m.put(e, PRESENT)==null;
//这时发现它使用的也是map的put方法
}
2.查看map
private transient NavigableMap<E,Object> m;
它是TreeSet的一个成员变量，是NavigableMap类型的
3.查看NavigableMap
public interface NavigableMap<K,V> extends SortedMap<K,V>
而NavigableMap确是一个接口，而且是继承了SortedMap的接口，向上查看都是接口。
怎么办呢？
4.这时回来查看m.put中的put方法看一下
public interface Map<K,V> {
V put(K key, V value);
}
发现这是map接口中的方法，没有具体方法语句。这时去查看API
5.查看API发现有一句描述：“基于 TreeMap 的 NavigableSet 实现”。
6.查看TreeMap
public class TreeMap<K,V>所以最终要看的是TreeMap的put()方法
extends AbstractMap<K,V>//继承自AbstractMap
implements NavigableMap<K,V>, Cloneable, Serializable//实现了NavigableMap接口
7.查看TreeMap的put()方法
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);//把当前的元素定义为根节点t
size = 1;
modCount++;
return null;
}
//由于TreeMap的数据结构是红黑树类型，以上代码就是判断根节点是否存在，如果不存在则造一个根节点。
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
//Comparator<? super K>是一个比较器，把comparator传过来，而comparator是TreeMap的一个成员变量
//private final Comparator<? super K> comparator;
//public TreeSet(Comparator<? super E> comparator)
//带参构造才会有此变量，无参构造没有comparator
if (cpr != null) {//当无参构造时cpr==null
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
//public interface Comparable<T>
//此接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序
//即此处实际上是把传过来的元素对象，转换成Comparable类型，既是向上转型！
do {
parent = t;
cmp = k.compareTo(t.key);
//这里是元素调用compareTo()方法与根进行比较compareTo()方法定义在Comparable接口中
//根据比较结果来决定元素在二叉树（红黑树）中的位置
//分析到此可以知道，元素的储存方式最终是由元素的compareTo()方法决定的
//而要使用compareTo()方法，就必须要实现Comparable接口
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
8.最终，由分析可知
真正的比较是依赖于元素的compareTo()方法，而这个方法是定义在 Comparable里面的。
所以，你要想重写该方法，就必须是先实现 Comparable接口。这个接口表示的就是自然排序。
9.所以，当用TreeSet储存元素时
如果用的是无参构造，那就是自然排序——元素具备比较性
A：当元素是String类型时
由于String已经实现 Comparable接口并重写了compareTo()方法所以可以保证有序和唯一。
B：当元素是自定义对象时，就需要自己根据条件来实现Comparable接口并重写compareTo()方法
如果是带参构造，那就是比较器排序——集合具备比较性
public TreeSet(Comparator<? super E> comparator)
带参构造传递的参数是comparator，而comparator是一个接口，实际传递的是实现类。
所以需要手写接口的实现类并重写compare()方法。或直接使用匿名内部类！