java.util

接口
异常
错误
java.lang.Object
  继承者 java.util.AbstractMap<K,V>
      继承者 java.util.TreeMap<K,V>
类型参数:
K - 此映射维护的键的类型
V - 映射值的类型
所有已实现的接口:
Serializable, Cloneable, Map<K,V>, NavigableMap<K,V>, SortedMap<K,V>

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

基于红黑树(Red-Black tree)的 NavigableMap 实现。该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。

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

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

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

   SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

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

注意,迭代器的快速失败行为无法得到保证,一般来说,当存在不同步的并发修改时,不可能作出任何肯定的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此,编写依赖于此异常的程序的做法是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测 bug。

此类及其视图中的方法返回的所有 Map.Entry 对都表示生成它们时的映射关系的快照。它们 支持 Entry.setValue 方法。(不过要注意的是,使用 put 更改相关映射中的映射关系是有可能的。)

此类是 Java Collections Framework 的成员。

从以下版本开始:
1.2
另请参见:
Map, HashMap, Hashtable, Comparable, Comparator, Collection, 序列化表格

嵌套类摘要
 
从类 java.util.AbstractMap 继承的嵌套类/接口
AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>
 
构造方法摘要
TreeMap()
          使用键的自然顺序构造一个新的、空的树映射。
TreeMap(Comparator<? super K> comparator)
          构造一个新的、空的树映射,该映射根据给定比较器进行排序。
TreeMap(Map<? extends K,? extends V> m)
          构造一个与给定映射具有相同映射关系的新的树映射,该映射根据其键的自然顺序 进行排序。
TreeMap(SortedMap<K,? extends V> m)
          构造一个与指定有序映射具有相同映射关系和相同排序顺序的新的树映射。
 
方法摘要
 Map.Entry<K,V> ceilingEntry(K key)
          返回一个键-值映射关系,它与大于等于给定键的最小键关联;如果不存在这样的键,则返回 null
 K ceilingKey(K key)
          返回大于等于给定键的最小键;如果不存在这样的键,则返回 null
 void clear()
          从此映射中移除所有映射关系。
 Object clone()
          返回此 TreeMap 实例的浅表副本。
 Comparator<? super K> comparator()
          返回对此映射中的键进行排序的比较器;如果此映射使用键的自然顺序,则返回 null
 boolean containsKey(Object key)
          如果此映射包含指定键的映射关系,则返回 true
 boolean containsValue(Object value)
          如果此映射为指定值映射一个或多个键,则返回 true
 NavigableSet<K> descendingKeySet()
          返回此映射中所包含键的逆序 NavigableSet 视图。
 NavigableMap<K,V> descendingMap()
          返回此映射中所包含映射关系的逆序视图。
 Set<Map.Entry<K,V>> entrySet()
          返回此映射中包含的映射关系的 Set 视图。
 Map.Entry<K,V> firstEntry()
          返回一个与此映射中的最小键关联的键-值映射关系;如果映射为空,则返回 null
 K firstKey()
          返回此映射中当前第一个(最低)键。
 Map.Entry<K,V> floorEntry(K key)
          返回一个键-值映射关系,它与小于等于给定键的最大键关联;如果不存在这样的键,则返回 null
 K floorKey(K key)
          返回小于等于给定键的最大键;如果不存在这样的键,则返回 null
 V get(Object key)
          返回指定键所映射的值,如果对于该键而言,此映射不包含任何映射关系,则返回 null
 SortedMap<K,V> headMap(K toKey)
          返回此映射的部分视图,其键值严格小于 toKey
 NavigableMap<K,V> headMap(K toKey, boolean inclusive)
          返回此映射的部分视图,其键小于(或等于,如果 inclusive 为 true)toKey
 Map.Entry<K,V> higherEntry(K key)
          返回一个键-值映射关系,它与严格大于给定键的最小键关联;如果不存在这样的键,则返回 null
 K higherKey(K key)
          返回严格大于给定键的最小键;如果不存在这样的键,则返回 null
 Set<K> keySet()
          返回此映射包含的键的 Set 视图。
 Map.Entry<K,V> lastEntry()
          返回与此映射中的最大键关联的键-值映射关系;如果映射为空,则返回 null
 K lastKey()
          返回映射中当前最后一个(最高)键。
 Map.Entry<K,V> lowerEntry(K key)
          返回一个键-值映射关系,它与严格小于给定键的最大键关联;如果不存在这样的键,则返回 null
 K lowerKey(K key)
          返回严格小于给定键的最大键;如果不存在这样的键,则返回 null
 NavigableSet<K> navigableKeySet()
          返回此映射中所包含键的 NavigableSet 视图。
 Map.Entry<K,V> pollFirstEntry()
          移除并返回与此映射中的最小键关联的键-值映射关系;如果映射为空,则返回 null
 Map.Entry<K,V> pollLastEntry()
          移除并返回与此映射中的最大键关联的键-值映射关系;如果映射为空,则返回 null
 V put(K key, V value)
          将指定值与此映射中的指定键进行关联。
 void putAll(Map<? extends K,? extends V> map)
          将指定映射中的所有映射关系复制到此映射中。
 V remove(Object key)
          如果此 TreeMap 中存在该键的映射关系,则将其删除。
 int size()
          返回此映射中的键-值映射关系数。
 NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
          返回此映射的部分视图,其键的范围从 fromKeytoKey
 SortedMap<K,V> subMap(K fromKey, K toKey)
          返回此映射的部分视图,其键值的范围从 fromKey(包括)到 toKey(不包括)。
 SortedMap<K,V> tailMap(K fromKey)
          返回此映射的部分视图,其键大于等于 fromKey
 NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)
          返回此映射的部分视图,其键大于(或等于,如果 inclusive 为 true)fromKey
 Collection<V> values()
          返回此映射包含的值的 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 接口。另外,所有这些键都必须是 可互相比较的:对于映射中的任意两个键 k1k2,执行 k1.compareTo(k2) 都不得抛出 ClassCastException。如果用户试图将违反此约束的键添加到映射中(例如,用户试图将字符串键添加到键为整数的映射中),则 put(Object key, Object value) 调用将抛出 ClassCastException


