TreeSet源码分析

简介

基于TreeMap的NavigableSet实现。 元素使用自然排序进行排序，或通过在集合创建时提供的Comparator进行排序，具体取决于所使用的构造函数。此实现保证在log（n）时间成本add ， remove和contains 。

类图

属性

	-- 基于map来实现
    private transient NavigableMap<E,Object> m;
    -- 因为是基于map的实现 value值要是用这个
    private static final Object PRESENT = new Object();

构造方法

-- 内部实现依赖TreeMap
public TreeSet() {
    this(new TreeMap<E,Object>());
}
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}
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);
}

方法

-- 方法都是调用TreeMap的方法实现
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();
}
public boolean contains(Object o) {
    return m.containsKey(o);
}
public boolean isEmpty() {
    return m.isEmpty();
}
public int size() {
    return m.size();
}
public Iterator<E> iterator() {
    return m.navigableKeySet().iterator();
}
-- 实现了一些导航方法
public E first() {
    return m.firstKey();
}
public E lower(E e) {
    return m.lowerKey(e);
}
-- 重写实现深拷贝
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;
}

总结

内部使用NavigableMap实现，大部分时间是TreeMap
有序
非线程安全