TreeSet学习（基于JDK1.8）

1. 概述

和TreeMap一样，自己好像从未使用过TreeSet 
学习HashSet时，发现HashSet的实现十分偷懒，直接基于HashMap历史构建哈希表，甚至重要方法的实现都是直接调用HashMap的方法
TreeSet的实现也是一样的，基于TreeMap实现
也就是说，TreeSet也是基于红黑树实现的，它的元素也是有序的

1.1 TreeSet的特性

TreeSet的类注释，提供了以下信息：

基于TreeMap实现了NavigableSet接口，支持返回给定搜索目标最近匹配项的导航方法
元素是有序的，可以按照自然顺序或创建set时提供的自定义比较器进行排序
性能：基本操作（add、remove、contains）的时间复杂度为 O ( l o g 2 n ) O(log2_n) O(log2n)
TreeSet是非线程安全的，多线程环境下访问，可以通过Collections.synchronizedSortedSet()方法转为线程安全的set类
使用fail-fast迭代器：一旦创建了迭代器，除非使用迭代器的remove方法，其他任何改变HashSet结构的方法都将使得迭代器抛出ConcurrentModificationException异常

总结

TreeSet基于TreeMap，实现了NavigableSet接口
元素有序（自然顺序或按照自定义比较器排序）、非线程安全、使用fail-fast迭代器
基本操作的时间复杂度为 O ( l o g 2 n ) O(log2_n) O(log2n)

1.2 类图

TreeSet类的声明如下

public class TreeSet extends AbstractSet
    implements NavigableSet, Cloneable, java.io.Serializable

类图如下
- 直观地看，TreeSet继承了AbstractSet抽象类，实现了NavigableSet、Cloneable、Serializable接口
- TreeSet内部，有一个基于NavigableMap接口的字段；实际创建时，都将实例化成TreeMap
- 可见，TreeSet确实是基于TreeMap实现的
AbstractSet抽象类：对Set接口的骨架级实现，最小化实现Set接口所需的工作量
NavigableSet接口：
- 继承了SortedSet接口，增加了返回给定搜索目标最近匹配项的道行方法
- SortedSet接口，继承Set接口、为元素提供全序；元素可以按照其自然顺序或创建时提供自定义比较器进行排序
Cloneable接口：表明TreeSet支持clone() 方法
Serializable接口：表明TreeSet支持序列化和反序列化

1.3 数据结构（成员变量）

成员变量如下：
- m：基于NavigableMap接口，构造函数中都使用TreeMap初始化该字段
- PRESENT：key对应真实的元素，value将无意义；将value统一指向PRESENT这个类常量，而非单独初始化
```
// 
private transient NavigableMap m;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
```
从成员变量的定义可以看出，TreeSet是基于NavigableMap接口的实现类（TreeMap）实现的

1.4 构造函数

5个pulic构造函数，还有一个内部的default构造函数

default构造函数，是其他构造函数的基础，用于初始化核心成员变量m

// 初始化成员变量m
TreeSet(NavigableMap m) {
    this.m = m;
}

// 创建一个空的、基于元素自然顺序的set
public TreeSet() {
    this(new TreeMap());
}

// 自定义比较器，创建一个空的set
public TreeSet(Comparator comparator) {
    this(new TreeMap<>(comparator));
}

// 创建包含指定元素的、基于自然顺序的set
public TreeSet(Collection c) {
    this();
    addAll(c);
}

// 基于现有的set创建TreeSet
public TreeSet(SortedSet s) {
    this(s.comparator());
    addAll(s);
}

常用的构造函数，应该是TreeSet() 和 TreeSet(Comparator comparator)

2. 重要方法 2.1 add方法

add方法，将调用TreeMap的put 方法
- 向TrreMap中添加entry时，value固定为PRESENT
- 如果存在对应的key，put方法返回的oldValue肯定为PRESENT，即不为null
- 所以，只需要判断返回的oldValue是否为null，就可以知道是否存在该元素
```
public boolean add(E e) {
        return m.put(e, PRESENT) == null;
    }
```

2.2 contains方法

判断TreeSet中是否存在某个元素，就是判断TreeMap中是否存在某个对应的key
```
public boolean contains(Object o) {
    return m.containsKey(o);
}
```

2.3 remove方法

从TreeSet中移除一个元素，就是从TreeMap中移除对应的entry
- 返回的oldValue为PRESENT，说明存在key为o的entry，即TreeSet中存在元素o
```
public boolean remove(Object o) {
    return m.remove(o) == PRESENT;
}
```

2.4 iterator方法

遍历TreeSet中的元素，就是遍历TreeMap中的key

因此，直接返回NavigableMap（TreeMap）中key的迭代器即可

public Iterator iterator() {
    return m.navigableKeySet().iterator();
}

3. 总结

TreeSet是基于TreeMap实现的：
- 内部包含NavigableMap接口的成员变量，实际使用时，将初始化为TreeMap
- 元素是有序的：自然顺序、或按照创建时提供的自定义比较器进行进行排序
TreeSet基于红黑树，基本操作的时间复杂度为 O ( l o g 2 n ) O(log2_n) O(log2n)
总之： TreeSet基于TreeMap实现，底层使用红黑树，元素有序，基本操作性能 O ( l o g 2 n ) O(log2_n) O(log2n)

参考文档：

java集合（7）：TreeSet源码分析（jdk1.8）（喜欢那句：TreeSet底层实现严重依赖于TreeMap，所以弄清楚TreeMap是关键。）
Java 集合框架系列十一：JDK 1.8 TreeSet 详解

TreeSet学习（基于JDK1.8）

Java相关栏目本月热门文章