TreeMap

public TreeMap(Comparator<? super K> comparator)
构造一个新的、空的树映射,该映射根据给定比较器进行排序。插入该映射的所有键都必须由给定比较器进行 相互比较:对于映射中的任意两个键 k1k2,执行 comparator.compare(k1, k2) 都不得抛出 ClassCastException。如果用户试图将违反此约束的键放入映射中,则 put(Object key, Object value) 调用将抛出 ClassCastException

参数:
comparator - 将用来对此映射进行排序的比较器。如果该参数为 null,则将使用键的 自然顺序

TreeMap

public TreeMap(Map<? extends K,? extends V> m)
构造一个与给定映射具有相同映射关系的新的树映射,该映射根据其键的 自然顺序 进行排序。插入此新映射的所有键都必须实现 Comparable 接口。另外,所有这些键都必须是 可互相比较的:对于映射中的任意两个键 k1k2,执行 k1.compareTo(k2) 都不得抛出 ClassCastException。此方法的运行时间为 n*log(n)。

参数:
m - 其映射关系将存放在此映射中的映射
抛出:
ClassCastException - 如果 m 中的键不是 Comparable,或者是不可相互比较的
NullPointerException - 如果指定映射为 null

TreeMap

public TreeMap(SortedMap<K,? extends V> m)
构造一个与指定有序映射具有相同映射关系和相同排序顺序的新的树映射。此方法是以线性时间运行的。

参数:
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<K,V> 中的 containsValue
覆盖:
AbstractMap<K,V> 中的 containsValue
参数:
value - 将测试其是否存在于此映射中的值
返回:
如果存在到 value 的映射关系,则返回 true;否则返回 false
从以下版本开始:
1.2

get

public V get(Object key)
返回指定键所映射的值,如果对于该键而言,此映射不包含任何映射关系,则返回 null

更确切地讲,如果此映射包含从键 k 到值 v 的映射关系,根据该映射的排序 key 比较起来等于 k,那么此方法将返回 v;否则返回 null。(最多只能有一个这样的映射关系。)

返回 null 值并不一定 表明映射不包含该键的映射关系;也可能此映射将该键显式地映射为 null。可以使用 containsKey 操作来区分这两种情况。

指定者:
接口 Map<K,V> 中的 get
覆盖:
AbstractMap<K,V> 中的 get
参数:
key - 要返回其关联值的键
返回:
指定键所映射的值;如果此映射不包含该键的映射关系,则返回 null
抛出:
ClassCastException - 如果指定键不能与在映射中的当前键进行比较
NullPointerException - 如果指定键为 null 并且此映射使用自然顺序,或者其比较器不允许使用 null 键

comparator

public Comparator<? super K> comparator()
从接口 SortedMap 复制的描述
返回对此映射中的键进行排序的比较器;如果此映射使用键的 自然顺序,则返回 null

指定者:
接口 SortedMap<K,V> 中的 comparator
返回:
用来对此映射中的键进行排序的比较器;如果此映射使用键的自然顺序,则返回 null

firstKey

public K firstKey()
从接口 SortedMap 复制的描述
返回此映射中当前第一个(最低)键。

指定者:
接口 SortedMap<K,V> 中的 firstKey
返回:
此映射中当前第一个(最低)键
抛出:
NoSuchElementException - 如果此映射为空

lastKey

public K lastKey()
从接口 SortedMap 复制的描述
返回映射中当前最后一个(最高)键。

指定者:
接口 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 - 要与指定键关联的值
返回:
key 关联的先前值;如果没有针对 key 的映射关系,则返回 null。(返回 null 还可能表示该映射以前将 nullkey 关联。)
抛出:
ClassCastException - 如果指定键不能与映射中的当前键进行比较
NullPointerException - 如果指定键为 null 并且此映射使用自然顺序,或者其比较器不允许使用 null 键

remove

public V remove(Object key)
如果此 TreeMap 中存在该键的映射关系,则将其删除。

指定者:
接口 Map<K,V> 中的 remove
覆盖:
AbstractMap<K,V> 中的 remove
参数:
key - 将为其移除映射关系的键
返回:
返回与 key 关联的先前值,如果没有针对 key 的映射关系,则返回 null。(返回 null 还可能表示该映射以前将 nullkey 关联。)
抛出:
ClassCastException - 如果指定键不能与映射中的当前键进行比较
NullPointerException - 如果指定键为 null 并且此映射使用自然顺序,或者其比较器不允许使用 null 键

clear

public void clear()
从此映射中移除所有映射关系。在此调用返回之后,映射将为空。

指定者:
接口 Map<K,V> 中的 clear
覆盖:
AbstractMap<K,V> 中的 clear

clone

public Object clone()
返回此 TreeMap 实例的浅表副本。(键和值本身不被复制。)

覆盖:
AbstractMap<K,V> 中的 clone
返回:
此映射的浅表副本
另请参见:
Cloneable

firstEntry

public Map.Entry<K,V> firstEntry()
从接口 NavigableMap 复制的描述
返回一个与此映射中的最小键关联的键-值映射关系;如果映射为空,则返回 null

指定者:
接口 NavigableMap<K,V> 中的 firstEntry
返回: <