TreeSet 源码解析

​

我的人生就像在白夜里走路。——东野圭吾《白夜行》

0 前言

上篇我们分析了HashSet，它是组合了 HashMap 实现的，那TreeSet会是怎么实现的呢？没错！组合 TreeMap 实现.

1 继承体系

​

• 继承了抽象类AbstracSet，方便扩展
• 实现的 SortedSet,解锁如下方法
  ​
• 实现 NavigableSet 接口，和 NavigableMap 接口类似，提供了各种导航方法
  ​
• 实现 Cloneable 接口，可被克隆
• 实现Serializable接口，可被序列化
  ​

2 属性

和 HashSet设计几乎一致

• 后备的 map
  ​
• 固定的value
  ​

3 构造方法

3.1 无参

• 构造一个新的空TreeSet，并根据其元素的自然顺序对其进行排序.插入set中的所有元素必须实现Comparable接口.此外,所有这些元素必须相互可比较:e1.compareTo(e2) 不得为集合中的任何元素e1和e2引发ClassCastException.如果用户尝试向违反此约束的集合中添加元素（例如，用户试图向其元素为整数的集合中添加字符串元素），则add调用将引发ClassCastException.
  
  ​

3.2 有参

• 构造一个包含指定集合中元素的新TreeSet，并根据其元素的自然顺序对其进行排序。 插入集合中的所有元素必须实现Comparable接口。 此外，所有这些元素必须相互可比较：e1.compareTo（e2）不得为集合中的任何元素e1和e2引发ClassCastException.
  ​
• 构造一个新的TreeSet，其中包含与指定的sorted set相同的元素，并使用相同的顺序
  ​
• 构造一个新的空树集，根据指定的比较器排序。 插入到集合中的所有元素必须与指定的比较器相互比较：compare.compare（e1，e2）不得为集合中的任何元素e1和e2抛出ClassCastException。 如果用户尝试将违反此约束的元素添加到集合中，则add调用将引发ClassCastException。
  ​

设计大都类似,看几个核心方法.

4 add

• 直接使用的是 TreeMap#put 并判断
  ​

如果指定的元素尚不存在，则将其添加到该set中。 更确切地讲，如果set中不包含任何元素e2，使得(e==null ? e2==null : e.equals(e2)),则将指定的元素e添加到该set中.如果此set已包含该元素，则调用将使该集合保持不变并返回false。

和HashSet的实现一样，也是利用了Map保存的Key-Value键值对的Key不会重复的特点.诸多类似 add 这种方法实现比较简单,所以 TreeSet 自己简单组合实现下即可.

借由不重复 key 特点,我们还可以用其对 key 进行去重,TreeSet 底层使用的是 TreeMap，TreeMap 在 put 的时候，如果发现 key 是相同的，会把 value 值进行覆盖，所有不会产生重复的 key ，利用这一特性，使用 TreeSet 正好可以去重.

5 ceiling

• TreeSet中实现NavigableSet接口
  ​
• 而调用的依旧是 TreeMap 中的实现
  ​

• TreeMap 中的 KeySet 定义:
  ​
  与Values和EntrySet不同，TreeMap 中的 KeySet类是静态的，委派给NavigableMap以供SubMap使用，这胜过需要对以下迭代器方法进行类型测试的麻烦，这些迭代器方法分别在main和submap类中定义

6 总结

总体设计和 HashSet 无异.

• 基于TreeMap实现的，支持自然排序和自定义排序
• 不允许null值；
• 非线程安全，并发场景下可以使用Collections.synchronizedSortedSet(new TreeSet(...))包装.