java.util
クラス TreeMap

java.lang.Object
  java.util.AbstractMap
      java.util.TreeMap

すべての実装されたインタフェース:

Serializable, Cloneable, Map, SortedMap

public class TreeMap
extends AbstractMap
implements SortedMap, 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 c)
指定されたコンパレータに従ってソートされた、新しい空のマップを作成します。

TreeMap(Map m)
指定されたマップと同じマッピングを持ち、そのキーの「自然順序付け」に従ってソートされた新しいマップを作成します。

TreeMap(SortedMap m)
指定された SortedMap と同じマッピングを持ち、同じ順序付けに従ってソートされた、新しいマップを作成します。

メソッドの概要

void	clear() TreeMap からすべてのマッピングを削除します。
Object	clone() TreeMap のインスタンスのシャローコピーを返します。
Comparator	comparator() マップを順序付けするのに使うコンパレータを返します。
boolean	containsKey(Object key) マップが指定のキーのマッピングを保持する場合に true を返します。
boolean	containsValue(Object value) マップが 1 つまたは複数のキーと指定された値をマップしている場合に true を返します。
Set	entrySet() マップ内に保持されているマッピングのセットビューを返します。
Object	firstKey() ソートマップ内に現在ある最初 (下端) のキーを返します。
Object	get(Object key) マップが指定されたキーをマップする値を返します。
SortedMap	headMap(Object toKey) マップの toKey より厳密に小さいキーを持つ部分のビューを返します。
Set	keySet() このマップに含まれているキーの Set ビューを返します。
Object	lastKey() ソートマップ内に現在ある最後 (上端) のキーを返します。
Object	put(Object key, Object value) 指定された値と指定されたキーをこのマップに関連付けます。
void	putAll(Map map) 指定されたマップからすべてのマッピングをマップにコピーします。
Object	remove(Object key) キーのマッピングがあれば TreeMap から削除します。
int	size() マップ内のキー値マッピングの数を返します。
SortedMap	subMap(Object fromKey, Object toKey) マップの fromKey (これを含む) 〜 toKey (これを含まない) のキー範囲を持つ部分のビューを返します。
SortedMap	tailMap(Object fromKey) マップの fromKey 以上のキーを持つ部分のビューを返します。
Collection	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 c)

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

パラメータ:

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

TreeMap

public TreeMap(Map m)

指定されたマップと同じマッピングを持ち、そのキーの「自然順序付け」に従ってソートされた新しいマップを作成します。新しいマップに挿入されたすべてのキーは Comparable インタフェースを実装する必要があります。さらに、各キーは「相互に比較可能」である必要があります。つまり、k1.compareTo(k2) は、マップ内の任意の要素 k1 と k2 のどちらに対しても ClassCastException をスローしてはいけません。このメソッドは、n*log(n) 時間で実行されます。

パラメータ:

m - マッピングがこのマップに配置されるマップ

例外:

ClassCastException - t 内のキーが Comparable でないか、相互に比較可能でない場合

NullPointerException - 指定されたマップが null の場合

TreeMap

public TreeMap(SortedMap m)

指定された SortedMap と同じマッピングを持ち、同じ順序付けに従ってソートされた、新しいマップを作成します。このメソッドは一次時間で動作します。

パラメータ:

m - マッピングがこのマップに配置され、コンパレータがこのマップのソートに使用される、ソートされたマップ

例外:

NullPointerException - 指定されたソートマップが null の場合

メソッドの詳細

size

public int size()

マップ内のキー値マッピングの数を返します。

定義:

インタフェース Map 内の size

オーバーライド:

クラス AbstractMap 内の size

戻り値:

マップ内のキー値マッピングの数

containsKey

public boolean containsKey(Object key)

マップが指定のキーのマッピングを保持する場合に true を返します。

定義:

インタフェース Map 内の containsKey

オーバーライド:

クラス AbstractMap 内の 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 内の containsValue

オーバーライド:

クラス AbstractMap 内の containsValue

パラメータ:

value - Map にあるかどうかを判定される値

戻り値:

value へのマッピングがある場合は true、マッピングがない場合は false

導入されたバージョン:

1.2

get

public Object get(Object key)

マップが指定されたキーをマップする値を返します。マップがこのキーのマッピングを保持していない場合は null を返します。戻り値の null は、マップがキーのマッピングを保持していないことを示すとはかぎりません。 つまり、マップが明示的にキーを null にマップすることもあります。containsKey オペレーションを使うと、こうした 2 つの場合を見分けることができます。

定義:

インタフェース Map 内の get

オーバーライド:

クラス AbstractMap 内の get

パラメータ:

key - 関連付けられている値が返されるキー

