- 源码前面的说明：
* 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.
* TreeMap是红黑树基于 NavigableMap 的实现，根据使用的构造器决定该 map 是根据 key 值进行自然排序还是按照map创建时指定的规则进行排序。
* <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>.
*该实现保证了containsKey，get，put，remove操作均具有log（n）的时间复杂度。算法改编自XXXX
* <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>.)
注意treemap维持的排序和任何排序的map一样，无论是否提供明确的比较器，要正确地实现map接口，必须有一致的equals方法。
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.
*这是因为Map接口是根据equals方法定义，但是一个排序map使用compare或者compareTo进行键值的比较，所以从这个角度看，两个键值相等的元素是相等的。
* <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>
*多线程并发访问，至少有一个线程会修改map结构，map必须使用外部同步。（结构性修改是指任何能够添加或删除一个或者多个映射的的操作，仅仅修改一个与已经存在的键值的相关值不是结构性修改）这个通常通过同步某一个自然地封装了map的对象实现。如果这样的对象不存在，map应当使用包装的集合类。为了避免异常地非同步访问map，这样的操作必须在创建时就完成。
* <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.
* 如果map在迭代器创建之后发生结构性的修改，除了通过迭代器的自己的移除方法，迭代器会抛出ConcurrentModificationException异常。。因此对于并发修改，迭代器快速而干净利落地失败，而不是在未来不确定的时间里面冒任何任意的不确定性的风险。
* <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}.)
* 该类中返回的所有的索引对以及他的视图代表它们产生时候的快照。不支持索引的setValue方法。
* <p>This class is a member of the
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
* Java Collections Framework</a>.
*
* @param <K> the type of keys maintained by this map 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
- 构造方法
public TreeMap();默认的构造无参数方法
public TreeMap(Map<? extends K, ? extends V> m) ；基于给定的比较器创建空map的构造方法
public TreeMap(Map<? extends K, ? extends V> m)；使用map作为参数的构造方法
public TreeMap(SortedMap<K, ? extends V> m) 使用排序map作为参数的构造方法
- 查询操作
-
public int size()； 获取map的大小
-
public boolean containsKey(Object key):查询key是否存在
-
public boolean containsValue(Object value): 查询值是否存在
-
public V get(Object key): 获取指定key的值
-
public Comparator<? super K> comparator();比较器的构造方法
-
public void putAll(Map<? extends K, ? extends V> map)：从参数表中的map复制到当前的map
-
final Entry<K,V> getEntry(Object key)：利用了红黑树的查找方法
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
-
final Entry<K,V> getCeilingEntry(K key): 取上界的entry。如果key不存在取比key大的一个entry；如果所有key都比输入的小，返回空；存在即返回
-
final Entry<K,V> getFloorEntry(K key):和上一个相反，取下界。
-
public V put(K key, V value): 原理和红黑树的插入原理基本一致
常用的方法基本就以上这些，TreeMap提供了十分详细具体的实现
网友评论