本篇文章给大家带来的内容是关于java中treeset怎么实现？（详解），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。
hashset是基于hashmap实现的，那treeset会是怎么实现的呢？没错！和大家想的一样，它是基于treemap实现的。所以，treeset的源码也很简单，主要还是理解treemap。
treeset的继承关系
按照惯例，先来看treeset类的继承关系：
public class treeset<e> extends abstractset<e>implements navigableset<e>, cloneable, java.io.serializable
毫不意外的继承了抽象类abstracset，方便扩展；
实现了一个navigableset接口，和navigablemap接口类似，提供了各种导航方法；
实现了cloneable接口，可以克隆；
实现了serializable接口，可以序列化；
这里主要看navigableset接口类：
public interface navigableset<e> extends sortedset<e>
熟悉的味道，继承sortedset接口。sortedset则提供了一个返回比较器的方法：
comparator<? super e> comparator();
和sortedmap一样，支持自然排序和自定义排序。自然排序要求添加到set中的元素实现comparable接口，自定义排序要求实现一个comparator比较器。
源码分析
关键点
关键点自然是treeset如何保证元素不重复以及元素有序的，前面说了它是基于treemap实现的，那我们来看看吧。
private transient navigablemap<e,object> m; // 保证有序// dummy value to associate with an object in the backing mapprivate static final object present = new object(); // 固定value
纵观treeset源码，发现只有这两个属性（还有个uid，这里就不算了）。很明显，m是用来保存元素的，但m声明的是navigablemap而不是treemap。可以猜测，treemap应该是在构造方法里实例化的，这里使用navigablemap可以让treeset更加灵活。present和hashset中的present作用一样，作为固定value值进行占位的。
再看add和remove方法：
public boolean add(e e) { return m.put(e, present)==null; }public boolean remove(object o) { return m.remove(o)==present; }
和hashset的实现一样，也是利用了map保存的key-value键值对的key不会重复的特点。
构造函数
果然，treeset中的treemap是在构造函数中初始化的。
public treeset() { this(new treemap<>()); // 默认自然排序的treemap }public treeset(comparator<? super e> comparator) { this(new treemap<>(comparator)); // 自定义比较器的treemap }public treeset(collection<? extends e> c) { this(); // 还是用的默认 addall(c); // 将元素一个一个添加到treemap中 } public treeset(sortedset<e> s) { this(s.comparator()); // 使用传入的sortedset的比较器 addall(s); // 一个一个添加元素 }
默认实例化了一个自然排序的treemap，当然，我们可以自定义比较器。
这里跟踪下addall方法：
public boolean addall(collection<? extends e> c) { // use linear-time version if applicable if (m.size()==0 && c.size() > 0 && c instanceof sortedset && m instanceof treemap) { sortedset<? extends e> set = (sortedset<? extends e>) c; treemap<e,object> map = (treemap<e, object>) m; // 强转成treemap comparator<?> cc = set.comparator(); comparator<? super e> mc = map.comparator(); if (cc==mc || (cc != null && cc.equals(mc))) { // 要保证set和map的比较器一样 map.addallfortreeset(set, present); // treemap专门为treeset准备的方法 return true; } } return super.addall(c); }
调用了treemap的addallfortreeset方法：
void addallfortreeset(sortedset<? extends k> set, v defaultval) { try { buildfromsorted(set.size(), set.iterator(), null, defaultval); } catch (java.io.ioexception | classnotfoundexception cannothappen) { } }
看到buildfromsorted，应该很熟悉，在treemap的文章中分析过。该方法将传入的集合元素构造成了一棵最底层的结点为红色，而其他结点都是黑色的红黑树。
导航方法
既然实现了navigableset，那各种导航方法自然少不了。它们的实现也很简单，直接调用m对应的导航方法即可。例如：
public e first() { return m.firstkey(); // 返回第一个元素 }public e lower(e e) { return m.lowerkey(e); // 返回小于e的第一个元素 }public navigableset<e> headset(e toelement, boolean inclusive) { return new treeset<>(m.headmap(toelement, inclusive)); // 取前几个元素构成子集 }public e pollfirst() { // 弹出第一个元素 map.entry<e,?> e = m.pollfirstentry(); return (e == null) ? null : e.getkey(); }public navigableset<e> descendingset() { // 倒排set return new treeset<>(m.descendingmap()); }......
这里需要注意的是返回子集合的方法，例如：headset。返回的子集合是可以添加和删除元素的，但是有边界限制，举个栗子。
// 前面构造了一个存储int的set // 3、5、7、9 sortedset<integer> subset = intset.headset(8); // 最大值7，超过7越界 for (integer sub : subset) { system.out.println(sub); } subset.add(2);// subset.add(8); // 越界了 subset.remove(3); for (integer sub : subset) { system.out.println(sub); }
treeset也是支持逆序输出的，因为有descendingiterator的实现：
public iterator<e> descendingiterator() { return m.descendingkeyset().iterator(); }
总结
treeset是基于treemap实现的，支持自然排序和自定义排序，可以进行逆序输出；
treeset不允许null值；
treeset不是线程安全的，多线程环境下可以使用sortedset s = collections.synchronizedsortedset(new treeset(...))；
以上就是java中treeset怎么实现？（详解）的详细内容。