TreeSet的继承关系
按照惯例，先来看TreeSet类的继承关系：
1
2
public class TreeSet extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
毫不意外的继承了抽象类AbstracSet，方便扩展；
实现了一个NavigableSet接口，和NavigableMap接口类似，提供了各种导航方法；
实现了Cloneable接口，可以克隆；
实现了Serializable接口，可以序列化；
这里主要看NavigableSet接口类：
1public interface NavigableSet extends SortedSet<E>
熟悉的味道，继承SortedSet接口。SortedSet则提供了一个返回比较器的方法：
1Comparator
和SortedMap一样，支持自然排序和自定义排序。自然排序要求添加到Set中的元素实现Comparable接口，自定义排序要求实现一个Comparator比较器。
源码分析
关键点
关键点自然是TreeSet如何保证元素不重复以及元素有序的，前面说了它是基于TreeMap实现的，那我们来看看吧。
1
2
3
4
private transient NavigableMap m; // 保证有序
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object(); // 固定Value
纵观TreeSet源码，发现只有这两个属性（还有个uid，这里就不算了）。很明显，m是用来保存元素的，但m声明的是NavigableMap而不是TreeMap。可以猜测，TreeMap应该是在构造方法里实例化的，这里使用NavigableMap可以让TreeSet更加灵活。PRESENT和HashSet中的PRESENT作用一样，作为固定Value值进行占位的。
再看add和remove方法：
1
2
3
4
5
6
7
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
和HashSet的实现一样，也是利用了Map保存的Key-Value键值对的Key不会重复的特点。
构造函数
果然，TreeSet中的TreeMap是在构造函数中初始化的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public TreeSet() {
this(new TreeMap<>()); // 默认自然排序的TreeMap
}
public TreeSet(Comparator
this(new TreeMap<>(comparator)); // 自定义比较器的TreeMap
}
public TreeSet(Collection
this(); // 还是用的默认
addAll(c); // 将元素一个一个添加到TreeMap中
}
public TreeSet(SortedSet<E> s) {
this(s.comparator()); // 使用传入的SortedSet的比较器
addAll(s); // 一个一个添加元素
}
默认实例化了一个自然排序的TreeMap，当然，我们可以自定义比较器。
这里跟踪下addAll方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean addAll(Collection
// Use linear-time version if applicable
if (m.size()==0 && c.size() > 0 &&
c instanceof SortedSet &&
m instanceof TreeMap) {
SortedSet set = (SortedSet
TreeMap map = (TreeMap) m; // 强转成TreeMap
Comparator<?> cc = set.comparator();
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方法：
1
2
3
4
5
6
void addAllForTreeSet(SortedSet
try {
buildFromSorted(set.size(), set.iterator(), null, defaultVal);
} catch (java.io.IOException | ClassNotFoundException cannotHappen) {
}
}
看到buildFromSorted，应该很熟悉，在TreeMap的文章中分析过。该方法将传入的集合元素构造成了一棵最底层的结点为红色，而其他结点都是黑色的红黑树。
导航方法
既然实现了NavigableSet，那各种导航方法自然少不了。它们的实现也很简单，直接调用m对应的导航方法即可。例如：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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,?> e = m.pollFirstEntry();
return (e == null) ? null : e.getKey();
}
public NavigableSet descendingSet() { // 倒排Set
return new TreeSet<>(m.descendingMap());
}
......
这里需要注意的是返回子集合的方法，例如：headSet。返回的子集合是可以添加和删除元素的，但是有边界限制，举个栗子。
1
2
3
4
5
6
7
8
9
10
11
12
13
// 前面构造了一个存储Int的Set
// 3、5、7、9
SortedSet<Integer> 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的实现：
1
2
3
public Iterator<E> descendingIterator() {
return m.descendingKeySet().iterator();
}
总结
TreeSet是基于TreeMap实现的，支持自然排序和自定义排序，可以进行逆序输出；
TreeSet不允许null值；
TreeSet不是线程安全的，多线程环境下可以使用SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...))；
欢迎工作一到八年的Java工程师朋友们加入Java高级交流群：828697593
本群提供免费的学习指导 架构资料 以及免费的解答
不懂得问题都可以在本群提出来 之后还会有直播平台和讲师直接交流噢
哦对了，喜欢就别忘了关注一下哦~
