Java Improvement Chapter (28) ------TreeSet-javaTutorial-php.cn

Java Improvement Chapter (28) ------TreeSet

黄舟

Release： 2017-02-11 10:05:16

Original

1615 people have browsed it

Just like HashSet is implemented based on HashMap, TreeSet is also implemented based on TreeMap. In "Java Improvement Chapter (27) -----TreeMap", LZ explained the TreeMap implementation mechanism in detail. If you have read this blog post in detail or have a more detailed understanding of TreeMap, then the implementation of TreeSet will be useful to you. It's as simple as drinking water.

1. TreeSet definition

We know that TreeMap is an ordered binary tree, so similarly TreeSet is also ordered, and its function is to provide an ordered Set collection. Through the source code, we know that TreeSet is based on AbstractSet, which implements NavigableSet, Cloneable, and Serializable interfaces. Among them, AbstractSet provides the backbone implementation of the Set interface, thus minimizing the work required to implement this interface. NavigableSet is an extension of SortedSet with navigation methods that report the closest match for a given search target, which means it supports a range of navigation methods. For example, find the best match for a specified target. Cloneable supports cloning, and Serializable supports serialization.

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

Copy after login

At the same time, the following variables are defined in TreeSet.

private transient NavigableMap<E,Object> m;        
//PRESENT会被当做Map的value与key构建成键值对
 private static final Object PRESENT = new Object();

Copy after login

Its construction method:

//默认构造方法，根据其元素的自然顺序进行排序
    public TreeSet() {        this(new TreeMap<E,Object>());
    }    
    //构造一个包含指定 collection 元素的新 TreeSet，它按照其元素的自然顺序进行排序。
    public TreeSet(Comparator<? super E> comparator) {            this(new TreeMap<>(comparator));
    }    
    //构造一个新的空 TreeSet，它根据指定比较器进行排序。
    public TreeSet(Collection<? extends E> c) {        this();
        addAll(c);
    }    
    //构造一个与指定有序 set 具有相同映射关系和相同排序的新 TreeSet。
    public TreeSet(SortedSet<E> s) {        this(s.comparator());
        addAll(s);
    }
    
    TreeSet(NavigableMap<E,Object> m) {        this.m = m;
    }

Copy after login

2. Main methods of TreeSet

1, add: Add the specified element to this set (if the element does not already exist in the set).

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

Copy after login

2, addAll: Add all elements in the specified collection to this 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<? super E> cc = (Comparator<? super E>) 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);
    }

Copy after login

3, ceiling: Returns the smallest element in this set that is greater than or equal to the given element; if there is no such element, then Return null.

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

Copy after login

4, clear: Remove all elements in this set.

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

Copy after login

5. Clone: Returns a shallow copy of the TreeSet instance. It is a shallow copy.

public Object clone() {
        TreeSet<E> clone = null;        try {
            clone = (TreeSet<E>) super.clone();
        } catch (CloneNotSupportedException e) {            throw new InternalError();
        }

        clone.m = new TreeMap<>(m);        return clone;
    }

Copy after login

6. comparator: Returns a comparator that sorts the elements in this set; returns null if this set uses the natural ordering of its elements.

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

Copy after login

7. contains: If this set contains the specified element, returns true.

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

Copy after login

8、descendingIterator：返回在此 set 元素上按降序进行迭代的迭代器。

public Iterator<E> descendingIterator() {        return m.descendingKeySet().iterator();
    }

Copy after login

9、descendingSet：返回此 set 中所包含元素的逆序视图。

public NavigableSet<E> descendingSet() {        return new TreeSet<>(m.descendingMap());
    }

Copy after login

10、first：返回此 set 中当前第一个（最低）元素。

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

Copy after login

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

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

Copy after login

12、headSet：返回此 set 的部分视图，其元素严格小于 toElement。

public SortedSet<E> headSet(E toElement) {        return headSet(toElement, false);
    }

Copy after login

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

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

Copy after login

14、isEmpty：如果此 set 不包含任何元素，则返回 true。

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

Copy after login

15、iterator：返回在此 set 中的元素上按升序进行迭代的迭代器。

public Iterator<E> iterator() {        return m.navigableKeySet().iterator();
    }

Copy after login

16、last：返回此 set 中当前最后一个（最高）元素。

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

Copy after login

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

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

Copy after login

18、pollFirst：获取并移除第一个（最低）元素；如果此 set 为空，则返回 null。

public E pollFirst() {
        Map.Entry<E,?> e = m.pollFirstEntry();        return (e == null) ? null : e.getKey();
    }

Copy after login

19、pollLast：获取并移除最后一个（最高）元素；如果此 set 为空，则返回 null。

public E pollLast() {
        Map.Entry<E,?> e = m.pollLastEntry();        return (e == null) ? null : e.getKey();
    }

Copy after login

20、remove：将指定的元素从 set 中移除（如果该元素存在于此 set 中）。

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

Copy after login

21、size：返回 set 中的元素数（set 的容量）。

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

Copy after login

22、subSet：返回此 set 的部分视图

/**
     * 返回此 set 的部分视图，其元素范围从 fromElement 到 toElement。     */
     public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
             E toElement,   boolean toInclusive) {             return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                  toElement,   toInclusive));
     }     
     /**
      * 返回此 set 的部分视图，其元素从 fromElement（包括）到 toElement（不包括）。      */
     public SortedSet<E> subSet(E fromElement, E toElement) {         return subSet(fromElement, true, toElement, false);
     }

Copy after login

23、tailSet：返回此 set 的部分视图

/**
     * 返回此 set 的部分视图，其元素大于（或等于，如果 inclusive 为 true）fromElement。     */
    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {        return new TreeSet<>(m.tailMap(fromElement, inclusive));
    }    
    /**
     * 返回此 set 的部分视图，其元素大于等于 fromElement。     */
    public SortedSet<E> tailSet(E fromElement) {        return tailSet(fromElement, true);
    }

Copy after login