Java源码解析TreeMap简介

/**

  * a red-black tree based {@link navigablemap} implementation.

  * the map is sorted according to the {@linkplain comparable natural

  * ordering} of its keys, or by a {@link comparator} provided at map

  * creation time, depending on which constructor is used.

  * <p>this implementation provides guaranteed log(n) time cost for the

  * {@code containskey}, {@code get}, {@code put} and {@code remove}

  * operations. algorithms are adaptations of those in cormen, leiserson, and

  * rivest's <em>introduction to algorithms</em>.

  * <p>note that the ordering maintained by a tree map, like any sorted map, and

  * whether or not an explicit comparator is provided, must be <em>consistent

  * with {@code equals}</em> if this sorted map is to correctly implement the

  * {@code map} interface. (see {@code comparable} or {@code comparator} for a

  * precise definition of <em>consistent with equals</em>.) this is so because

  * the {@code map} interface is defined in terms of the {@code equals}

  * operation, but a sorted map performs all key comparisons using its {@code

  * compareto} (or {@code compare}) method, so two keys that are deemed equal by

  * this method are, from the standpoint of the sorted map, equal. the behavior

  * of a sorted map <em>is</em> well-defined even if its ordering is

  * inconsistent with {@code equals}; it just fails to obey the general contract

  * of the {@code map} interface.

  * <p><strong>note that this implementation is not synchronized.</strong>

  * if multiple threads access a map concurrently, and at least one of the

  * threads modifies the map structurally, it <em>must</em> be synchronized

  * externally. (a structural modification is any operation that adds or

  * deletes one or more mappings; merely changing the value associated

  * with an existing key is not a structural modification.) this is

  * typically accomplished by synchronizing on some object that naturally

  * encapsulates the map.

  * if no such object exists, the map should be "wrapped" using the

  * {@link collections#synchronizedsortedmap collections.synchronizedsortedmap}

  * method. this is best done at creation time, to prevent accidental

  * unsynchronized access to the map: <pre>

  *  sortedmap m = collections.synchronizedsortedmap(new treemap(...));</pre>

  * <p>the iterators returned by the {@code iterator} method of the collections

  * returned by all of this class's "collection view methods" are

  * <em>fail-fast</em>: if the map is structurally 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.

  * <p>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:  <em>the fail-fast behavior of iterators

  * should be used only to detect bugs.</em>

  * <p>all {@code map.entry} pairs returned by methods in this class

  * and its views represent snapshots of mappings at the time they were

  * produced. they do <strong>not</strong> support the {@code entry.setvalue}

  * method. (note however that it is possible to change mappings in the

  * associated map using {@code put}.)

  * <p>this class is a member of the

  * <a href="{@docroot}/technotes/guides/collections/index.html" rel="external nofollow" >

  * java collections framework</a>.

  * @param <k> the type of keys maintained by this map

  * @param <v> the type of mapped values

  * @author josh bloch and doug lea

  * @see map

  * @see hashmap

  * @see hashtable

  * @see comparable

  * @see comparator

  * @see collection

  * @since 1.2

  **/