共计 5639 个字符，预计需要花费 15 分钟才能阅读完成。
问题
（1）TreeSet 真的是使用 TreeMap 来存储元素的吗？
（2）TreeSet 是有序的吗？
（3）TreeSet 和 LinkedHashSet 有何不同？
简介
TreeSet 底层是采用 TreeMap 实现的一种 Set，所以它是有序的，同样也是非线程安全的。
源码分析
经过前面我们学习 HashSet 和 LinkedHashSet，基本上已经掌握了 Set 实现的套路了。
所以，也不废话了，直接上源码：
package java.util;
// TreeSet 实现了 NavigableSet 接口，所以它是有序的
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
// 元素存储在 NavigableMap 中
// 注意它不一定就是 TreeMap
private transient NavigableMap<E,Object> m;
// 虚拟元素, 用来作为 value 存储在 map 中
private static final Object PRESENT = new Object();
// 直接使用传进来的 NavigableMap 存储元素
// 这里不是深拷贝, 如果外面的 map 有增删元素也会反映到这里
// 而且, 这个方法不是 public 的, 说明只能给同包使用
TreeSet(NavigableMap<E,Object> m) {this.m = m;}
// 使用 TreeMap 初始化
public TreeSet() {this(new TreeMap<E,Object>());
}
// 使用带 comparator 的 TreeMap 初始化
public TreeSet(Comparator<? super E> comparator) {this(new TreeMap<>(comparator));
}
// 将集合 c 中的所有元素添加的 TreeSet 中
public TreeSet(Collection<? extends E> c) {this();
addAll(c);
}
// 将 SortedSet 中的所有元素添加到 TreeSet 中
public TreeSet(SortedSet<E> s) {this(s.comparator());
addAll(s);
}
// 迭代器
public Iterator<E> iterator() {return m.navigableKeySet().iterator();}
// 逆序迭代器
public Iterator<E> descendingIterator() {return m.descendingKeySet().iterator();}
// 以逆序返回一个新的 TreeSet
public NavigableSet<E> descendingSet() {return new TreeSet<>(m.descendingMap());
}
// 元素个数
public int size() {return m.size();
}
// 判断是否为空【本篇文章由公众号“彤哥读源码”原创】public boolean isEmpty() {return m.isEmpty();
}
// 判断是否包含某元素
public boolean contains(Object o) {return m.containsKey(o);
}
// 添加元素, 调用 map 的 put() 方法, value 为 PRESENT
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();
}
// 添加集合 c 中的所有元素
public boolean addAll(Collection<? extends E> c) {// 满足一定条件时直接调用 TreeMap 的 addAllForTreeSet() 方法添加元素
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;
Comparator<?> cc = set.comparator();
Comparator<? super E> mc = map.comparator();
if (cc==mc || (cc != null && cc.equals(mc))) {map.addAllForTreeSet(set, PRESENT);
return true;
}
}
// 不满足上述条件, 调用父类的 addAll() 通过遍历的方式一个一个地添加元素
return super.addAll(c);
}
// 子 set（NavigableSet 中的方法）public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive) {
return new TreeSet<>(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
}
// 头 set（NavigableSet 中的方法）public NavigableSet<E> headSet(E toElement, boolean inclusive) {return new TreeSet<>(m.headMap(toElement, inclusive));
}
// 尾 set（NavigableSet 中的方法）public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {return new TreeSet<>(m.tailMap(fromElement, inclusive));
}
// 子 set（SortedSet 接口中的方法）public SortedSet<E> subSet(E fromElement, E toElement) {return subSet(fromElement, true, toElement, false);
}
// 头 set（SortedSet 接口中的方法）public SortedSet<E> headSet(E toElement) {return headSet(toElement, false);
}
// 尾 set（SortedSet 接口中的方法）public SortedSet<E> tailSet(E fromElement) {return tailSet(fromElement, true);
}
// 比较器
public Comparator<? super E> comparator() {return m.comparator();
}
// 返回最小的元素
public E first() {return m.firstKey();
}
// 返回最大的元素
public E last() {return m.lastKey();
}
// 返回小于 e 的最大的元素
public E lower(E e) {return m.lowerKey(e);
}
// 返回小于等于 e 的最大的元素
public E floor(E e) {return m.floorKey(e);
}
// 返回大于等于 e 的最小的元素
public E ceiling(E e) {return m.ceilingKey(e);
}
// 返回大于 e 的最小的元素
public E higher(E e) {return m.higherKey(e);
}
// 弹出最小的元素
public E pollFirst() {Map.Entry<E,?> e = m.pollFirstEntry();
return (e == null) ? null : e.getKey();}
public E pollLast() {Map.Entry<E,?> e = m.pollLastEntry();
return (e == null) ? null : e.getKey();}
// 克隆方法
@SuppressWarnings("unchecked")
public Object clone() {
TreeSet<E> clone;
try {clone = (TreeSet<E>) super.clone();} catch (CloneNotSupportedException e) {throw new InternalError(e);
}
clone.m = new TreeMap<>(m);
return clone;
}
// 序列化写出方法【本篇文章由公众号“彤哥读源码”原创】private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden stuff
s.defaultWriteObject();
// Write out Comparator
s.writeObject(m.comparator());
// Write out size
s.writeInt(m.size());
// Write out all elements in the proper order.
for (E e : m.keySet())
s.writeObject(e);
}
// 序列化写入方法
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden stuff
s.defaultReadObject();
// Read in Comparator
@SuppressWarnings("unchecked")
Comparator<? super E> c = (Comparator<? super E>) s.readObject();
// Create backing TreeMap
TreeMap<E,Object> tm = new TreeMap<>(c);
m = tm;
// Read in size
int size = s.readInt();
tm.readTreeSet(size, s, PRESENT);
}
// 可分割的迭代器
public Spliterator<E> spliterator() {return TreeMap.keySpliteratorFor(m);
}
// 序列化 id
private static final long serialVersionUID = -2479143000061671589L;
}源码比较简单，基本都是调用 map 相应的方法。
总结
（1）TreeSet 底层使用 NavigableMap 存储元素；
（2）TreeSet 是有序的【本篇文章由公众号“彤哥读源码”原创】；
（3）TreeSet 是非线程安全的；
（4）TreeSet 实现了 NavigableSet 接口，而 NavigableSet 继承自 SortedSet 接口；
（5）TreeSet 实现了 SortedSet 接口；（彤哥年轻的时候面试被问过 TreeSet 和 SortedSet 的区别 ^^）
彩蛋
（1）通过之前的学习，我们知道 TreeSet 和 LinkedHashSet 都是有序的，那它们有何不同？
LinkedHashSet 并没有实现 SortedSet 接口，它的有序性主要依赖于 LinkedHashMap 的有序性，所以它的有序性是指按照插入顺序保证的有序性；
而 TreeSet 实现了 SortedSet 接口，它的有序性主要依赖于 NavigableMap 的有序性，而 NavigableMap 又继承自 SortedMap，这个接口的有序性是指按照 key 的自然排序保证的有序性，而 key 的自然排序又有两种实现方式，一种是 key 实现 Comparable 接口，一种是构造方法传入 Comparator 比较器。
（2）TreeSet 里面真的是使用 TreeMap 来存储元素的吗？
通过源码分析我们知道 TreeSet 里面实际上是使用的 NavigableMap 来存储元素，虽然大部分时候这个 map 确实是 TreeMap，但不是所有时候都是 TreeMap。
因为有一个构造方法是 TreeSet(NavigableMap<E,Object> m)，而且这是一个非 public 方法，通过调用关系我们可以发现这个构造方法都是在自己类中使用的，比如下面这个：
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {return new TreeSet<>(m.tailMap(fromElement, inclusive));
}而这个 m 我们姑且认为它是 TreeMap，也就是调用 TreeMap 的 tailMap() 方法：
public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
return new AscendingSubMap<>(this,
false, fromKey, inclusive,
true, null, true);
}可以看到，返回的是 AscendingSubMap 对象，这个类的继承链是怎么样的呢？
可以看到，这个类并没有继承 TreeMap，不过通过源码分析也可以看出来这个类是组合了 TreeMap，也算和 TreeMap 有点关系，只是不是继承关系。
所以，TreeSet 的底层不完全是使用 TreeMap 来实现的，更准确地说，应该是 NavigableMap。
欢迎关注我的公众号“彤哥读源码”，查看更多源码系列文章, 与彤哥一起畅游源码的海洋。
