JavaTM 2 Platform
Std. Ed. v1.3

java.util
クラス TreeMap

java.lang.Object
  |
  +--java.util.AbstractMap
        |
        +--java.util.TreeMap
すべての実装インタフェース:
Cloneable, Map, Serializable, SortedMap

public class TreeMap
extends AbstractMap
implements SortedMap, Cloneable, Serializable

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

この実装は、containsKeygetputremove の各オペレーションに保証済みの 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 をスローします。したがって、同時に変更が行われると、反復子は、将来の予測できない時点において予測できない動作が発生する危険を回避するために、直ちにかつ手際よく例外をスローします。

導入されたバージョン:
1.2
関連項目:
Map, HashMap, Hashtable, Comparable, Comparator, Collection, Collections.synchronizedMap(Map), 直列化された形式

クラス java.util.Map から継承した内部クラス
Map.Entry
 
コンストラクタの概要
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) は、マップ内の任意の要素 k1k2 のどちらに対しても ClassCastException をスローすべきではありません。たとえばキーが整数のマップに文字列キーを入れようとするなど、ユーザがこの制約に違反するキーをマップに入れようとすると、put(Object key, Object value) の呼び出しが ClassCastException をスローします。
関連項目:
Comparable

TreeMap

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

TreeMap

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

TreeMap

public TreeMap(SortedMap m)
指定の SortedMap と同じマッピングを持ち、同じ順序付けに従ってソートされた、新しいマップを作成します。このメソッドは、線形時間で実行されます。
パラメータ:
m - マッピングがこのマップに配置され、コンパレータがこのマップのソートに使用される、ソートされたマップ
メソッドの詳細

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 にあるかどうかを判定される値
導入されたバージョン:
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 である場合

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
戻り値:
指定されたキーに関連関連付けられる値。または、キーのマッピングがなかった場合は null。戻り値 null は、マップが以前に null と指定されたキーを関連付けていたことを示す場合もある
例外:
ClassCastException - キーがマップ内に現在あるキーと比較できない場合
NullPointerException - キーが null の場合に、マップが自然順序付けを使うとき、あるいはそのコンパレータが null キーを許容しないとき

clear

public void clear()
TreeMap からすべてのマッピングを削除します。
定義:
インタフェース Map 内の clear
オーバーライド:
クラス AbstractMap 内の clear
インタフェース java.util.Map からコピーされたタグ:
例外:
UnsupportedOperationException - clear がマップによってサポートされていない場合

clone

public Object clone()
TreeMap のインスタンスのシャローコピーを返します。そのキーと値は複製されません。
オーバーライド:
クラス Object 内の clone
戻り値:
この Map のシャローコピー

keySet

public Set keySet()
マップ内に保持されているキーの Set ビューを返します。セットの反復子は、キーを昇順で返します。マップは TreeMap のインスタンスに基づいており、マップへの変更は Set に反映され、その逆の場合も同様です。Set は要素の削除をサポートします。この削除では、Iterator.removeSet.removeremoveAllretainAllclear の各オペレーションを使って対応するマッピングをマップから削除します。Set は、add オペレーションや addAll オペレーションはサポートしていません。
定義:
インタフェース Map 内の keySet
オーバーライド:
クラス AbstractMap 内の keySet
戻り値:
TreeMap に含まれているキーのセットビュー

values

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

entrySet

public Set entrySet()
マップ内に保持されているマッピングのセットビューを返します。セットの反復子は、マッピングをキーの昇順で返します。返されるセットの各要素は Map.Entry です。セットはこのマップに基づいており、マップへの変更はセットに反映され、その逆も同様です。セットは要素の削除をサポートします。この削除では、Iterator.removeSet.removeremoveAllretainAllclear の各オペレーションを使って対応するマッピングを TreeMap から削除します。Set は、add オペレーションや addAll オペレーションはサポートしていません。
定義:
インタフェース Map 内の entrySet
オーバーライド:
クラス AbstractMap 内の entrySet
戻り値:
マップ内に保持されているマッピングのセットビュー
関連項目:
Map.Entry

subMap

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

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

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

    SortedMap sub = m.submap(low, high+"\0");
同様のテクニックを使って、上下端点のどちらも含まない「開いた範囲」を生成できます。次の慣用法は、キーが lowhigh の範囲 (上下端点を含まない) にある m 内のすべてのキーと値のマッピングを保持するビューを取得します。
    SortedMap sub = m.subMap(low+"\0", high);
定義:
インタフェース SortedMap 内の subMap
パラメータ:
fromKey - subMap の下端点 (これを含む)
toKey - subMap の上端点 (これを含まない)
戻り値:
マップの fromKey (これを含む) から toKey (これを含まない) のキー範囲を持つ部分のビュー
例外:
ClassCastException - マップのコンパレータを使用して、fromKeytoKey を相互に比較できない場合 (または、マップに自然順序付けを使用するコンパレータがない場合)
IllegalArgumentException - fromKeytoKey より大きい場合
NullPointerException - fromKey または toKeynull の場合に、マップが自然順序付けを使うとき、あるいはそのコンパレータが 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 がマップのコンパレータと互換性がない場合 (または、マップにコンパレータがない場合、toKeyComparable が実装されていない場合)
IllegalArgumentException - このマップ自体が subMap、headMap、または tailMap で、toKey が指定した範囲の subMap、headMap、または tailMap にない場合
NullPointerException - toKeynull の場合に、マップが自然順序付けを使うとき、あるいはそのコンパレータが 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 がマップのコンパレータと互換性がない場合 (または、マップにコンパレータがない場合、fromKeyComparable が実装されていない場合)
IllegalArgumentException - このマップ自体が subMap、headMap、または tailMap で、fromKey が指定した範囲の subMap、headMap、または tailMap にない場合
NullPointerException - fromKeynull の場合に、マップが自然順序付けを使うとき、あるいはそのコンパレータが null キーを許容しないとき

JavaTM 2 Platform
Std. Ed. v1.3

バグや機能要求の報告
さらに詳しい API リファレンスおよび開発者ドキュメントについては、 Java 2 SDK SE Developer Documentation を参照してください。このドキュメントには、概念、用語の定義、回避策、 実用的なコード例など、開発者を対象にした詳細な解説が掲載されています。

Java、Java 2D、JDBC は、米国およびその他の国における米国 Sun Microsystems, Inc. の商標もしくは登録商標です。
Copyright 1993-2000 Sun Microsystems, Inc. 901 San Antonio Road,
Palo Alto, California, 94303, U.S.A. All Rights Reserved.