TreeSet介绍
与HashSet是基于HashMap实现一样，TreeSet同样是基于TreeMap实现的，我们知道TreeMap是一个有序的二叉树，那么TreeSet肯定也是一个有序的，它的作用是提供Set集合。
本文源码均为JDK1.8
TreeSet源码分析
定义
TreeSet继承了AbstractSet，实现NavigableSet、Cloneable、Serializable接口，其中AbstractSet提供set接口的骨干实现，NavigableSet继承SortedSet，具有了为给定搜索目标报告最接近匹配项的导航方法，这意味着它支持一系列的导航方法。
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
属性
/**
* The backing map.
*/
// 维护一个NavigableMap型变量，NavigableMap是TreeMap的接口
private transient NavigableMap<E,Object> m;
// Dummy value to associate with an Object in the backing Map
//PRESENT定义为静态常量，用来填充map的value位置
private static final Object PRESENT = new Object();
构造方法
这个构造方法有点意思，还记得HashSet中也有一个构造方法不对外提供么，TreeSet中的这个构造方法也是包权限，不对外提供
/**
* Constructs a set backed by the specified navigable map.
*/
//私有构造方法，不对外提供
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
//默认的空构造方法
public TreeSet() {
//调用TreeMap的无参构造
this(new TreeMap<E,Object>());
}
//自定义比较器的构造方法
public TreeSet(Comparator<? super E> comparator) {
//调用TreeMap类的比较器构造方法
this(new TreeMap<>(comparator));
}
//已知集合构造成TreeSet
public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
//已知SortedSet型集合构造成TreeSet
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
方法
add()方法
/**
* Adds the specified element to this set if it is not already present.
* More formally, adds the specified element {@code e} to this set if
* the set contains no element {@code e2} such that
* <tt>(e==null ? e2==null : e.equals(e2))</tt>.
* If this set already contains the element, the call leaves the set
* unchanged and returns {@code false}.
*
* @param e element to be added to this set
* @return {@code true} if this set did not already contain the specified
* element
* @throws ClassCastException if the specified object cannot be compared
* with the elements currently in this set
* @throws NullPointerException if the specified element is null
* and this set uses natural ordering, or its comparator
* does not permit null elements
*/
//若该元素尚未存在于Set中，将指定的元素存入TreeSet
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
addAll()方法
/**
* Adds all of the elements in the specified collection to this set.
*
* @param c collection containing elements to be added to this set
* @return {@code true} if this set changed as a result of the call
* @throws ClassCastException if the elements provided cannot be compared
* with the elements currently in the set
* @throws NullPointerException if the specified collection is null or
* if any element is null and this set uses natural ordering, or
* its comparator does not permit null elements
*/
//添加指定的Collection所有元素添加到这个Set集合中
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);
}
ceiling()方法
该方法的最终实现在NavigableMap的ceilingKey方法
其作用是：返回此 set 中大于或者等于给定元素的最小元素；如果不存在这样的元素，则返回 null。
/**
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException if the specified element is null
* and this set uses natural ordering, or its comparator
* does not permit null elements
* @since 1.6
*/
public E ceiling(E e) {
return m.ceilingKey(e);
}
/**
* Returns the least key greater than or equal to the given key,
* or {@code null} if there is no such key.
*
* @param key the key
* @return the least key greater than or equal to {@code key},
* or {@code null} if there is no such key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map does not permit null keys
*/
K ceilingKey(K key);
clear()方法
移除该Set中的所有元素
/**
* Removes all of the elements from this set.
* The set will be empty after this call returns.
*/
public void clear() {
m.clear();
}
clone()方法
返回 TreeSet 实例的浅表副本。属于浅拷贝。
/**
* Returns a shallow copy of this {@code TreeSet} instance. (The elements
* themselves are not cloned.)
*
* @return a shallow copy of this set
*/
@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;
}
contains()方法
如果此 set 包含指定的元素，则返回 true
/**
* Returns {@code true} if this set contains the specified element.
* More formally, returns {@code true} if and only if this set
* contains an element {@code e} such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o object to be checked for containment in this set
* @return {@code true} if this set contains the specified element
* @throws ClassCastException if the specified object cannot be compared
* with the elements currently in the set
* @throws NullPointerException if the specified element is null
* and this set uses natural ordering, or its comparator
* does not permit null elements
*/
public boolean contains(Object o) {
return m.containsKey(o);
}
isEmpty()方法
如果此 set 包含指定的元素，则返回 true。
/**
* Returns {@code true} if this set contains no elements.
*
* @return {@code true} if this set contains no elements
*/
public boolean isEmpty() {
return m.isEmpty();
}
iterator()方法
返回在此 set 中的元素上按升序进行迭代的迭代器
/**
* Returns an iterator over the elements in this set in ascending order.
*
* @return an iterator over the elements in this set in ascending order
*/
public Iterator<E> iterator() {
return m.navigableKeySet().iterator();
}
最后
由于TreeSet是基于TreeMap实现的，我们从TreeSet中的源码可以看出，其实现过程非常简单，几乎所有的方法实现全部都是基于TreeMap的。