java.lang.Object java.util.AbstractMap<K,V> java.util.TreeMap<K,V>
K
- 此映射维护的键的类型
V
- 映射值的类型
public class TreeMap<K,V>
基于红黑树(Red-Black tree)的 NavigableMap
实现。该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator
进行排序,具体取决于使用的构造方法。
此实现为 containsKey、get、put 和 remove 操作提供受保证的 log(n) 时间开销。这些算法是 Cormen、Leiserson 和 Rivest 的 Introduction to Algorithms 中的算法的改编。
注意,如果要正确实现 Map 接口,则有序映射所保持的顺序(无论是否明确提供了比较器)都必须与 equals 一致。(关于与 equals 一致 的精确定义,请参阅 Comparable 或 Comparator)。这是因为 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 的成员。
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) 返回此映射的部分视图,其键的范围从 fromKey 到 toKey 。 |
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 |
构造方法详细信息 |
---|
public TreeMap()
Comparable
接口。另外,所有这些键都必须是
可互相比较的:对于映射中的任意两个键
k1 和
k2,执行
k1.compareTo(k2) 都不得抛出
ClassCastException。如果用户试图将违反此约束的键添加到映射中(例如,用户试图将字符串键添加到键为整数的映射中),则
put(Object key, Object value) 调用将抛出
ClassCastException。
public TreeMap(Comparator<? super K> comparator)
comparator
- 将用来对此映射进行排序的比较器。如果该参数为
null,则将使用键的
自然顺序。
public TreeMap(Map<? extends K,? extends V> m)
Comparable
接口。另外,所有这些键都必须是
可互相比较的:对于映射中的任意两个键
k1 和
k2,执行
k1.compareTo(k2) 都不得抛出
ClassCastException。此方法的运行时间为 n*log(n)。
m
- 其映射关系将存放在此映射中的映射
ClassCastException
- 如果 m 中的键不是
Comparable
,或者是不可相互比较的
NullPointerException
- 如果指定映射为 null
public TreeMap(SortedMap<K,? extends V> m)
m
- 有序映射,其映射关系将存放在此映射中,并且其比较器将用来对此映射进行排序
NullPointerException
- 如果指定映射为 null
方法详细信息 |
---|
public int size()
public boolean containsKey(Object key)
Map<K,V>
中的
containsKey
AbstractMap<K,V>
中的
containsKey
key
- 测试是否存在于此映射中的键
ClassCastException
- 如果指定键不能与映射中的当前键进行比较
NullPointerException
- 如果指定键为 null 并且此映射使用自然顺序,或者其比较器不允许使用 null 键
public boolean containsValue(Object value)
Map<K,V>
中的
containsValue
AbstractMap<K,V>
中的
containsValue
value
- 将测试其是否存在于此映射中的值
public V get(Object key)
null
。
更确切地讲,如果此映射包含从键 k
到值 v
的映射关系,根据该映射的排序 key
比较起来等于 k
,那么此方法将返回 v
;否则返回 null
。(最多只能有一个这样的映射关系。)
返回 null
值并不一定 表明映射不包含该键的映射关系;也可能此映射将该键显式地映射为 null
。可以使用 containsKey
操作来区分这两种情况。
key
- 要返回其关联值的键
null
ClassCastException
- 如果指定键不能与在映射中的当前键进行比较
NullPointerException
- 如果指定键为 null 并且此映射使用自然顺序,或者其比较器不允许使用 null 键
public Comparator<? super K> comparator()
SortedMap
复制的描述
SortedMap<K,V>
中的
comparator
public K firstKey()
SortedMap
复制的描述
NoSuchElementException
- 如果此映射为空
public K lastKey()
SortedMap
复制的描述
NoSuchElementException
- 如果此映射为空
public void putAll(Map<? extends K,? extends V> map)
map
- 将存储在此映射中的映射关系
ClassCastException
- 如果指定映射中的键或值的类不允许将键或值存储在此映射中
NullPointerException
- 如果指定映射为 null,或者指定映射包含 null 键,但此映射不允许使用 null 键
public V put(K key, V value)
key
- 要与指定值关联的键
value
- 要与指定键关联的值
ClassCastException
- 如果指定键不能与映射中的当前键进行比较
NullPointerException
- 如果指定键为 null 并且此映射使用自然顺序,或者其比较器不允许使用 null 键
public V remove(Object key)
key
- 将为其移除映射关系的键
ClassCastException
- 如果指定键不能与映射中的当前键进行比较
NullPointerException
- 如果指定键为 null 并且此映射使用自然顺序,或者其比较器不允许使用 null 键
public void clear()
public Object clone()
AbstractMap<K,V>
中的
clone
Cloneable
public Map.Entry<K,V> firstEntry()
NavigableMap
复制的描述
null
。
NavigableMap<K,V>
中的
firstEntry