转载

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(...))包装.
正文到此结束
本文目录