开篇
TreeSet作为HashSet的姊妹类型，TreeSet是用来排序的, 可以指定一个顺序, 对象存入之后会按照指定的顺序排列。
TreeSet类图
TreeSet类图
TreeSet类图
TreeSet秉承了HashSet的一贯做法，内部通过Map来保存key/value数据，由于Set只保存key，所以内部的Map的value公用了一个定义的Object对象PRESENT。
TreeSet由于维持有序性，所以内部通过TreeMap存储数据。
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
// 用于保存TreeMap的对象，会在构造函数当中赋值TreeMap对象
private transient NavigableMap<E,Object> m;
// TreeMap当中所有的value都是保存的PRESENT对象
private static final Object PRESENT = new Object();
}
TreeSet的构造函数
TreeSet的构造函数分为两大类：
- 通过创建TreeMap对象赋值给TreeSet当中NavigableMap<E,Object> m变量；
- 通过创建NavigableMap<E,Object> m变量并通过addAll方法方法添加到TreeMap当中。
- 在TreeSet的addAll()方法通过super.addAll()方法调用AbstractCollection的addAll()方法，在该方法内部最后又调用TreeSet的add()方法添加到TreeMap m当中。
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet() {
this(new TreeMap<E,Object>());
}
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);
}
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;
Comparator<?> cc = set.comparator();
Comparator<? super E> mc = map.comparator();
if (cc==mc || (cc != null && cc.equals(mc))) {
map.addAllForTreeSet(set, PRESENT);
return true;
}
}
return super.addAll(c);
}
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
----------AbstractCollection.java中代码-----------
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
for (E e : c)
if (add(e))
modified = true;
return modified;
}
TreeSe常用操作
TreeSet常用的操作其实都是针对TreeMap进行的操作，这里就不再多做啰嗦了，基本上都是TreeMap对外提供的api而已。
private transient NavigableMap<E,Object> m;
public E first() {
return m.firstKey();
}
public E last() {
return m.lastKey();
}
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();
}
TreeSet迭代器
TreeSet的iterator本质也是TreeMap当中实现的，在TreeMap.java中的navigableKeySet()方法中创建KeySet类对象，在KeySet类iterator方法当中我们可以看出来其实就是应用了TreeMap的keyIterator()方法。
这里再一次印证了TreeSet只是使用了TreeMap的key而已。
public Iterator<E> iterator() {
return m.navigableKeySet().iterator();
}
----------------TreeMap.java------------------------
public NavigableSet<K> navigableKeySet() {
KeySet<K> nks = navigableKeySet;
return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
}
static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
private final NavigableMap<E, ?> m;
KeySet(NavigableMap<E,?> map) { m = map; }
public Iterator<E> iterator() {
if (m instanceof TreeMap)
return ((TreeMap<E,?>)m).keyIterator();
else
return ((TreeMap.NavigableSubMap<E,?>)m).keyIterator();
}
