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. * *

This implementation provides guaranteed log(n) time cost for the basic

* operations ({@code add}, {@code remove} and {@code contains}).

*

*

Note that the ordering maintained by a set (whether or not an explicit * comparator is provided) must beconsistent with equalsif it is to * correctly implement the {@code Set} interface.  (See {@code Comparable} * or {@code Comparator} for a precise definition ofconsistent with

* 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.  The behavior of a set *iswell-defined even if its ordering is inconsistent with equals; it * just fails to obey the general contract of the {@code Set} interface. * *

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, itmustbe 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.  This is best done at creation time, to prevent accidental * unsynchronized access to the set:

*  SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

* *

The iterators returned by this class's {@code iterator} method are *fail-fast: 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}. * Thus, in the face of concurrent modification, the iterator fails quickly * and cleanly, rather than risking arbitrary, non-deterministic behavior at * an undetermined time in the future. * *

Note that the fail-fast behavior of an iterator cannot be guaranteed * as it is, generally speaking, impossible to make any hard guarantees in the * presence of unsynchronized concurrent modification.  Fail-fast iterators * throw {@code ConcurrentModificationException} on a best-effort basis. * Therefore, it would be wrong to write a program that depended on this * exception for its correctness:the fail-fast behavior of iterators

* should be used only to detect bugs.* *

This class is a member of the * * Java Collections Framework. * * @param the type of elements maintained by this set

*

* @author  Josh Bloch

* @see    Collection

* @see    Set

* @see    HashSet

* @see    Comparable

* @see    Comparator

* @see    TreeMap

* @since  1.2

*/