上一篇文章中介绍了 Set 接口和它的两个主要实现，HashSet 和 LinkedHashSet。回忆一下它们的特点，HashSet 特点是无序，而 LinkedHashSet 则是有有序的，它的顺序是按照集合内元素的添加顺序。
它们具体的内部实现也较为简单，都是对两个 Map 数据结构的封装，应该都不难理解。
今天介绍的数据结构也同属于 Set 接口之下，同样不能存放相同的元素，但是最大的不同之处在于它是有顺序的，它就是 TreeSet。
SortedSet
在开始分析源码之前还是先来看看 TreeSet 的类图：
TreeSet.png
从类图上看，出现了两个之前没有见过的接口，即 SortedSet 和 NavigableSet 。让我们先来看看 SortedSet 的注释和源码。
注释给我们提供了以下的这些信息：
-
SortedSet是一个「有序」的集合，它的顺序由Comparable或是Comparator的结果决定。这意味着SortedSet容器内的元素必须实现这两个接口中的任一一个。 - 所有实现
SortedSet接口的具体类，需要提供 4 个不同的构造函数，这里不再赘述，有兴趣的读者可以直接看这部分的注释。 -
SortedSet提供的部分获取某个范围元素的方法，都是前闭后开的。如果需要两个都是闭区间或是开区间，只能通过自己调整输入参数来控制。
现在我们已经了解了 SortedSet 和 TreeSet 「有顺序」的意思了，接着就看看 SortedSet 接口上有哪些有意思的方法。
-
first,last方法分别是返回集合内第一个和最后一个元素。 -
headSet(E toElement)返回集合内所有小于toElement元素的集合，注意这里是开区间，是「小于」而不是「小于等于」。 -
tailSet(E fromElement)与headSet类似，返回所有大于等于fromElement元素的集合，注意这里是闭区间，即是「大于等于」。 -
subSet(E fromElement, E toElement)返回fromElement和toElement范围之间的元素集合，注意这里是前面提到的前闭后开区间，即「大于等于」fromElement，「小于」toElement元素的集合。
SortedSet 关键方法就这些，准备进入下一个接口 NavigableSet 吧。
NavigableSet
NavigableSet 继承了 SortedSet 接口，并增加了数个方法，让我们逐一分析。
新增了 lower(E e)，floor(E e)，ceiling(E e)，higher(E e) 四个方法，分别返回集合内「小于」，「小于等于」，「大于等于」，「大于」输入参数的 e 的元素，如果集合内没有符合条件的参数，则返回 null。
pollFirst() 和 pollLast() 分别返回并移除集合中最小和最大的元素。
重载了父接口 SortedSet 中的 headSet ，tailSet，subSet 这些方法，增加了额外的参数，控制区间的闭合，让方法更加方便使用，具体可以看对应的方法签名和注释。
剩下值得一提的是 descendingSet 方法，该方法会返回一个当前集合降序排列的视图，而注释中也提及通常情况下升序操作的性能好于降序。
TreeSet
其实写到这里 TreeSet 本身并没有太多值得分析的，因为它与 HashSet 一样，真正存储数据，并进行各种操作的是代理给了 TreeMap。基本上前面提到的所有方法都是直接掉用了 TreeMap 上的相关方法。看下面的代码片段：
private transient NavigableMap<E,Object> m;
public E last() {
return m.lastKey();
}
public E pollFirst() {
Map.Entry<E,?> e = m.pollFirstEntry();
return (e == null) ? null : e.getKey();
}
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
return new TreeSet<>(m.headMap(toElement, inclusive));
}
额外可以从注释中了解的就是 add，remove，contains 这几个方法的时间复杂度为 log(n)。
下阶段预告
看完 Set 部分的源码你会发现其实大部分数据结构的操作都是由 Map 这个数据结构完成，包括了 HashMap 和 TreeMap，而 Map 作为开发人员日常使用频率最高的数据结构之一，可谓是 Java Collections Framework 中最核心的数据结构之一，而它的代码中也包含了大量必备的数据结构知识和算法，在面试中也是被问到最多的。
很多读者问我什么时候会开始 Map 源码的讲解，答案就是现在。从下一篇开始我会开始分析 Map 源码，因为其中涉及的知识点很多，我会写的非常细，估计会有4 ～ 5 篇专门来分析 Map 系列的源码。如果你希望真正了解和掌握 Java Collections Framework 的一些知识，我想接下来的文章是不容错过的。我也欢迎你提出任何问题，我都会回复你。下一篇见！
网友评论