Java集合源码分析-TreeSet

上篇文章分析完HashSet和LinkedHashSet的源码，我们清楚：HashSet是无序的、不重复的、允许最多一个null，LinkedHashSet是按插入顺序存储的，而这篇文章分析的TreeSet利用二叉排序树可以根据指定的Comparator进行排序，如果不指定Comparator那么就是自然排序(从小到大)。

TreeSet类图

TreeSet类图

和HashSet不同的一点是：HashSet实现了Set，而TreeSet实现了NavigableSet。

TreeSet构造器

TreeSet提供了5个构造器：

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

可以看到，第三个和第五个构造器提供了Comparator，那么会根据Comparator进行排序，其余三个构造器会进行自然排序(从小到大)。而且对TreeSet的所有操作，都是在一个TreeMap的成员变量上进行的。

TreeSet核心操作

TreeSet核心操作包括：

1. add(val:E):boolean
2. remove(ob:Object):boolean
3. clone():Object
4. contains(val:Object):boolean
5. lower(e:E):E
6. higher(e:E):E
7. floor(e:E):E
8. ceiling(e:E):E
9. headSet(e:E, inclusive: boolean):NavigableSet<E>
10. tailSet(e:E, inclusive: boolean):NavigableSet<E>
    TreeSet的核心操作都是操作TreeMap，具体可以分析TreeMap源码。

add(val:E):boolean

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

remove(ob:Object):boolean

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

clone():Object

    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(val:Object):boolean

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

lower(e:E):E

    public E lower(E e) {
        return m.lowerKey(e);
    }

返回此 set 中严格小于给定元素的最大元素；如果不存在这样的元素，则返回null。

higher(e:E):E

    public E higher(E e) {
        return m.higherKey(e);
    }

返回此 set中严格大于给定元素的最小元素；如果不存在这样的元素，则返回null。

floor(e:E):E

    public E floor(E e) {
        return m.floorKey(e);
    }

返回此 set 中小于等于给定元素的最大元素；如果不存在这样的元素，则返回null。

ceiling(e:E):E

    public E ceiling(E e) {
        return m.ceilingKey(e);
    }

返回此 set中大于等于给定元素的最小元素；如果不存在这样的元素，则返回null。

headSet(e:E, inclusive: boolean):NavigableSet<E>

    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        return new TreeSet<>(m.headMap(toElement, inclusive));
    }

返回此 set 的部分视图，其元素小于（或等于，如果inclusive为 true）toElement。

tailSet(e:E, inclusive: boolean):NavigableSet<E>

    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
        return new TreeSet<>(m.tailMap(fromElement, inclusive));
    }

返回此 set 的部分视图，其元素大于（或等于，如果inclusive为 true）toElement。