戻り値:

マップが、指定されたキーにマップしている値。 キーに対するマッピングがマップにない場合は null

例外:

ClassCastException - キーがマップ内に現在あるキーと比較できない場合

NullPointerException - キーが null で、このマップが自然順序付けを使用する場合、またはそのコンパレータが null キーを許容しないとき

関連項目:

containsKey(Object)

comparator

public Comparator comparator()

マップを順序付けするのに使うコンパレータを返します。ただし、マップがそのキーの自然順序付けを使う場合は null を返します。

定義:

インタフェース SortedMap 内の comparator

戻り値:

ソートマップに関連したコンパレータ。ソートマップがそのキーの自然ソートメソッドを使う場合は null

firstKey

public Object firstKey()

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

定義:

インタフェース SortedMap 内の firstKey

戻り値:

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

例外:

NoSuchElementException - Map が空の場合

lastKey

public Object lastKey()

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

定義:

インタフェース SortedMap 内の lastKey

戻り値:

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

例外:

NoSuchElementException - Map が空の場合

putAll

public void putAll(Map map)

指定されたマップからすべてのマッピングをマップにコピーします。これにより、マップが指定されたマップ内に現在あるキーのすべてに対して持っていたマッピングが置き換えられます。

定義:

インタフェース Map 内の putAll

オーバーライド:

クラス AbstractMap 内の putAll

パラメータ:

map - マップに格納されるマッピング

例外:

ClassCastException - 指定のマップ内のキーまたは値のクラスが、キーまたは値をこのマップ内に格納させないようにする場合

NullPointerException - 指定されたマップが null である場合、またはこのマップが null のキーを許可しないのに、指定されたマップに null が含まれている場合

put

public Object put(Object key,
                  Object value)

指定された値と指定されたキーをこのマップに関連付けます。マップが以前にこのキーのマッピングを保持していた場合、古い値が置き換えられます。

定義:

インタフェース Map 内の put

オーバーライド:

クラス AbstractMap 内の put

パラメータ:

key - 指定の値が関連付けられるキー

value - 指定のキーに関連付けられる値

戻り値:

指定されたキーと関連付けられていた以前の値。キーのマッピングがなかった場合は null。戻り値 null は、マップが以前に null と指定されたキーを関連付けていたことを示す場合もある

例外:

ClassCastException - キーがマップ内に現在あるキーと比較できない場合

NullPointerException - キーが null の場合にこのマップが自然順序付けを使うとき、またはそのコンパレータが null キーを許容しないとき

remove

public Object remove(Object key)

キーのマッピングがあれば TreeMap から削除します。

定義:

インタフェース Map 内の remove

オーバーライド:

クラス AbstractMap 内の remove

パラメータ:

key - マッピングを削除する必要があるキー

戻り値:

指定されたキーと関連付けられていた以前の値。キーのマッピングがなかった場合は null。戻り値 null は、マップが以前に null と指定されたキーを関連付けていたことを示す場合もある

例外:

ClassCastException - キーがマップ内に現在あるキーと比較できない場合

NullPointerException - キーが null の場合にこのマップが自然順序付けを使うとき、またはそのコンパレータが null キーを許容しないとき

clear

public void clear()

TreeMap からすべてのマッピングを削除します。

定義:

インタフェース Map 内の clear

オーバーライド:

クラス AbstractMap 内の clear

clone

public Object clone()

TreeMap のインスタンスのシャローコピーを返します。そのキーと値は複製されません。

オーバーライド:

クラス AbstractMap 内の clone

戻り値:

この Map のシャローコピー

関連項目:

Cloneable

keySet

public Set keySet()

このマップに含まれているキーの Set ビューを返します。セットの反復子は、キーを昇順で返します。マップはこの TreeMap インスタンスと連動しているので、このマップに対する変更は Set 内に反映され、その逆もまた同様です。Set は要素の削除をサポートしており、対応するマッピングをマップから削除できます。削除は、Iterator.remove、Set.remove、removeAll、retainAll、および clear の各オペレーションを通して行います。Set は、add オペレーションや addAll オペレーションはサポートしていません。

定義:

インタフェース Map 内の keySet

オーバーライド:

クラス AbstractMap 内の keySet

戻り値:

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

values

public Collection values()

マップ内に保持されている値のコレクションビューを返します。コレクションの反復子は、対応するキーのツリー内での表示順に従って値を返します。コレクションはこの TreeMap インスタンスと連動しているので、このマップに対する変更はコレクションに反映され、コレクションに対する変更はマップに反映されます。コレクションは要素の削除をサポートしており、対応するマッピングをマップから削除できます。削除は、Iterator.remove、Collection.remove、removeAll、retainAll、および clear の各オペレーションを通して行います。Set は、add オペレーションや addAll オペレーションはサポートしていません。

