1 TreeSet
TreeSet是一个有序的Set集合。
既然是有序，那么它是靠什么来维持顺序的呢，TreeMap中是通过一个比较器Comparator比较大小，因此TreeSet要实现比较也必须依靠于Comparator接口。
Map和Set有很大渊源关系，比如Map有HashMap，LinkedHashMap还有TreeMap，Set有HashSet，LinkedHashSet还有TreeSet，很一致是不是。所有的Set的实现都是依靠于Map的，这一点在HashSet中有讲过，重复一边Set的实现是利用Map作为底层存储，主要用到Map的key来存储元素。
TreeSet和TreeMap一样都是基于红黑树实现的
1.1 定义
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
从定义上可以看出TreeSet继承了AbstractSet抽象类，并实现了NavigableSet、Cloneable，Serializable接口，对于NavigableSet，在TreeMap中出现过一个NavigableMap，它们的的目的都一样，都是为了提供跟搜索相关的接口
不过要先看下NavigableSet的接口定义：
public interface NavigableSet<E> extends SortedSet<E> {
E lower(E e);
E floor(E e);
E ceiling(E e);
E higher(E e);
E pollFirst();
E pollLast();
Iterator<E> iterator();
NavigableSet<E> descendingSet();
Iterator<E> descendingIterator();
NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive);
NavigableSet<E> headSet(E toElement, boolean inclusive);
NavigableSet<E> tailSet(E fromElement, boolean inclusive);
SortedSet<E> subSet(E fromElement, E toElement);
SortedSet<E> headSet(E toElement);
SortedSet<E> tailSet(E fromElement);
}
1.2 底层存储和构造方法
// 底层使用NavigableMap来保存TreeSet的元素
private transient NavigableMap<E,Object> m;
// Dummy value to associate with an Object in the backing Map
// 由于Set只使用到了Map的key，所以此处定义一个静态的常量Object类，来充当Map的value
private static final Object PRESENT = new Object();
/**
* 使用指定的navigable map来构造TreeSet
*/
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
/**
* 默认构造方法，底层使用TreeMap来存储TreeSet元素
*/
public TreeSet() {
this(new TreeMap<E,Object>());
}
/**
* 使用指定的构造器，构造一个TreeMap来保存TreeSet的数据
*/
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<E,Object>(comparator));
}
/** * 构造一个指定Collection参数的TreeSet
*/
public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
/** * 构造一个指定SortedMap的TreeSet，根据SortedMap的比较器来来维持TreeSet的顺序
*/
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
TreeSet底层用的是NavigableMap来存储数据，而不是直接使用TreeMap，我们知道TreeMap是实现类NavigableMap接口的，所以TreeSet默认构造了一个TreeMap来作为NavigableMap的一个实现类，提供给TreeSet存储数据
看NavigableMap定义：
public interface NavigableMap<K,V> extends SortedMap<K,V> {
// 获取小于指定key的第一个节点对象
Map.Entry<K,V> lowerEntry(K key);
// 获取小于指定key的第一个key
K lowerKey(K key);
// 获取小于或等于指定key的第一个节点对象
Map.Entry<K,V> floorEntry(K key);
// 获取小于或等于指定key的第一个key
K floorKey(K key);
// 获取大于或等于指定key的第一个节点对象
Map.Entry<K,V> ceilingEntry(K key);
// 获取大于或等于指定key的第一个key
K ceilingKey(K key);
// 获取大于指定key的第一个节点对象
Map.Entry<K,V> higherEntry(K key);
// 获取大于指定key的第一个key
K higherKey(K key);
// 获取Map的第一个（最小的）节点对象
Map.Entry<K,V> firstEntry();
// 获取Map的最后一个（最大的）节点对象
Map.Entry<K,V> lastEntry();
// 获取Map的第一个节点对象，并从Map中移除改节点
Map.Entry<K,V> pollFirstEntry();
// 获取Map的最后一个节点对象，并从Map中移除改节点
Map.Entry<K,V> pollLastEntry();
// 返回当前Map的逆序Map集合
NavigableMap<K,V> descendingMap();
// 返回当前Map中包含的所有key的Set集合
NavigableSet<K> navigableKeySet();
// 返回当前map的逆序Set集合，Set由key组成
NavigableSet<K> descendingKeySet();
// 返回当前map中介于fromKey（fromInclusive是否包含）和toKey（toInclusive是否包含） 之间的子map
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive);
// 返回介于map第一个元素到toKey（inInclusive是否包含）之间的子map
NavigableMap<K,V> headMap(K toKey, boolean inclusive);
// 返回当前map中介于fromKey（inInclusive是否包含） 到map最后一个元素之间的子map
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
// 返回当前map中介于fromKey（包含）和toKey（不包含）之间的子map
SortedMap<K,V> subMap(K fromKey, K toKey);
// 返回介于map第一个元素到toKey（不包含）之间的子map
SortedMap<K,V> headMap(K toKey);
// 返回当前map中介于fromKey（包含） 到map最后一个元素之间的子map
SortedMap<K,V> tailMap(K fromKey);
}
从NavigableMap接口的方法中可以看出，基本上定义的都是一些边界的搜索和查询。当然这些方法是不能实现Set的，再看下NavigableMap的定义，NavigableMap继承了SortedMap接口，而SortedMap继承了Map接口，所以NavigableMap是在Map接口的基础上丰富了这些对于边界查询的方法，但是不妨碍只是用其中Map中自身的功能
1.3 TreeSet的增加和删除
/** * 利用NavigableMap的put方法实现add方法
*/
public boolean add(E e) {
return m .put(e, PRESENT)== null;
}
/**
* 利用NavigableMap的remove方法实现add方法
*/
public boolean remove(Object o) {
return m .remove(o)==PRESENT;
}
/**
* 添加一个集合到TreeSet中
*/ public boolean addAll(Collection<? extends E> c) {
// Use linear-time version if applicable
// 如果集合c是SortedSet的子类，并且m是TreeMap的子类，则用下面的方法添加（主要为了检查是否需要重新排序）
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;
// 取出集合c的比较器
Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
// 取出当前set的比较器
Comparator<? super E> mc = map.comparator();
// 如果上面的两种比较器是同一个的话（==或equals），当然TreeSet和TreeMap默认构造方法比较器都是null，这里也是==的
if (cc==mc || (cc != null && cc.equals(mc))) {
// 将集合c在当前set集合顺序的基础上，按顺序插入
map.addAllForTreeSet(set, PRESENT);
return true;
}
}
// 不需要排序的话就按普通方法，调用父类AbstractCollection的addAll方法（将集合c添加到Set尾部）
return super.addAll(c);
}
/** * 添加一个集合到TreeSet中
*/
public boolean removeAll(Collection<?> c) {
boolean modified = false;
// 判断当前TreeSet元素个数和指定集合c的元素个数，目的是减少遍历次数
if (size() > c.size()) {
// 如果当前TreeSet元素多，则遍历集合c，将集合c中的元素一个个删除
for (Iterator<?> i = c.iterator(); i.hasNext(); )
modified |= remove(i.next());
} else {
// 如果集合c元素多，则遍历当前TreeSet，将集合c中包含的元素一个个删除
for (Iterator<?> i = iterator(); i.hasNext(); ) {
if (c.contains(i.next())) {
i.remove();
modified = true;
}
}
}
return modified;
}
1.4 是否包含
/** * 利用TreeMap的containsKey方法实现contains方法
*/
public boolean contains(Object o) {
return m .containsKey(o);
}
/**
* 检查是否包含指定集合中所有元素，该方法在AbstractCollection中
*/
public boolean containsAll(Collection<?> c) {
// 取得集合c的迭代器Iterator
Iterator<?> e = c.iterator();
// 遍历迭代器，只要集合c中有一个元素不属于当前HashSet，则返回false
while (e.hasNext())
if (!contains(e.next()))
return false;
return true;
}
1.5 容量检查
/**
* Returns the number of elements in this set (its cardinality).
*
* @return the number of elements in this set (its cardinality)
*/
public int size() {
return map .size();
}
/**
* Returns <tt>true</tt> if this set contains no elements.
*
* @return <tt> true</tt> if this set contains no elements
*/
public boolean isEmpty() {
return map .isEmpty();
}
可以看到由于TreeSet底层基于TreeMap（默认情况下）实现，在代码层面上来看是非常简单的，但是如果想要透彻的明白TreeSet底层存储及其操作，还是要了解TreeMap底层红黑树的原理
1.6 NavigableSet&NavigableMap
如果没想错的话，TreeSet实现于NavigableSet的一些边界搜索方法也是基于NavigableMap实现的，随便拿两个方法实现来看一下：
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();
}
果然没有猜错，这些方法还是基于NavigableMap实现的，要明白其具体实现代码，来看看TreeMap中是怎么实现NavigableMap接口中这些方法的
public Map.Entry<K,V> pollFirstEntry() {
// 取得当前Map第一个节点
Entry<K,V> p = getFirstEntry();
// 返回一个只包含key、value的简单Entry对象，exportEntry不必深究也很简单
Map.Entry<K,V> result = exportEntry(p);
// 如果节点不为空，将节点删除
if (p != null)
deleteEntry(p);
return result;
}
public Map.Entry<K,V> pollLastEntry() {
// 取得当前Map第一个节点
Entry<K,V> p = getLastEntry();
// 返回一个只包含key、value的简单Entry对象，exportEntry不必深究也很简单
Map.Entry<K,V> result = exportEntry(p);
// 如果节点不为空，将节点删除
if (p != null)
deleteEntry(p);
return result;
}
/** * Returns the first Entry in the TreeMap (according to the TreeMap's
* key -sort function). Returns null if the TreeMap is empty.
*/
final Entry<K,V> getFirstEntry() {
// 取得根节点
Entry<K,V> p = root;
if (p != null)
// 循环取根节点的left，直到取到最左边的一个节点，也就是取得最小值（红黑树原则最左边最小）
while (p.left != null)
p = p. left;
return p;
}
/** * Returns the last Entry in the TreeMap (according to the TreeMap's
* key -sort function). Returns null if the TreeMap is empty.
*/
final Entry<K,V> getLastEntry() {
// 取得根节点
Entry<K,V> p = root;
if (p != null)
// 循环取根节点的right，直到取到最右边的一个节点，也就是取得最大值（红黑树原则最右边最大）
while (p.right != null)
p = p. right;
return p;
}
在明白了红黑树的原则之后，这几个取第一个和最后一个的方法看起来还是很简单的，我们再来看下其他方法的实现：
public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive) {
// key越界检查，key怎么越界呢，当然是因为TreMap已经对key排序了，不细看
if (!inRange(fromKey, fromInclusive))
throw new IllegalArgumentException( "fromKey out of range" );
if (!inRange(toKey, toInclusive))
throw new IllegalArgumentException( "toKey out of range" );
// 返回AscendingSubMap对象
return new AscendingSubMap(m,
false, fromKey, fromInclusive,
false, toKey, toInclusive);
}
AscendingSubMap是NavigableSubMap子类，该构造方法直接调用NavigableSubMap，继续看：
static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, java.io.Serializable {
/**
* The backing map.
*/
final TreeMap<K,V> m; // 底层使用原始TreeMap提供数据操作
final K lo, hi;
final boolean fromStart, toEnd;
final boolean loInclusive, hiInclusive;
NavigableSubMap(TreeMap<K,V> m,
boolean fromStart, K lo, boolean loInclusive,
boolean toEnd, K hi, boolean hiInclusive) {
if (!fromStart && !toEnd) {
if (m.compare(lo, hi) > 0)
throw new IllegalArgumentException( "fromKey > toKey" );
} else {
if (!fromStart) // type check
m.compare(lo, lo);
if (!toEnd)
m.compare(hi, hi);
}
// 记录边界
this.m = m;
this.fromStart = fromStart;
this.lo = lo;
this.loInclusive = loInclusive;
this.toEnd = toEnd;
this.hi = hi;
this.hiInclusive = hiInclusive;
}
... ...
... ...
public final V put(K key, V value) {
// 边界检查，如果不在边界范围内，则抛出异常
if (!inRange(key))
throw new IllegalArgumentException( "key out of range" );
return m .put(key, value);
}
public final V get(Object key) {
return !inRange(key)? null : m.get(key);
}
}
上面的代码比较乱，这里总结一下，subMap这个方法要求返回一个介于fromKey、toKey范围内的字Map。在TreeMap的实现中，是靠一个内部Map的子类NavigableSubMap ，这个类将记录fromKey、toKey等，将这个子Map返回后，在操作这个子Map的put、get等操作的时候，都会检查是否在之前的限定内，如果是在限定内则抛出异常，也就是说实际上并不是对原Map的切割负责，底层继续使用原Map，只是给原Map加一个限定条件。
想一想这样做的好处，如果是新创建一个子Map来存限定内的元素，或者复制原Map切割掉限定外的元素，这样的新创建都会在堆内存中申请一份内存空间；而TreeMap这样做，只是在一个类中加了一个指针指向原先的Map，这个指针只分配在栈空间，占用很小的一块内存，这样是不是节省内存空间了呢，虽然其他操作要先检查边界效率会低一些。其实这在设计模式上就叫做代理，实际上NavigableSubMap是TreeMap的一个静态代理类。但是这样存在的一个问题是什么呢，原Map和NavigableSubMap指向的是一块内存，当对NavigableSubMap进行添加、删除等修改操作的时候，实际上原Map也已经变化了。
网友评论