TreeSet源码分析.md

简介

TreeSet是一个无序、不重复的集合，无序指的是无法按照插入顺序遍历TreeSet，因为TreeSet会对插入的元素进行排序，默认是自然排序，也可以自定义排序规则。

TreeSet是通过TreeMap实现的，TreeMap的key就是TreeSet不重复的集合，TreeMap的value都指向同一个Object实例，本质上还是通过红黑树实现的。可见TreeMap源码分析

源码

源码也是比较简单

构造方法

    private transient NavigableMap<E,Object> m;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a set backed by the specified navigable map.
     */
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
    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是一个接口，TreeMap实现了它，具有更强的搜索能力。

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

    public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }
    public  boolean addAll(Collection<? extends E> c) {
        // Use linear-time version if applicable
        // c不为空，是SortedSet类型，
        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();
            // 将c插入到红黑树中
            if (cc==mc || (cc != null && cc.equals(mc))) {
                map.addAllForTreeSet(set, PRESENT);
                return true;
            }
        }
        return super.addAll(c);
    }

add方法

基本上所有的功能都是调用TreeMap的方法，所以也没啥说的。

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