定義:

インタフェース Map 内の values

オーバーライド:

クラス AbstractMap 内の values

戻り値:

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

entrySet

public Set entrySet()

マップ内に保持されているマッピングのセットビューを返します。セットの反復子は、マッピングをキーの昇順で返します。返されるセットの各要素は Map.Entry です。セットはこのマップと連動しているので、このマップに対する変更はセットに反映され、また、セットに対する変更はマップに反映されます。セットは要素の削除をサポートしており、対応するマッピングを TreeMap から削除できます。削除は、Iterator.remove、Set.remove、removeAll、retainAll、および clear の各オペレーションを通して行います。Set は、add オペレーションや addAll オペレーションはサポートしていません。

定義:

インタフェース Map 内の entrySet

定義:

クラス AbstractMap 内の entrySet

戻り値:

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

関連項目:

Map.Entry

subMap

public SortedMap subMap(Object fromKey,
                        Object 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 内の subMap

パラメータ:

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

toKey - subMap の上端点 (これを含まない)

戻り値:

マップの fromKey (これを含む) から toKey (これを含まない) のキー範囲を持つ部分のビュー

例外:

ClassCastException - このマップのコンパレータを使用して、fromKey と toKey を相互に比較できない場合 (または、マップに自然順序付けを使用するコンパレータがない場合)。

IllegalArgumentException - fromKey が toKey より大きい場合

NullPointerException - fromKey または toKey が null であるのに、このマップが自然順序付けを使用する場合、またはそのコンパレータが null キーを許容しない場合

headMap

public SortedMap headMap(Object toKey)

マップの toKey より厳密に小さいキーを持つ部分のビューを返します。返されるソートマップはこのマップに連動しており、返されるソートマップでの変更はこのマップに反映され、その逆の場合も同様です。返されるソートマップは、オプションのマップオペレーションをすべてサポートします。

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

注:このメソッドは常に、その上端点を含まないビューを返します。この端点を含むビューが必要であり、そのキーの型で、指定されたキーの直後のキーの計算が可能な場合は、単に successor(highEndpoint) により限界を設けられた headMap を要求してください。たとえば、m が、文字列のキーを持つソートマップであるとします。次の慣用法では、キーが high 以下の m 内のすべてのキーと値のマッピングを保持するビューを取得します。

     SortedMap head = m.headMap(high+"\0");
 

定義:

インタフェース SortedMap 内の headMap

パラメータ:

toKey - headMap の上端点 (これを含まない)

戻り値:

マップの toKey より厳密に小さいキーを持つ部分のビュー

例外:

ClassCastException - toKey がこのマップのコンパレータと互換性がない場合 (または、マップにコンパレータがない場合、toKey に Comparable が実装されていない場合)

IllegalArgumentException - このマップ自体が subMap、headMap、または tailMap で、toKey が指定した範囲の subMap、headMap、または tailMap にない場合

NullPointerException - toKey が null の場合に、このマップが自然順序付けを使うとき、またはそのコンパレータが null キーを許容しないとき

tailMap

public SortedMap tailMap(Object fromKey)

マップの fromKey 以上のキーを持つ部分のビューを返します。返されるソートマップはこのマップに連動しており、返されるソートマップでの変更はこのマップに反映され、その逆の場合も同様です。返されるソートマップは、オプションのマップオペレーションをすべてサポートします。

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

注:このメソッドは常に、その下端点を含むビューを返します。この端点を含まないビューを必要とし、その要素の型で、指定された値の直後の値の計算が可能な場合は、単に successor(lowEndpoint) により限界を設けられた tailMap を要求してください。たとえば、m が、文字列のキーを持つソートマップであるとします。次の慣用法では、キーが low より厳密に大きい m 内のすべてのキーと値のマッピングを保持するビューを取得します。

     SortedMap tail = m.tailMap(low+"\0");
 

定義:

インタフェース SortedMap 内の tailMap

パラメータ:

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

戻り値:

マップの fromKey と同じかこれより大きいキーを持つ部分のビュー

例外:

ClassCastException - fromKey がマップのコンパレータと互換性がない場合 (または、マップにコンパレータがない場合、fromKey に Comparable が実装されていない場合)

IllegalArgumentException - このマップ自体が subMap、headMap、または tailMap で、fromKey が指定した範囲の subMap、headMap、または tailMap にない場合

NullPointerException - fromKey が null であるのに、このマップが自然順序付けを使用する場合、またはそのコンパレータが null キーを許容しない場合