TreeSet属于Java集合框架的一部分，是一个有序的集合，本篇重点详解TreeSet的底层结构与原理@mikechen
TreeSet简介
TreeSet是一个包含有序的且没有重复元素的集合，通过TreeMap实现。
TreeSet 是一个具有唯一元素的二叉树的集合，又被翻译为 树集，是 Java 集合框架的一部分，如下图所示：
TreeSet的特点
TreeSet的作用是提供有序的Set集合，主要特点如下：
- 不可以存储重复元素
- 没有索引
- 可以将元素按照规则进行排序
- TreeSet()：根据其元素的自然排序进行排序
- TreeSet(Comparator comparator) ：根据指定的比较器进行排序
TreeSet数据结构
TreeSet 是通过 TreeMap 实现的一个有序的、不可重复的集合，底层维护的是红黑树结构。
红黑树的特点：
- 节点不是黑色，就是红色（非黑即红）；
- 根节点为黑色；
- 叶节点为黑色（叶节点是指末梢的空节点 Nil或Null）；
- 一个节点为红色，则其两个子节点必须是黑色的（根到叶子的所有路径，不可能存在两个连续的红色节点）；
- 每个节点到叶子节点的所有路径，都包含相同数目的黑色节点（相同的黑色高度）。
TreeSet底层原理
1.TreeSet继承关系
TreeSet继承了AbstractSet抽象类，实现了NavigableSet<E>，Cloneable，Serializable接口。
java.lang.Object
↳ java.util.AbstractCollection<E>
↳ java.util.AbstractSet<E>
↳ java.util.TreeSet<E>
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable{}
2.TreeSet构造函数
TreeSet提供了四种构造器：
3.TreeSet成员属性
// NavigableMap对象（NavigableMap下就一个TreeMap实现） private transient NavigableMap<E,Object> m; // 固定常量作为Map值 private static final Object PRESENT = new Object();
4.TreeSet基础方法
// 长度
public int size() {
return m.size();
}
// 是否为空
public boolean isEmpty() {
return m.isEmpty();
}
// 是否存在
public boolean contains(Object o) {
return m.containsKey(o);
}
// 添加
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
// 删除
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
// 清空
public void clear() {
m.clear();
}
TreeSet使用示例
我们可以以任意顺序将元素插入到集合中，在对集合进行遍历时，会返回排序好的值，例如：
import java.util.TreeSet;
public class TreeSetExample {
public static void main(String[] args) {
// 定义一个 String 类型的树集
TreeSet<String> treeset = new TreeSet<String>();
// 添加元素
treeset.add("Learning TreeSet");
treeset.add("Hello, world!");
treeset.add("ABC");
treeset.add("Yuzhou1su");
treeset.add("宇宙之一粟");
for (String ts : treeset) {
System.out.println(ts);
}
}
}
运行结果：
ABC Hello, world! Learning TreeSet Yuzhou1su 宇宙之一粟
TreeSet总结
- 底层是在TreeMap的基础上进行封装，所以结构是红黑树；
- 因为是红黑树结构，所以不需要重写hashCode()和equals()方法来保证唯一性；
- TreeMap有的特性TreeSet都有，还在这个基础上增加了保证元素唯一性的特点。
关于mikechen
mikechen睿哥，10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
关注「mikechen」公众号，获取更多技术干货！
