java.util
类 TreeMap<K,V>

java.lang.Object
  java.util.AbstractMap<K,V>
      java.util.TreeMap<K,V>

所有已实现的接口：

Serializable, Cloneable, Map<K,V>, SortedMap<K,V>

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements SortedMap<K,V>, Cloneable, Serializable

SortedMap 接口的基于红黑树的实现。此类保证了映射按照升序顺序排列关键字，根据使用的构造方法不同，可能会按照键的类的自然顺序 进行排序（参见 Comparable），或者按照创建时所提供的比较器进行排序。

此实现为 containsKey、get、put 和 remove 操作提供了保证的 log(n) 时间开销。这些算法是 Cormen、Leiserson 和 Rivest 的《Introduction to Algorithms》中的算法的改编。

注意，如果有序映射要正确实现 Map 接口，则有序映射所保持的顺序（无论是否明确提供比较器）都必须保持与等号一致。（请参见与等号一致 的精确定义的 Comparable 或 Comparator。）这也是因为 Map 接口是按照等号操作定义的，但映射使用它的 compareTo（或 compare）方法对所有键进行比较，因此从有序映射的观点来看，此方法认为相等的两个键就是相等的。即使顺序与等号不一致，有序映射的行为仍然是 定义良好的；只不过没有遵守 Map 接口的常规约定。

注意，此实现不是同步的。如果多个线程同时访问一个映射，并且其中至少一个线程从结构上修改了该映射，则其必须 保持外部同步。（结构上修改是指添加或删除一个或多个映射关系的操作；仅改变与现有键关联的值不是结构上的修改。）这一般通过对自然封装该映射的某个对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的不同步访问，如下所示：

     Map m = Collections.synchronizedMap(new TreeMap(...));
 

由所有此类的“collection 视图方法”所返回的迭代器都是快速失败 的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器自身的 remove 或 add 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就完全失败，而不是冒着在将来不确定的时间任意发生不确定行为的风险。

注意，迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法：迭代器的快速失败行为应该仅用于检测 bug。

此类是 Java Collections Framework 的成员。

从以下版本开始：

1.2

另请参见：

Map, HashMap, Hashtable, Comparable, Comparator, Collection, Collections.synchronizedMap(Map), 序列化表格

构造方法摘要

TreeMap()
构造一个新的空映射，该映射按照键的自然顺序排序。

TreeMap(Comparator<? super K> c)
构造一个新的空映射，该映射根据给定的比较器进行排序。

TreeMap(Map<? extends K,? extends V> m)
构造一个新映射，包含的映射关系与给定的映射相同，这个新映射按照键的自然顺序 进行排序。

TreeMap(SortedMap<K,? extends V> m)
构造一个新的映射，包含的映射关系与给定的 SortedMap 相同，该映射按照相同的排序方式进行排序。

方法摘要

void	clear() 从此 TreeMap 中删除所有映射关系。
Object	clone() 返回 TreeMap 实例的浅表复制。
Comparator<? super K>	comparator() 返回用于对此映射进行排序的比较器，如果此映射使用它的键的自然顺序，则返回 null。
boolean	containsKey(Object key) 如果此映射包含对于指定的键的映射关系，则返回 true。
boolean	containsValue(Object value) 如果此映射把一个或多个键映射到指定值，则返回 true。
Set<Map.Entry<K,V>>	entrySet() 返回此映射所包含的映射关系的 set 视图。
K	firstKey() 返回有序映射中当前第一个（最小的）键。
V	get(Object key) 返回此映射中映射到指定键的值。
SortedMap<K,V>	headMap(K toKey) 返回此映射的部分视图，其键严格小于 toKey。
Set<K>	keySet() 返回此映射中所包含的键的 Set 视图。
K	lastKey() 返回有序映射中当前最后一个（最大的）键。
V	put(K key, V value) 在此映射中关联指定值与指定键。
void	putAll(Map<? extends K,? extends V> map) 将指定映射中所有映射关系复制到此映射中。
V	remove(Object key) 如果此 TreeMap 中存在该键的映射关系，则将其移除。
int	size() 返回此映射中的键-值映射关系数。
SortedMap<K,V>	subMap(K fromKey, K toKey) 返回此映射的部分视图，其键值从 fromKey（包括）到 toKey（不包括）。
SortedMap<K,V>	tailMap(K fromKey) 返回映射的部分视图，其键大于或等于 fromKey。
Collection<V>	values() 返回此 Map 中所包含的值的 collection 视图。

从类 java.util.AbstractMap 继承的方法

equals, hashCode, isEmpty, toString

从类 java.lang.Object 继承的方法

finalize, getClass, notify, notifyAll, wait, wait, wait

从接口 java.util.Map 继承的方法

equals, hashCode, isEmpty

构造方法详细信息

TreeMap

