java集合框架之TreeSet

starlin 268 2018-05-09

TreeSet介绍

与HashSet是基于HashMap实现一样,TreeSet同样是基于TreeMap实现的,我们知道TreeMap是一个有序的二叉树,那么TreeSet肯定也是一个有序的,它的作用是提供Set集合。

本文源码均为JDK1.8

TreeSet源码分析

定义

TreeSet继承了AbstractSet,实现NavigableSet、Cloneable、Serializable接口,其中AbstractSet提供set接口的骨干实现,NavigableSet继承SortedSet,具有了为给定搜索目标报告最接近匹配项的导航方法,这意味着它支持一系列的导航方法。

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

属性

    /**
     * The backing map.
     */
    // 维护一个NavigableMap型变量,NavigableMap是TreeMap的接口 
    private transient NavigableMap<E,Object> m;

    // Dummy value to associate with an Object in the backing Map
    //PRESENT定义为静态常量,用来填充map的value位置 
    private static final Object PRESENT = new Object();

构造方法

这个构造方法有点意思,还记得HashSet中也有一个构造方法不对外提供么,TreeSet中的这个构造方法也是包权限,不对外提供

    /**
     * Constructs a set backed by the specified navigable map.
     */
    //私有构造方法,不对外提供
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
    
    //默认的空构造方法
    public TreeSet() {
        //调用TreeMap的无参构造
        this(new TreeMap<E,Object>());
    }
    
    //自定义比较器的构造方法
    public TreeSet(Comparator<? super E> comparator) {
        //调用TreeMap类的比较器构造方法
        this(new TreeMap<>(comparator));
    }
    
    //已知集合构造成TreeSet
    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    //已知SortedSet型集合构造成TreeSet
    public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }

方法

add()方法

    /**
     * Adds the specified element to this set if it is not already present.
     * More formally, adds the specified element {@code e} to this set if
     * the set contains no element {@code e2} such that
     * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
     * If this set already contains the element, the call leaves the set
     * unchanged and returns {@code false}.
     *
     * @param e element to be added to this set
     * @return {@code true} if this set did not already contain the specified
     *         element
     * @throws ClassCastException if the specified object cannot be compared
     *         with the elements currently in this set
     * @throws NullPointerException if the specified element is null
     *         and this set uses natural ordering, or its comparator
     *         does not permit null elements
     */
    //若该元素尚未存在于Set中,将指定的元素存入TreeSet 
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

addAll()方法

    /**
     * Adds all of the elements in the specified collection to this set.
     *
     * @param c collection containing elements to be added to this set
     * @return {@code true} if this set changed as a result of the call
     * @throws ClassCastException if the elements provided cannot be compared
     *         with the elements currently in the set
     * @throws NullPointerException if the specified collection is null or
     *         if any element is null and this set uses natural ordering, or
     *         its comparator does not permit null elements
     */
    //添加指定的Collection所有元素添加到这个Set集合中 
    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);
    }

ceiling()方法

该方法的最终实现在NavigableMap的ceilingKey方法
其作用是:返回此 set 中大于或者等于给定元素的最小元素;如果不存在这样的元素,则返回 null。

    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if the specified element is null
     *         and this set uses natural ordering, or its comparator
     *         does not permit null elements
     * @since 1.6
     */
    public E ceiling(E e) {
        return m.ceilingKey(e);
    }

    /**
     * Returns the least key greater than or equal to the given key,
     * or {@code null} if there is no such key.
     *
     * @param key the key
     * @return the least key greater than or equal to {@code key},
     *         or {@code null} if there is no such key
     * @throws ClassCastException if the specified key cannot be compared
     *         with the keys currently in the map
     * @throws NullPointerException if the specified key is null
     *         and this map does not permit null keys
     */
    K ceilingKey(K key);

clear()方法

移除该Set中的所有元素

    /**
     * Removes all of the elements from this set.
     * The set will be empty after this call returns.
     */
    public void clear() {
        m.clear();
    }

clone()方法

返回 TreeSet 实例的浅表副本。属于浅拷贝。

    /**
     * Returns a shallow copy of this {@code TreeSet} instance. (The elements
     * themselves are not cloned.)
     *
     * @return a shallow copy of this set
     */
    @SuppressWarnings("unchecked")
    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()方法

如果此 set 包含指定的元素,则返回 true

    /**
     * Returns {@code true} if this set contains the specified element.
     * More formally, returns {@code true} if and only if this set
     * contains an element {@code e} such that
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
     *
     * @param o object to be checked for containment in this set
     * @return {@code true} if this set contains the specified element
     * @throws ClassCastException if the specified object cannot be compared
     *         with the elements currently in the set
     * @throws NullPointerException if the specified element is null
     *         and this set uses natural ordering, or its comparator
     *         does not permit null elements
     */
    public boolean contains(Object o) {
        return m.containsKey(o);
    }

isEmpty()方法

如果此 set 包含指定的元素,则返回 true。

    /**
     * Returns {@code true} if this set contains no elements.
     *
     * @return {@code true} if this set contains no elements
     */
    public boolean isEmpty() {
        return m.isEmpty();
    }

iterator()方法

返回在此 set 中的元素上按升序进行迭代的迭代器

    /**
     * Returns an iterator over the elements in this set in ascending order.
     *
     * @return an iterator over the elements in this set in ascending order
     */
    public Iterator<E> iterator() {
        return m.navigableKeySet().iterator();
    }

最后

由于TreeSet是基于TreeMap实现的,我们从TreeSet中的源码可以看出,其实现过程非常简单,几乎所有的方法实现全部都是基于TreeMap的。


# java集合