Set集合之TreeSet

定义

public class TreeSet<E> extends AbstractSet<E>implements NavigableSet<E>, Cloneable, java.io.Serializable

继承自AbstractSet

实现了NavigableSet，排序集合

实现了Cloneable，可以对象克隆

实现了Serializable，可以序列化

成员变量

private transient NavigableMap<E,Object> m;

TreeSet底层实际存储数据的地方。结合构造器TreeSet(NavigbleMap<E,Object> m) 来看，这里的m就是TreeMap实例。

所以TreeSet的底层就是TreeMap。

private static final Object PRESENT = new Object();

由于TreeSet底层是TreeMap，而TreeSet中元素就相当于TreeMap中的key列数据，而TreeMap的value列数据全部指定为固定的PRESENT。

构造器

TreeSet(NavigableMap<E,Object> m)

TreeSet(NavigableMap<E,Object> m) {this.m = m;
}

该构造器用于给成员变量m初始化。 

public TreeSet()

public TreeSet() {this(new TreeMap<E,Object>());
}

无参构造器，默认底层TreeMap是使用自然排序的，所以加入该TreeSet集合的元素类型必须实现Compareble接口， 重写compareTo方法

public TreeSet(Comparator<? super E> comparator)

public TreeSet(Comparator<? super E> comparator) {this(new TreeMap<>(comparator));
}

指定比较器的构造器。底层TreeMap也使用指定的比较器。 

public TreeSet(Collection<? extends E> c)

public TreeSet(Collection<? extends E> c) {this();addAll(c);
}

将其他单列集合转化为TreeSet集合。内部调用addAll方法。

注意该构造器得到的TreeSet实例的底层TreeMap是使用自然排序的，所以需要c集合元素类型实现Compareble接口，重写compareTo方法。 

public TreeSet(SortedSet<E> s)

​​​​​​​public TreeSet(SortedSet<E> s) {this(s.comparator());addAll(s);
}

将其他有序Set集合转变为TreeSet。内部调用addAll方法。

注意该构造器得到的TreeSet实例的底层TreeMap使用有序Set集合的比较器。 

成员方法

public boolean add(E e)

    public boolean add(E e) {return m.put(e, PRESENT)==null;}

内部调用TreeMap的put方法，其中TreeSet集合元素对应TreeMap的key列数据，TreeMap的value列数据固定为PRESENT。

TreeMap的put方法返回值

当返回null时，表示插入成功。

当返回不为null时，表示覆盖oldValue成功，并返回oldValue。

public  boolean addAll(Collection<? extends E> c)

    public  boolean addAll(Collection<? extends E> c) {// Use linear-time version if applicableif (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);}

将Colletion集合中所有元素加入到TreeSet集合中

public boolean remove(Object o)

    public boolean remove(Object o) {return m.remove(o)==PRESENT;}

 TreeSet的remove方法调用了TreeMap的remove方法

而TreeMap的remove方法删除成功的话，会返回被删除键值对的value，而来自TreeSet插入的键值对的value都是PRESENT,所以删除成功的话，都会返回PRESENT。

即当m.remove(o)删除成功时，返回值和PRESENT相等，即return ture

public int size()

    public int size() {return m.size();}

TreeSet本身没有size属性，TreeSet的size()方法返回的时底层TreeMap的size()返回值

public boolean contains(Object o)

    public boolean contains(Object o) {return m.containsKey(o);}

TreeSet包含某个元素，即等同于TreeMap包含某个Key

 public void clear()

    public void clear() {m.clear();}

TreeSet清空集合元素，即等同于底层TreeMap清空键值对

public boolean isEmpty()

    public boolean isEmpty() {return m.isEmpty();}

TreeSet判空，即等同于底层TreeMap判空

public Comparator<? super E> comparator()

    public Comparator<? super E> comparator() {return m.comparator();}

获取比较器

public E first()

    public E first() {return m.firstKey();}

获取TreeSet第一个元素 ，即底层TreeMap红黑树结构中最左边节点

public E last()

    public E last() {return m.lastKey();}

获取TreeSet最后一个元素 ，即底层TreeMap红黑树结构中最右边节点

public Object clone()

    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;}

TreeSet的对象克隆属于浅克隆，因为没有对集合元素进行克隆。