public TreeMap()

构造一个新的空映射，该映射按照键的自然顺序排序。插入该映射的所有键必须实现 Comparable 接口。而且，所有这样的键必须是可相互比较的：对映射中的任何元素 k1 和 k2 执行 k1.compareTo(k2) 必须不抛出 ClassCastException。如果用户尝试将违背此约束的键添加到此映射中（例如，用户试图将字符串键添加到其键为整数的映射中），则 put(Object key, Object value) 调用将抛出 ClassCastException。

另请参见：

Comparable

TreeMap

public TreeMap(Comparator<? super K> c)

构造一个新的空映射，该映射根据给定的比较器进行排序。所有插入到该映射到的所有键必须可由给定的比较器相互可比较：对映射中的任何键 k1 和 k2 执行 comparator.compare(k1, k2) 必须不抛出 ClassCastException。如果用户尝试将违背此约束的键添加到映射中，则 put(Object key, Object value) 调用将抛出 ClassCastException。

参数：

c - 用于对此映射进行排序的比较器。null 值指示应该使用键的自然排序。

TreeMap

public TreeMap(Map<? extends K,? extends V> m)

构造一个新映射，包含的映射关系与给定的映射相同，这个新映射按照键的自然顺序 进行排序。插入到该新映射的所有键必须实现 Comparable 接口。而且，所有这样的键必须是可相互比较的：为映射中的任何元素 k1 和 k2 执行 k1.compareTo(k2) 必须不抛出 ClassCastException。此方法在 n*log(n) 时间内运行。

参数：

m - 映射，其映射关系将存放在此映射中。

抛出：

ClassCastException - t 中的键不是 Comparable 或者不是可相互比较的。

NullPointerException - 如果指定的映射为 null。

TreeMap

public TreeMap(SortedMap<K,? extends V> m)

构造一个新的映射，包含的映射关系与给定的 SortedMap 相同，该映射按照相同的排序方式进行排序。此方法以线性的时间运行。

参数：

m - 有序映射，其映射关系将存放在此映射中，并且其比较器要用于对此映射进行排序。

抛出：

NullPointerException - 如果指定的有序映射为 null。

方法详细信息

size

public int size()

返回此映射中的键-值映射关系数。

指定者：

接口 Map<K,V> 中的 size

覆盖：

类 AbstractMap<K,V> 中的 size

返回：

映射中的键-值映射关系数。

containsKey

public boolean containsKey(Object key)

如果此映射包含对于指定的键的映射关系，则返回 true。

指定者：

接口 Map<K,V> 中的 containsKey

覆盖：

类 AbstractMap<K,V> 中的 containsKey

参数：

key - 测试在此映射中存在与否的键。

返回：

如果此映射包含指定键的映射关系，则返回 true。

抛出：

ClassCastException - 如果该键不能与映射中的当前键进行比较。

NullPointerException - 键为 null 并且此映射使用自然排序，或者它的比较器不允许使用 null 键。

containsValue

public boolean containsValue(Object value)

如果此映射把一个或多个键映射到指定值，则返回 true。更正式地说，当且仅当此映射包含至少一个到值 v 的映射关系，并且 (value==null ? v==null :value.equals(v))，才返回 true。对于大部分 Map 实现而言，此操作需要的时间可能会与 Map 的大小呈线性关系。

指定者：

接口 Map<K,V> 中的 containsValue

覆盖：

类 AbstractMap<K,V> 中的 containsValue

参数：

value - 要测试其在此 Map 中存在与否的值。

返回：

如果到 value 的映射关系存在，则返回 true；否则，返回 false。

从以下版本开始：

1.2

get

public V get(Object key)

返回此映射中映射到指定键的值。如果该映射中没有此键的映射关系，则返回 null。返回值 null 并非一定表明该映射不包含该键的映射关系；也可能此映射将该键显式地映射到 null。可使用 containsKey 操作区分这两种情况。

指定者：

接口 Map<K,V> 中的 get

覆盖：

类 AbstractMap<K,V> 中的 get

参数：

key - 要返回其关联值的键。

返回：

此映射将指定键映射到的值，如果映射不包含该键的映射关系，则返回 null。

抛出：

ClassCastException - 键不能与在映射中的当前键进行比较。

NullPointerException - 键为 null 并且此映射使用自然排序，或者它的比较器不允许使用 null 键。

另请参见：

containsKey(Object)

comparator

public Comparator<? super K> comparator()

返回用于对此映射进行排序的比较器，如果此映射使用它的键的自然顺序，则返回 null。

指定者：

接口 SortedMap<K,V> 中的 comparator

返回：

与此有序映射关联的比较器，如果使用它的键的自然排序方法，则返回 null。

firstKey

public K firstKey()

返回有序映射中当前第一个（最小的）键。

指定者：

接口 SortedMap<K,V> 中的 firstKey

