本文介绍了TreeSet如何在Java中实现。 (详细调查)，有一定的参考价值。 需要的朋友请参考。 我希望对你有帮助。
HashSet是基于HashMap实现的，那么TreeSet如何实现呢？ 没错！ 正如大家想的那样，它是基于TreeMap实现的。 所以，TreeSet的源代码也很简单，主要了解TreeMap。
TreeSet的继承关系
按照惯例，我们先看看TreeSet类的继承关系。
publicclasstreesetextendsabstractset
implements NavigableSet，Cloneable，java.io.Serializable
意外继承抽象类AbstracSet，容易扩展
实现了与NavigableMap界面类似的NavigableSet界面，提供了各种导航方法；
可以实现Cloneable接口并进行克隆；
实现了可序列化接口，可以序列化；
这里主要看NavigableSet接口类：
publicinterfacenavigablesetextendssortedset
熟悉的味道，继承SortedSet接口。 SortedSet提供了返回比较器的方法。
Comparator super E comparator (；
和SortedMap一样，支持自然排序和自定义排序。 对于自然排序，添加到Set中的元素必须实现Comparable接口，而自定义排序则必须实现Comparator比较器。
源代码分析
关键点
关键当然是TreeSet如何保证元素不重叠和元素有序，如上所述是基于TreeMap实现的，让我们来看看吧。
私有传输navigable map m； //保持秩序
//dummyvaluetoassociatewithanobjectinthebackingmap
privatestaticfinalobjectpresent=new object (； //固定值
通过查看TreeSet源代码，我们发现只有这两个属性(也有uid，但在这里不计算) 显然，m用于存储元素，但m声明的是NavigableMap而不是TreeMap。 据推测，TreeMap应该是用构建方法实例化的，这里可以通过使用NavigableMap提高TreeSet的灵活性。 PRESENT与HashSet的PRESENT一样，作为固定的Value值被占位符。
让我们看看add和remove的方法：
publicbooleanadd{
returnm.put(e，PRESENT )==null；
}
公共空间内存(objecto ) {
returnm.remove(o )==PRESENT；
}
与HashSet的实现相同，还具有利用Map保存的Key-Value键值对的Key不重复的特征。
构造函数
还是用构造函数初始化TreeSet的TreeMap。
公共树集
this (新流) )； //默认自然排序的TreeMap
}
公共流集(comparatorsuperecomparator ) {
新流计算机(this )； //定制比较器流映射
}
公共流集(collectionextendsec ) {
this (； //还是默认使用
addall(c )； 将//元素逐个添加到TreeMap
}
公共流集(sorted sets ) {
this(s.comparator ) )； //使用传入的SortedSet的比较器
addall(s )； //一个一个地添加元素
}
缺省情况下，会实例化自然排序的TreeMap。 当然，可以定制比较器。
在这里追踪addAll方法。
publicbooleanaddall (collectionextendsec ) (
//use linear-timeversionifapplicable
if(m.size(==0c.size ) ) 0
c instanceof SortedSet
m instanceof TreeMap )
{SortedSet extends E> set = (SortedSet extends E>) c;
TreeMap map = (TreeMap) m; // 强转成TreeMap
Comparator> cc = set.comparator();
Comparator super E> mc = map.comparator();
if (cc==mc || (cc != null && cc.equals(mc))) { // 要保证set和map的比较器一样
map.addAllForTreeSet(set, PRESENT); // TreeMap专门为TreeSet准备的方法
return true;
}
}
return super.addAll(c);
}
调用了TreeMap的addAllForTreeSet方法：
void addAllForTreeSet(SortedSet extends K> set, V defaultVal) {
try {
buildFromSorted(set.size(), set.iterator(), null, defaultVal);
} catch (java.io.IOException | ClassNotFoundException cannotHappen) {
}
}
看到buildFromSorted，应该很熟悉，在TreeMap的文章中分析过。该方法将传入的集合元素构造成了一棵最底层的结点为红色，而其他结点都是黑色的红黑树。
导航方法
既然实现了NavigableSet，那各种导航方法自然少不了。它们的实现也很简单，直接调用m对应的导航方法即可。例如：
public E first() {
return m.firstKey(); // 返回第一个元素
}
public E lower(E e) {
return m.lowerKey(e); // 返回小于e的第一个元素
}
public NavigableSet headSet(E toElement, boolean inclusive) {
return new TreeSet<>(m.headMap(toElement, inclusive)); // 取前几个元素构成子集
}
public E pollFirst() { // 弹出第一个元素
Map.Entry e = m.pollFirstEntry();
return (e == null) ? null : e.getKey();
}
public NavigableSet descendingSet() { // 倒排Set
return new TreeSet<>(m.descendingMap());
}
......
这里需要注意的是返回子集合的方法，例如：headSet。返回的子集合是可以添加和删除元素的，但是有边界限制，举个栗子。
// 前面构造了一个存储Int的Set
// 3、5、7、9
SortedSet subSet = intSet.headSet(8); // 最大值7，超过7越界
for (Integer sub : subSet) {
System.out.println(sub);
}
subSet.add(2);
// subSet.add(8); // 越界了
subSet.remove(3);
for (Integer sub : subSet) {
System.out.println(sub);
}
TreeSet也是支持逆序输出的，因为有descendingIterator的实现：
public Iterator descendingIterator() {
return m.descendingKeySet().iterator();
}
总结
TreeSet是基于TreeMap实现的，支持自然排序和自定义排序，可以进行逆序输出；
TreeSet不允许null值；
TreeSet不是线程安全的，多线程环境下可以使用SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...))；