Java java.util 类 TreeMap<K,V>（JDK5）

所有类

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

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)