返回：

有序映射中当前第一个（最小的）键。

抛出：

NoSuchElementException - 映射为空。

lastKey

public K lastKey()

返回有序映射中当前最后一个（最大的）键。

指定者：

接口 SortedMap<K,V> 中的 lastKey

返回：

有序映射中当前最后一个（最大的）键。

抛出：

NoSuchElementException - 映射为空。

putAll

public void putAll(Map<? extends K,? extends V> map)

将指定映射中所有映射关系复制到此映射中。针对指定映射中的当前所有键，这些映射关系将替换此映射具有的所有映射关系。

指定者：

接口 Map<K,V> 中的 putAll

覆盖：

类 AbstractMap<K,V> 中的 putAll

参数：

map - 要存储在此映射中的映射关系。

抛出：

ClassCastException - 指定映射中的键或值的类不允许将键或值存储在此映射中。

NullPointerException - 如果给定的映射为 null 或者此映射不允许使用 null 键，但是指定映射中的键为 null。

put

public V put(K key,
             V value)

在此映射中关联指定值与指定键。如果映射以前包含一个此键的映射关系，那么将替换原值。

指定者：

接口 Map<K,V> 中的 put

覆盖：

类 AbstractMap<K,V> 中的 put

参数：

key - 指定值将要关联的键。

value - 指定键将要关联的值。

返回：

以前与指定键关联的值，如果没有该键的映射关系，则返回 null。返回 null 还可能表示该映射以前关联了 null 与指定键。

抛出：

ClassCastException - 键不能与映射中的当前键进行比较。

NullPointerException - 键为 null 并且此映射使用自然排序，或者它的比较器不允许使用 null 键。

remove

public V remove(Object key)

如果此 TreeMap 中存在该键的映射关系，则将其移除。

指定者：

接口 Map<K,V> 中的 remove

覆盖：

类 AbstractMap<K,V> 中的 remove

参数：

key - 应该删除映射关系的键

返回：

以前与指定的键关联的值，如果没有该键的映射关系，则返回 null。返回 null 还可能表示该映射以前关联了 null 与指定键。

抛出：

ClassCastException - 键不能和映射中的当前键进行比较。

NullPointerException - 键为 null 并且此映射使用自然排序，或者它的比较器不允许使用 null 键。

clear

public void clear()

从此 TreeMap 中删除所有映射关系。

指定者：

接口 Map<K,V> 中的 clear

覆盖：

类 AbstractMap<K,V> 中的 clear

clone

public Object clone()

返回 TreeMap 实例的浅表复制。（不复制键和值本身。）

覆盖：

类 AbstractMap<K,V> 中的 clone

返回：

此 Map 的浅表复制。

另请参见：

Cloneable

keySet

public Set<K> keySet()

返回此映射中所包含的键的 Set 视图。集合的迭代器将按照升序顺序返回键。映射受此 TreeMap 实例的支持，所有对此映射的更改也反映在 Set 中，反之亦然。通过 Iterator.remove、Set.remove、removeAll、retainAll 和 clear 操作，此 Set 支持元素移除，可从此映射移除相应的映射关系。它不支持 add 或 addAll 操作。

指定者：

接口 Map<K,V> 中的 keySet

覆盖：

类 AbstractMap<K,V> 中的 keySet

返回：

此 TreeMap 中包含的键的 set 视图。

values

public Collection<V> values()

返回此 Map 中所包含的值的 collection 视图。该 collection 的迭代器将按照值的相应键在树中出现的顺序返回值。collection 受此 TreeMap 实例的支持，所以对此映射的更改也反映在 collection 中，反之亦然。通过 Iterator.remove、Collection.remove、removeAll、retainAll 和 clear 操作，此 collection 支持元素移除，可从该映射中移除相应的映射关系。它不支持 add 或 addAll 操作。

指定者：

接口 Map<K,V> 中的 values

覆盖：

类 AbstractMap<K,V> 中的 values

返回：

此映射所包含的值的 collection 视图。

entrySet

public Set<Map.Entry<K,V>> entrySet()

返回此映射所包含的映射关系的 set 视图。该集合的迭代器按照键的升序顺序返回映射关系。在返回的 set 中，每个元素都是一个 Map.Entry。该 set 受此映射支持，所以对此映射的更改也反映在该 set 中，反之亦然。通过 Iterator.remove、Set.remove、removeAll、retainAll 和 clear 操作，该 set 支持元素移除，可从该 TreeMap 移除相应的映射关系。它不支持 add 或 addAll 操作。

指定者：

接口 Map<K,V> 中的 entrySet

指定者：

类 AbstractMap<K,V> 中的 entrySet

返回：

包含此映射中的映射关系的 set 视图。

另请参见：

Map.Entry

subMap

public SortedMap<K,V> subMap(K fromKey,
                             K toKey)

