Java源码解析TreeMap简介

TreeMap是常用的排序树，本文主要介绍TreeMap中，类的注释中对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
 **/

这是一个基于红黑树的可导航的实现。这个map基于key的可比较的自然顺序，或者基于在map创建时提供的Comparator的顺序来存储元素。

这个实现提供可保证的log(n)的时间复杂度来完成containsKey，get，put和remove操作。

需要注意到这一点，不管是否显式提供了排序器，如果这个排序map想要正确实现Map接口，tree map维护的顺序必须和equals保持一致，就像任何排序map那样。之所以会这样，是因为Map接口是根据equals操作来定义的，但是排序map进行所有key的比较时使用的是他们的compareTo方法，所以，从排序map的观点来看，被这个方法认为相等的两个key，才是相等的。尽管如果它的顺序和equals不一致，排序map的行为也是正常的，它只是没有遵守Map接口的通常约定。

请注意这个实现是非同步的。如果多个线程并发访问一个treemap，并且至少有一个线程修改结构，必须进行外部同步。这个通常是通过在包含这个map的对象上进行同步来实现的。如果没有这样的对象，那么这个map需要用Collections.synchronizedSortedMap方法包装一下。最好是在创建map时就这样做，以防止意外非同步访问这个map。代码如下SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

所有这个类的集合视角方法返回的集合的iterator方法返回的迭代器都是fast-fail的：如果迭代器创建后的任何时间map发生了结构性改变，除了通过迭代器的删除方法外，迭代器都会抛出同步修改异常。于是，面对同步修改时，迭代器会迅速干净的失败，而不是冒着在未来的不确定的时间发生不一致或无法确定的行为的风险。

这个类和它的视图的方法返回的Map.Entry对代表了他们被创建时的快照。他们不支持Entry.setValue方法。

这个类是Java集合框架的一个成员。

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对小牛知识库的支持。如果你想了解更多相关内容请查看下面相关链接