Set（二）：TreeSet源码浅析

TreeSet

TreeSet是一个有序的集合，它的作用是提供有序的Set集合。它继承了AbstractSet抽象类，实现了NavigableSet<E>，Cloneable，Serializable接口。TreeSet是基于TreeMap实现的，TreeSet的元素支持2种排序方式：自然排序或者根据提供的Comparator进行排序

private transient NavigableMap<E,Object> m;

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

// 创建一个默认的TreeMap并赋值给m
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
    // 创建一个带自定义排序方式的TreeMap并赋值给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);
    }

NavigableMap继承于SortedMap,同时本身也是TreeMap的父类,所以第二三个构造方法创建的TreeMap对象赋值给了m

TreeSet重写addAll()

TreeSet#addAll()

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

判断体的判断条件注意的是c instanceof SortedSet,并且只有在新创建TreeSet或TreeSet元素为空的时候的时候才会进入这个判断,其他时候是进不来的;TreeSet本身继承于SortedSet,所以此时的c等同于一个TreeSet对象,然后分别获取到传入的集合和TreeSet本身维护的TreeMap中的比较器Comparator,如果两个比较器相等,则直接将传入的set对象通过addAllForTreeSet添加到TreeMap中
TreeMap维护着一颗红黑树,最后会将传入的set集合加入到红黑树中,具体的加入方法,会在Map<一>：TreeMap源码浅析一节中提到
如果进入不到判断体,则最终调用TreeSet的add(),将元素添加到集合中,其他的f方法则都在TreeMap中实现