返回此映射的部分视图，其键值从 fromKey（包括）到 toKey（不包括）。（如果 fromKey 和 toKey 相等，则返回空的有序映射。）返回的有序映射由此映射支持，所以返回的有序映射中的更改将反映在此映射中，反之亦然。返回的有序映射支持所有可选的映射操作。

如果用户试图插入小于 fromKey 或大于等于 toKey 的键，那么此方法返回的有序映射将抛出 IllegalArgumentException。

注意：此方法总是返回 半开区间（包括它的低终结点而不包括高终结点）。如果需要一个闭区间（同时包括两个终结点），并且键类型允许计算给定键的后续值，则只需请求从 lowEndpoint 到 successor(highEndpoint) 的子区间。例如，假定 m 是用字符串作为键的有序映射。下面的语句得到一个包含 m 中键在 low 和 high（包括）之间所有键-值映射关系的视图：

    SortedMap sub = m.submap(low, high+"\0");

可以使用类似的技术生成开区间（两个终结点都不包括）。下面的语句将得到一个包含 m 中键在 low 和 high（不包括）之间的所有键-值映射关系的视图：

    SortedMap sub = m.subMap(low+"\0", high);

指定者：

接口 SortedMap<K,V> 中的 subMap

参数：

fromKey - subMpa 的低终结点（包括）。

toKey - subMap 的高终结点（不包括）。

返回：

此映射的部分视图，其键从 fromKey（包括）到 toKey（不包括）。

抛出：

ClassCastException - 如果不能使用此映射的比较器（如果该映射没有比较器，使用自然排序）比较 fromKey 和 toKey。

IllegalArgumentException - 如果 fromKey 大于 toKey。

NullPointerException - 如果 fromKey 或 toKey 为 null，并且此映射使用自然排序，或者其比较器不允许使用 null 键。

headMap

public SortedMap<K,V> headMap(K toKey)

返回此映射的部分视图，其键严格小于 toKey。返回的有序映射由此映射支持，所以返回的有序映射中的更改将反映在此映射中，反之亦然。返回的有序映射支持所有可选的映射操作。

如果用户试图插入大于或等于 toKey 的键，那么由此方法返回的有序映射将抛出 IllegalArgumentException。

注：此方法总是返回不包括（高）终结点的视图。如果需要不包含此终结点的视图，并且键类型允许计算给定键的后续值，则只需要请求以 successor(highEndpoint) 为界的 headMap。例如，假定 m 是用字符串作为键的有序映射。下面的语句将得到一个包含 m 中键小于或等于 high 的所有键-值映射关系的视图：

     SortedMap head = m.headMap(high+"\0");
 

指定者：

接口 SortedMap<K,V> 中的 headMap

参数：

toKey - headMap 的高终结点（不包括）。

返回：

此映射的部分视图，要求其键严格小于 toKey。

抛出：

ClassCastException - 如果 toKey 与此映射的比较器不兼容（如果映射没有比较器，并且 toKey 没有实现 Comparable）。

IllegalArgumentException - 如果此映射本身是一个 subMap、headMap 或 tailMap，并且 toKey 不在 subMap、headMap 或 tailMap 指定的范围之内。

NullPointerException - 如果 toKey 为 null，并且此映射使用自然排序，或者其比较器不允许使用 null 键。

tailMap

public SortedMap<K,V> tailMap(K fromKey)

返回映射的部分视图，其键大于或等于 fromKey。返回的有序映射由此映射支持，所以返回的有序映射中的更改也反映在此映射中，反之亦然。返回的有序映射支持所有可选的映射操作。

如果用户试图插入小于 fromKey 的键，则由此方法返回的有序映射将抛出 IllegalArgumentException。

注：此方法总是返回包括（低）终结点的视图。如果需要不含此终结点的视图，并且元素类型允许计算给定值的后续值，则只需要请求以 successor(lowEndpoint) 为界的 headMap。例如，假定 m 是用字符串作为键的有序映射。下面的语句将得到一个包含 m 中键严格大于 low 的所有键-值映射关系的视图：

     SortedMap tail = m.tailMap(low+"\0");
 

指定者：

接口 SortedMap<K,V> 中的 tailMap

参数：

fromKey - tailMap 的低终结点（包括）。

返回：

此映射的部分视图，其键大于或等于 fromKey 。

抛出：

ClassCastException - 如果 fromKey 与此映射的比较器不兼容（如果映射没有比较器，并且 fromKey 没有实现 Comparable）。

IllegalArgumentException - 如果此映射本身是一个 subMap、headMap 或 tailMap，并且 fromKey 不在 subMap、headMap 或 tailMap 指定的范围之内。

NullPointerException - 如果 fromKey 为 null，并且此映射使用自然排序，或者其比较器不允许使用 null 键。