SortedSet

概述

A {@link Set} that further provides a <i>total ordering</i> on its elements.
The elements are ordered using their {@linkplain Comparable natural ordering}, or by a {@link Comparator} typically provided at sorted set creation time.
The set's iterator will traverse the set in ascending element order.
Several additional operations are provided to take advantage of the ordering. (This interface is the set analogue of {@link SortedMap}.)

SortedSet支持元素排序；

SortedSet排序 使用元素的Comparable自然排序 或 创建时的Comparator；

Comparator的iterator将升序遍历；

All elements inserted into a sorted set must implement the <tt>Comparable</tt> interface (or be accepted by the specified comparator).
Furthermore, all such elements must be <i>mutually comparable</i>: <tt>e1.compareTo(e2)</tt> (or <tt>comparator.compare(e1, e2)</tt>) must not throw a <tt>ClassCastException</tt> for any elements <tt>e1</tt> and <tt>e2</tt> in the sorted set.
Attempts to violate this restriction will cause the offending method or constructor invocation to throw a <tt>ClassCastException</tt>.

SortedSet的所有元素 必须实现Comparable接口（或创建时指定comparator）；

SortedSet的所有元素必须是可比较的；

Note that the ordering maintained by a sorted set (whether or not an explicit comparator is provided) must be <i>consistent with equals</i> if the sorted set is to correctly implement the <tt>Set</tt> interface.
This is so because the <tt>Set</tt> interface is defined in terms of the <tt>equals</tt> operation, but a sorted set performs all element comparisons using its <tt>compareTo</tt> (or <tt>compare</tt>) method, so two elements that are deemed equal by this method are, from the standpoint of the sorted set, equal.

实现Set接口的SortedSet的排序必须与equals一致；

因为Set使用equals比较，SortedSet使用Compare/CompareTo比较；

public interface SortedSet<E> extends Set<E> {
}

NavigableSet

概述

A {@link SortedSet} extended with navigation methods reporting closest matches for given search targets.
Methods {@code lower}, {@code floor}, {@code ceiling}, and {@code higher} return elements respectively less than, less than or equal, greater than or equal, and greater than a given element, returning {@code null} if there is no such element.
A {@code NavigableSet} may be accessed and traversed in either ascending or descending order.

NavigableSet扩展了SortedSet，提供最接近查询目标的内容；

lower、floor、ceiling、higher 返回 <、<=、>=、>给定元素的内容；

NavigableSet可以 升序/降序遍历；

The {@code descendingSet} method returns a view of the set with the senses of all relational and directional methods inverted.
The performance of ascending operations and views is likely to be faster than that of descending ones.

descendingSet方法返回 降序的view；

升序的操作 性能优于 降序；

This interface additionally defines methods {@code pollFirst} and {@code pollLast} that return and remove the lowest and highest element, if one exists, else returning {@code null}.
Methods {@code subSet}, {@code headSet}, and {@code tailSet} differ from the like-named {@code SortedSet} methods in accepting additional arguments describing whether lower and upper bounds are inclusive versus exclusive.
Subsets of any {@code NavigableSet} must implement the {@code NavigableSet} interface.

pollFirst、pollLast 返回/移除 最低、最高的元素；

The return values of navigation methods may be ambiguous in implementations that permit {@code null} elements.
However, even in this case the result can be disambiguated by checking {@code contains(null)}.
To avoid such issues, implementations of this interface are encouraged to <em>not</em> permit insertion of {@code null} elements.

由于允许null，方法的返回值可能不明确；

鼓励实现NavigableSet接口的class不允许null；

public interface NavigableSet<E> extends SortedSet<E> {
}

TreeSet

概述

A {@link NavigableSet} implementation based on a {@link TreeMap}.
The elements are ordered using their {@linkplain Comparable natural ordering}, or by a {@link Comparator} provided at set creation time, depending on which constructor is used.

TreeSet是基于TreeMap的NavigableSet实现；

排序使用元素的Comparable自然排序 或 创建时提供的Comparator；

This implementation provides guaranteed log(n) time cost for the basic operations ({@code add}, {@code remove} and {@code contains}).

add、remove、contains话费 log(n) 的时间复杂度；

Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be <i>consistent with equals</i> if it is to correctly implement the {@code Set} interface.  

实现Set接口的排序 必须与equals一致；

This is so because the {@code Set} interface is defined in terms of the {@code equals} operation, but a {@code TreeSet} instance performs all element comparisons using its {@code compareTo} (or {@code compare}) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal. 

因为Set使用equals比较，TreeSet使用compareTo/compare比较；

Note that this implementation is not synchronized.
If multiple threads access a tree set concurrently, and at least one of the threads modifies the set, it <i>must</i> be synchronized externally.
This is typically accomplished by synchronizing on some object that naturally encapsulates the set.
If no such object exists, the set should be "wrapped" using the {@link Collections#synchronizedSortedSet Collections.synchronizedSortedSet} method.

TreeSet是线程非同步的；

如果多个线程并发修改TreeSet结构，必须在外部进行同步；

可以使用Collections.synchronizedSortedSet；

The iterators returned by this class's {@code iterator} method are <i>fail-fast</i>: if the set is modified at any time after the iterator is created, in any way except through the iterator's own {@code remove} method, the iterator will throw a {@link ConcurrentModificationException}.

TreeSet的iterator是fail-fast：如果在iterator时进行remove（非iterator的remove）操作，将会抛出ConcurrentModificationException；

链路

add(E e)

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

    // java.util.TreeMap.put
    public V put(K key, V value) {
        TreeMap.Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new TreeMap.Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        TreeMap.Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        TreeMap.Entry<K,V> e = new TreeMap.Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }