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 インタフェースの実装に基づく Red-Black ツリーです。このクラスでは、マップが確実にキーの昇順でソートされます。ただし、ソート方法はコンストラクタにより異なり、キーのクラスの「自然順序付け」(Comparable を参照) によりソートされる場合と、作成時に提供されるコンパレータによってソートされる場合があります。

この実装は、containsKey、get、put、remove の各オペレーションに保証済みの log(n) 時間コストを提供します。アルゴリズムは、Cormen、Leiserson、Rivest の「Introduction to Algorithms」のものに手を加えています。

ソートマップにより Map インタフェースを正しく実装する場合は、明示的なコンパレータの提供の有無にかかわらず、ソートマップで管理される順序付けは「equals と一貫性」が必要です (「equals との一貫性」の正確な定義については、Comparable または Comparator を参照)。これは Map インタフェースが equals オペレーションに基づいて定義されるためですが、マップはその compareTo メソッドまたは compare メソッドを使ってすべてのキーを比較するので、このメソッドによって等しいと見なされる 2 つのキーはソートマップから見ても等価です。ソートマップの動作は、その順序付けが equals と一貫性がない場合でも明確に定義されていますが、Map インタフェースの一般規約には準拠していません。

この実装は同期化されません。複数のスレッドが同時にマップにアクセスし、それらのスレッドの少なくとも 1 つが構造的にマップを変更する場合には、外部で同期をとる必要があります。構造的な変更とは、1 つ以上のマッピングを追加または削除するようなオペレーションです。既存のキーに関連付けられている値を変更する処理は、構造的な変更ではありません。通常、構造的な変更は、マップを自然にカプセル化する特定のオブジェクトで同期をとることによって達成されます。そのようなオブジェクトがない場合には、Collections.synchronizedMap メソッドを使ってマップを「ラップ」します。マップへの偶発的な非同期アクセスを防ぐために、作成時に行うのが最適です。

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

このクラスの「コレクションビューメソッド」によって返される反復子は「フェイルファスト」です。つまり、反復子の作成後に、反復子自体の remove メソッドまたは add メソッド以外の方法でマップが構造的に変更されると、反復子は ConcurrentModificationException をスローします。したがって、同時に変更が行われると、反復子は、将来の予測できない時点において予測できない動作が発生する危険を回避するために、ただちにかつ手際よく例外をスローします。

通常、非同期の同時変更がある場合、確かな保証を行うことは不可能なので、反復子のフェイルファストの動作を保証することはできません。フェイルファスト反復子は最善努力原則に基づき、ConcurrentModificationException をスローします。したがって、正確を期すためにこの例外に依存するプログラムを書くことは誤りです。「反復子のフェイルファストの動作はバグを検出するためにのみ使用すべきです」

このクラスは、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() マップを順序付けするのに使うコンパレータを返します。
boolean	containsKey(Object key) マップが指定されたキーのマッピングを保持する場合に true を返します。
boolean	containsValue(Object value) マップが 1 つ以上のキーを指定された値にマップする場合に true を返します。
Set<Map.Entry<K,V>>	entrySet() マップ内に保持されているマッピングのセットビューを返します。
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() マップ内に保持されている値のコレクションビューを返します。

クラス 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.compareTo(k2) は、マップ内の任意の要素 k1 と k2 のどちらに対しても ClassCastException をスローすべきではありません。たとえばキーが整数のマップに文字列キーを入れようとするなど、ユーザがこの制約に違反するキーをマップに入れようとすると、put(Object key, Object value) の呼び出しが ClassCastException をスローします。

関連項目:

Comparable

TreeMap

public TreeMap(Comparator<? super K> c)

指定されたコンパレータに従ってソートされた、新しい空のマップを作成します。マップに挿入されたすべてのキーは、指定されたコンパレータによって「相互に比較可能」である必要があります。つまり、comparator.compare(k1, k2) は、マップ内の任意のキー k1 と k2 のどちらに対しても ClassCastException をスローすべきではありません。ユーザがこの制約に違反するキーをマップに入れようとすると、put(Object key, Object value) の呼び出しが ClassCastException をスローします。

パラメータ:

c - このマップをソートするために使用されるコンパレータ。null 値は、キーの「自然順序付け」を使用することを示す

TreeMap

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

指定されたマップと同じマッピングを持ち、キーの「自然順序付け」に従ってソートされた新しいマップを作成します。新しいマップに挿入されたすべてのキーは Comparable インタフェースを実装する必要があります。さらに、各キーは「相互に比較可能」である必要があります。つまり、k1.compareTo(k2) は、マップ内の任意の要素 k1 と 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)

マップが 1 つ以上のキーを指定された値にマップする場合に true を返します。つまり、マップが (value==null ? v==null : value.equals(v)) のような値 v へのマッピングを 1 つ以上保持している場合にだけ 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 オペレーションを使うと、こうした 2 つの場合を見分けることができます。

定義:

インタフェース 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 - Map が空の場合

lastKey

public K lastKey()

ソートマップ内に現在ある最後 (上端) のキーを返します。

定義:

インタフェース SortedMap<K,V> 内の lastKey

戻り値:

ソートマップ内に現在ある最後 (上端) のキー

例外:

NoSuchElementException - Map が空の場合

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 に反映され、その逆の場合も同様です。Set は要素の削除をサポートします。この削除では、Iterator.remove、Set.remove、removeAll、retainAll、clear の各オペレーションを使って対応するマッピングをマップから削除します。Set は、add オペレーションや addAll オペレーションはサポートしていません。

定義:

インタフェース Map<K,V> 内の keySet

オーバーライド:

クラス AbstractMap<K,V> 内の keySet

戻り値:

TreeMap に含まれているキーのセットビュー

values

public Collection<V> values()

マップ内に保持されている値のコレクションビューを返します。コレクションの反復子は、各値を対応するキーがツリーに表示される順序で返します。コレクションは TreeMap のインスタンスに基づいており、マップへの変更はコレクションに反映され、その逆も同様です。コレクションは要素の削除をサポートします。この削除では、Iterator.remove、Collection.remove、removeAll、retainAll、clear の各オペレーションを使って対応するマッピングをマップから削除します。コレクションは、add オペレーションや addAll オペレーションはサポートしていません。

定義:

インタフェース Map<K,V> 内の values

オーバーライド:

クラス AbstractMap<K,V> 内の values

戻り値:

マップ内に含まれている値のコレクションビュー

entrySet

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

マップ内に保持されているマッピングのセットビューを返します。セットの反復子は、マッピングをキーの昇順で返します。返されるセットの各要素は Map.Entry です。セットはこのマップに基づいており、マップへの変更はセットに反映され、その逆も同様です。セットは要素の削除をサポートします。この削除では、Iterator.remove、Set.remove、removeAll、retainAll、clear の各オペレーションを使って対応するマッピングを TreeMap から削除します。Set は、add オペレーションや addAll オペレーションはサポートしていません。

定義:

インタフェース Map<K,V> 内の entrySet

定義:

クラス AbstractMap<K,V> 内の entrySet

戻り値:

マップ内に保持されているマッピングのセットビュー

関連項目:

Map.Entry

subMap

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

マップの fromKey (これを含む) 〜 toKey (これを含まない) のキー範囲を持つ部分のビューを返します。fromKey と toKey が等しい場合は、空のソートマップが返されます。返されるソートマップはマップに基づいており、返されるソートマップでの変更はマップに反映され、その逆の場合も同様です。返されるソートマップは、マップのオプションのオペレーションをすべてサポートします。

このメソッドが返すソートマップは、ユーザが fromKey より小さいキーまたは toKey と同じかこれより大きいキーを挿入しようとすると IllegalArgumentException をスローします。

注: このメソッドは常に、その下端点は含むが上端点は含まない「片側が開いた範囲」を返します。上下端点を含む「閉じた範囲」が必要で、キーの型により直後のキーが計算可能になる場合、単に lowEndpoint 〜 successor(highEndpoint) の部分範囲を指定してください。たとえば、m が文字列のキーを持つソートマップである場合、次の慣用法は、キーが low 〜 high の範囲 (上下端点を含む) にある m 内のすべてのキーと値のマッピングを保持するビューを取得します。

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

同様のテクニックを使って、上下端点のどちらも含まない「開いた範囲」を生成できます。次の慣用法は、キーが low 〜 high の範囲 (上下端点を含まない) にある m 内のすべてのキーと値のマッピングを保持するビューを取得します。

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

定義:

インタフェース SortedMap<K,V> 内の subMap

パラメータ:

fromKey - subMap の下端点 (これを含む)

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 が文字列のキーを持つソートマップである場合、次の慣用法は、キーが high と同じかこれより小さい m 内のすべてのキー値マッピングを保持するビューを取得します。

     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) によって限界を設けられた tailMap を指定してください。たとえば、m はそのキーが文字列のソートマップである場合、次の慣用法は、キーが low より大きい m 内のすべてのキーと値のマッピングを保持するビューを取得します。

     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 キーを許容しないとき