All Packages Class Hierarchy This Package Previous Next Index
Class java.util.TreeMap
java.lang.Object
|
+----java.util.AbstractMap
|
+----java.util.TreeMap
- public class TreeMap
- extends AbstractMap
- implements Map, Serializable
Red-Black tree based implementation of the Map interface. This class
guarantees that the Map will be in ascending key order, sorted according
to the natural sort method for the key Class (see Comparable), or
by the Comparator provided at TreeMap creation time, depending on which
constructor is used.
This implementation provides guaranteed log(n) time cost for the
containsKey, get, put and remove operations. Algorithms are adaptations
of those in Corman, Leiserson, and Rivest's Introduction to
Algorithms.
Note that this implementation is not synchronized. If
multiple threads access a TreeMap concurrently, and at least one of the
threads modifies the TreeMap structurally, it must be synchronized
externally. (A structural modification is any operation that adds or
deletes one or more mappings; merely changing the value associated
with a key that is already contained in the Table is not a structural
modification.) This is typically accomplished by synchronizing on some
object that naturally encapsulates the TreeMap. If no such object exists,
the TreeMap should be "wrapped" using the Collections.synchronizedSet
method. This is best done at creation time, to prevent accidental
unsynchronized access to the TreeMap:
Map m = Collections.synchronizedMap(new TreeMap(...));
The Iterators returned by the iterator methods of the Collections returned
by all of TreeMap's "collection view methods" are fail-fast: if the
TreeMap is structurally modified at any time after the Iterator is created,
in any way except through the Iterator's own remove or add methods, the
Iterator will throw a 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.
- Since:
- JDK1.2
- See Also:
- Map, HashMap, ArrayMap, Hashtable, Comparable, Comparator, Collection, synchronizedMap
TreeMap()
- Constructs a new, empty TreeMap, sorted according to the keys'
natural sort method.
TreeMap(Comparator)
- Constructs a new, empty TreeMap, sorted according to the given
comparator.
TreeMap(Map)
- Constructs a new TreeMap containing the same mappings as the given
Map, sorted according to the keys' natural sort method.
clear()
- Removes all mappings from this TreeMap.
containsKey(Object)
- Returns true if this TreeMap contains a mapping for the specified key.
entries()
- Returns a Collection view of the mappings contained in this Map.
get(Object)
- Returns the value to which this TreeMap maps the specified key.
keySet()
- Returns a Set view of the keys contained in this TreeMap.
put(Object, Object)
- Associates the specified value with the specified key in this TreeMap.
remove(Object)
- Removes the mapping for this key from this TreeMap if present.
size()
- Returns the number of key-value mappings in this TreeMap.
subMap(Object, Object)
- Returns a view of the portion of this TreeMap whose keys range
from fromKey, inclusive, to toKey, exclusive.
values()
- Returns a Collection view of the values contained in this TreeMap.
TreeMap
public TreeMap()
- Constructs a new, empty TreeMap, sorted according to the keys'
natural sort method. All keys inserted into the TreeMap must
implement the Comparable interface. Furthermore, all such keys
must be mutually comparable: k1.compareTo(k2) must not
throw a typeMismatchException for any elements k1 and k2 in the
TreeMap. If the user attempts to put a key into the TreeMap that
violates this constraint (for example, the user attempts to put a String
key into a TreeMap whose keys are Integers), the put(Object key,
Object value) call will throw a ClassCastException.
- See Also:
- Comparable
TreeMap
public TreeMap(Comparator c)
- Constructs a new, empty TreeMap, sorted according to the given
comparator. All keys inserted into the TreeMap must be mutually
comparable by the given comparator: comparator.compare(k1,
k2) must not throw a typeMismatchException for any keys k1 and k2
in the TreeMap. If the user attempts to put a key into the
TreeMap that violates this constraint, the put(Object key, Object
value) call will throw a ClassCastException.
TreeMap
public TreeMap(Map t)
- Constructs a new TreeMap containing the same mappings as the given
Map, sorted according to the keys' natural sort method. All
keys inserted into the TreeMap must implement the Comparable
interface. Furthermore, all such keys must be mutually
comparable: k1.compareTo(k2) must not throw a
typeMismatchException for any elements k1 and k2 in the TreeMap.
- Throws:
ClassCastException
- the keys in t are not Comparable, or
are not mutually comparable.
size
public int size()
- Returns the number of key-value mappings in this TreeMap.
- Overrides:
- size in class AbstractMap
containsKey
public boolean containsKey(Object key)
- Returns true if this TreeMap contains a mapping for the specified key.
- Parameters:
- key - key whose presence in this Map is to be tested.
- Throws:
ClassCastException
- key cannot be compared with the keys
currently in the TreeMap.
- Throws:
NullPointerException
- key is null and this TreeMap uses
natural sort method, or its comparator does not tolerate
null keys.
- Overrides:
- containsKey in class AbstractMap
get
public Object get(Object key)
- Returns the value to which this TreeMap maps the specified key.
Returns null if the TreeMap contains no mapping for this key. A return
value of null does not necessarily indicate that the TreeMap
contains no mapping for the key; it's also possible that the TreeMap
explicitly maps the key to null. The containsKey operation may be
used to distinguish these two cases.
- Parameters:
- key - key whose associated value is to be returned.
- Throws:
ClassCastException
- key cannot be compared with the keys
currently in the TreeMap.
- Throws:
NullPointerException
- key is null and this TreeMap uses
natural sort method, or its comparator does not tolerate
null keys.
- Overrides:
- get in class AbstractMap
- See Also:
- containsKey
put
public Object put(Object key,
Object value)
- Associates the specified value with the specified key in this TreeMap.
If the TreeMap previously contained a mapping for this key, the old
value is replaced.
- Parameters:
- key - key with which the specified value is to be associated.
- value - value to be associated with the specified key.
- Returns:
- previous value associated with specified key, or null if there
was no mapping for key. A null return can also indicate that
the TreeMap previously associated null with the specified key.
- Throws:
ClassCastException
- key cannot be compared with the keys
currently in the TreeMap.
- Throws:
NullPointerException
- key is null and this TreeMap uses
natural sort method, or its comparator does not tolerate
null keys.
- Overrides:
- put in class AbstractMap
remove
public Object remove(Object key)
- Removes the mapping for this key from this TreeMap if present.
- Returns:
- previous value associated with specified key, or null if there
was no mapping for key. A null return can also indicate that
the TreeMap previously associated null with the specified key.
- Throws:
ClassCastException
- key cannot be compared with the keys
currently in the TreeMap.
- Throws:
NullPointerException
- key is null and this TreeMap uses
natural sort method, or its comparator does not tolerate
null keys.
- Overrides:
- remove in class AbstractMap
clear
public void clear()
- Removes all mappings from this TreeMap.
- Overrides:
- clear in class AbstractMap
keySet
public Set keySet()
- Returns a Set view of the keys contained in this TreeMap. The
Set's Iterator will return the keys in ascending order. The Set is
backed by the TreeMap, so changes to the TreeMap are reflected in the
Set, and vice-versa. The Set supports element removal, which removes
the corresponding mapping from the TreeMap, via the Iterator.remove,
Set.remove, removeAll retainAll, and clear operations. It does not
support the add or addAll operations.
- Overrides:
- keySet in class AbstractMap
values
public Collection values()
- Returns a Collection view of the values contained in this TreeMap.
The Collection's iterator will return the values in the order that
their corresponding keys appear in the tree. The Collection is
backed by the TreeMap, so changes to the TreeMap are reflected in
the Collection, and vice-versa. The Collection supports element
removal, which removes the corresponding mapping from the TreeMap,
via the Iterator.remove, Collection.remove, removeAll, retainAll
and clear operations. It does not support the add or addAll
operations.
- Overrides:
- values in class AbstractMap
entries
public Collection entries()
- Returns a Collection view of the mappings contained in this Map.
The Collection's Iterator will return the mappings in ascending Key
order. Each element in the returned collection is a Map.Entry.
The Collection is backed by the TreeMap, so changes to the TreeMap
are reflected in the Collection, and vice-versa. The Collection
supports element removal, which removes the corresponding mapping
from the TreeMap, via the Iterator.remove, Collection.remove,
removeAll, retainAll and clear operations. It does not support the
add or addAll operations.
- Overrides:
- entries in class AbstractMap
- See Also:
- Map.Entry
subMap
public Map subMap(Object fromKey,
Object toKey)
- Returns a view of the portion of this TreeMap whose keys range
from fromKey, inclusive, to toKey, exclusive. The returned Map
is backed by this TreeMap, so changes in the returned Map are
reflected in this TreeMap, and vice-versa. The returned Map supports
all optional Map operations. It does not support the subMap
operation, as it is not a TreeMap.
- Parameters:
- fromKey - low endpoint (inclusive) of the subMap.
- fromKey - high endpoint (exclusive) of the subMap.
- Throws:
ClassCastException
- fromKey or toKey cannot be compared
with the keys currently in the TreeMap.
- Throws:
NullPointerException
- fromKey or toKey is null and this
TreeMap uses natural sort method, or its comparator does
not tolerate null keys.
- Throws:
IllegalArgumentException
- fromKey is greater than toKey.
All Packages Class Hierarchy This Package Previous Next Index
Submit a bug or feature