集合系列 Set（八）：TreeSet

TreeSet 是 Set 集合的红黑树实现，但其内部并没有具体的逻辑，而是直接使用 TreeMap 对象实现。我们先来看看 TreeSet 的定义。

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

可以看到 TreeSet 实现了 NavigableSet 接口，而 NavigableSet 接口又继承了接口。SortedSet 接口又继承了 Set 接口。

public interface NavigableSet<E> extends SortedSet<E>

public interface SortedSet<E> extends Set<E>

TreeSet 的类继承关系如下图所示。

原理

我们还是通过类成员变量、构造方法、核心方法来解析 TreeSet 的实现。

类成员变量

// 具体的实现类
private transient NavigableMap<E,Object> m;
// Map的value
private static final Object PRESENT = new Object();

构造方法

TreeSet 一共有 5 个构造方法，如下所示：

// 默认采用TreeMap实现
public TreeSet() {
    this(new TreeMap<E,Object>());
}
// 指定实现类型
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}
// 指定TreeMap的比较器
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}
// 指定初始集合
public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}
// 指定比较器以及初始集合
public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

可以看到，如果我们没有指定传入的 Map 类型，TreeSet 将自动采用 TreeMap 来实现。而如果你传入了 NavigableMap 类型的对象，那么就按照你传入的对象类型来实现。

核心方法

TreeSet 的核心方法实现直接采用了 TreeMap 的实现，无论是 add 还是 remove 方法。

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}
    
public boolean remove(Object o) {
    return m.remove(o)==PRESENT;
}

总结

TreeSet 的实现与 HashSet 类似，都是直接采用了 TreeMap 的方法实现。所以如果理解了 TreeMap，那么 TreeSet 就很简单了。

FEATURED TAGS

性能优化单测事务 Spring 性能调优 Tomcat MySQL 系统设计稳定性建设 synchronized 并发编程 Java内存模型思维误区认知成长简历爬虫 Github 邮件经济学书籍推荐年度总结个税排序算法程序员架构师软件工程操作系统阻塞队列源码系列推送基础系列 JVM 规范系列 Prometheus 入门系列集合源码系列 JVM 基础系列并发集合源码系列并发包源码系列线程池源码系列 JVM实战 Apache Common Pool 树结构数据结构中年危机教员 Redis HBase 有赞 Chrome 技术管理美团建站 Kafka 法律 Prometheus 商业哲学时间管理 Markdown 面试华为 Maven 区块链源码雷军小米线上问题管理方法论数据库 Push JVM Alfred 架构设计计算机原理 MongoDb 职业规划运维重构设计模式 LOG4J ImageMagick 计算机网络入门教程毛主席 Java Canal ElasticSearch Linux Shell

FRIENDS

田小波的博客

原理

类成员变量

构造方法

核心方法

总结

目录

FEATURED TAGS

FRIENDS