Sun JDKクラスライブラリ学習(四)集合クラスにおけるMap
HashMap
HashMapのソースコード:http://blog.csdn.net/lengyuhong/archive/2010/10/29/5973703.aspx
JDKでのHashMapの概要:
ハッシュ表に基づくMapインタフェースの実装.このインプリメンテーションでは、オプションのマッピング操作がすべて提供され、null値とnullキーを使用できます.(非同期化とnullの使用が許可されている場合を除き、HashMapクラスはHashtableとほぼ同じです.)このようなマッピングの順序は保証されません.特に、この順序が恒久的に変わらないことは保証されません.
この実装は、ハッシュ関数が各バケツ間に要素を適切に分布すると仮定し、基本動作(getおよびput)に安定した性能を提供することができる.collectionビューを反復するのに要する時間は、HashMapインスタンスの「容量」(バケツの数)とそのサイズ(キー値マッピング関係数)に比例します.したがって、反復パフォーマンスが重要な場合は、初期容量をあまり高く設定しない(またはロードファクタを低く設定しない).
HashMapの例には、初期容量とロードファクタの2つのパラメータがあります.容量はハッシュ・テーブルのバケツの数であり、初期容量はハッシュ・テーブルの作成時の容量にすぎない.ロードファクタは、ハッシュ・テーブルが容量が自動的に増加する前に、マルチフルに達することができるスケールです.ハッシュ・テーブルのエントリ数がロード・ファクタと現在の容量の積を超えている場合、ハッシュ・テーブルはrehash操作(すなわち、内部データ構造の再構築)され、ハッシュ・テーブルは約2倍のバケツ数を有する.
通常、デフォルトのロードファクタ(.75)は、時間および空間コストのトレードオフを求めます.ロードファクタが高すぎると、スペースオーバーヘッドが削減されますが、クエリーコストも増加します(多くのHashMapクラスの操作では、getやput操作を含めて、この点が反映されています).初期容量を設定するときは、rehash操作回数を最小限に抑えるために、マッピングに必要なエントリ数とそのロード係数を考慮する必要があります.初期容量が最大エントリ数をロードファクタで割った場合、rehash操作は発生しません.
多くのマッピング関係がHashMapインスタンスに格納される場合、テーブルの容量を増やすために必要に応じて自動的なrehash操作を実行するよりも、十分な初期容量を使用して作成すると、マッピング関係がより効率的に格納されます.
このインプリメンテーションは同期されていないことに注意してください.複数のスレッドが同時に1つのハッシュマッピングにアクセスし、少なくとも1つのスレッドが構造的にマッピングを変更した場合、外部同期を維持する必要があります.(構造上の変更とは、1つ以上のマッピング関係を追加または削除する操作です.インスタンスにすでに含まれているキーに関連付けられている値のみを変更するのは、構造上の変更ではありません.)これは、マッピングを自然にカプセル化したオブジェクトを同期することによって一般的に行われます.このようなオブジェクトが存在しない場合、
このようなcollectionビューメソッドのすべてから返される反復器は、反復器が作成された後、反復器自体のremoveメソッドを使用しない限り、構造的にマッピングを変更すると、反復器は
反復器の急速な失敗挙動は保証されず、一般的に非同期の同時修正がある場合、いかなる断固たる保証もできないことに注意してください.高速障害反復器は、C o n c u r r r e ntModificationExceptionを放出するために最善を尽くします.したがって、この例外に依存するプログラムを記述する方法は間違っており、反復器の迅速な失敗行為は、プログラムエラーの検出にのみ使用されるべきであることが正しい.
注意点:
HashMapはkey,valueからなるEntryオブジェクトを配列方式で格納し,容量制限なし
HashMapはkey hashに基づいてEntryオブジェクトが配列に格納されている場所を探し,hash競合に対してチェーンテーブルで解決する.
HashMapは、要素を挿入するときに配列の容量を拡張し、容量を拡大するときにhashを再計算し、新しい配列にオブジェクトをコピーする必要があります.
HashMapは非スレッドで安全です
TreeMap
TreeMapのソースコード:http://blog.csdn.net/lengyuhong/archive/2010/10/29/5973715.aspx
レッドブラックツリーに基づく
このインプリメンテーションは、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つまたは複数のマッピング関係を追加または削除する操作です.既存のキーに関連付けられた値のみを変更するのは、構造上の変更ではありません.)これは、一般に、マッピングを自然にカプセル化したオブジェクトに対して同期操作を実行することによって行われます.このようなオブジェクトが存在しない場合、
collection(このクラスのすべての「collectionビューメソッド」から返される)のiteratorメソッドが返す反復器は、反復器の作成後、反復器自体のremoveメソッドを使用しない限り、構造的にマッピングを変更すると、反復器が
反復器の急速な失敗は保証されず、一般的には、非同期の同時修正がある場合、肯定的な保証はできません.高速障害反復器は、C o n c u r r r e ntModificationExceptionを放出するために最善を尽くします.したがって、この例外に依存するプログラムを記述する方法は間違っており、正しくは、反復器の急速な失敗行為はバグの検出にのみ使用されるべきである.
このようなメソッドとそのビュー内のメソッドが返すすべてのMap.Entryペアは、それらを生成するときのマッピング関係のスナップショットを表します.Entry.setValueメソッドはサポートされていません.(ただし、putを使用して関連マッピングのマッピング関係を変更することは可能であることに注意してください.)
注意点:
TreeMapは赤と黒のツリーに基づいて実現され、容量制限がない
TreeMapは非スレッドで安全です
HashMapのソースコード:http://blog.csdn.net/lengyuhong/archive/2010/10/29/5973703.aspx
JDKでのHashMapの概要:
ハッシュ表に基づくMapインタフェースの実装.このインプリメンテーションでは、オプションのマッピング操作がすべて提供され、null値とnullキーを使用できます.(非同期化とnullの使用が許可されている場合を除き、HashMapクラスはHashtableとほぼ同じです.)このようなマッピングの順序は保証されません.特に、この順序が恒久的に変わらないことは保証されません.
この実装は、ハッシュ関数が各バケツ間に要素を適切に分布すると仮定し、基本動作(getおよびput)に安定した性能を提供することができる.collectionビューを反復するのに要する時間は、HashMapインスタンスの「容量」(バケツの数)とそのサイズ(キー値マッピング関係数)に比例します.したがって、反復パフォーマンスが重要な場合は、初期容量をあまり高く設定しない(またはロードファクタを低く設定しない).
HashMapの例には、初期容量とロードファクタの2つのパラメータがあります.容量はハッシュ・テーブルのバケツの数であり、初期容量はハッシュ・テーブルの作成時の容量にすぎない.ロードファクタは、ハッシュ・テーブルが容量が自動的に増加する前に、マルチフルに達することができるスケールです.ハッシュ・テーブルのエントリ数がロード・ファクタと現在の容量の積を超えている場合、ハッシュ・テーブルはrehash操作(すなわち、内部データ構造の再構築)され、ハッシュ・テーブルは約2倍のバケツ数を有する.
通常、デフォルトのロードファクタ(.75)は、時間および空間コストのトレードオフを求めます.ロードファクタが高すぎると、スペースオーバーヘッドが削減されますが、クエリーコストも増加します(多くのHashMapクラスの操作では、getやput操作を含めて、この点が反映されています).初期容量を設定するときは、rehash操作回数を最小限に抑えるために、マッピングに必要なエントリ数とそのロード係数を考慮する必要があります.初期容量が最大エントリ数をロードファクタで割った場合、rehash操作は発生しません.
多くのマッピング関係がHashMapインスタンスに格納される場合、テーブルの容量を増やすために必要に応じて自動的なrehash操作を実行するよりも、十分な初期容量を使用して作成すると、マッピング関係がより効率的に格納されます.
このインプリメンテーションは同期されていないことに注意してください.複数のスレッドが同時に1つのハッシュマッピングにアクセスし、少なくとも1つのスレッドが構造的にマッピングを変更した場合、外部同期を維持する必要があります.(構造上の変更とは、1つ以上のマッピング関係を追加または削除する操作です.インスタンスにすでに含まれているキーに関連付けられている値のみを変更するのは、構造上の変更ではありません.)これは、マッピングを自然にカプセル化したオブジェクトを同期することによって一般的に行われます.このようなオブジェクトが存在しない場合、
Collections.synchronizedMapメソッドを使用してマッピングを「パッケージ」する必要があります.以下に示すように、マッピングへの予期しない非同期アクセスを防止するために、作成時にこの操作を完了することが望ましい. Map m = Collections.synchronizedMap(new HashMap(...));このようなcollectionビューメソッドのすべてから返される反復器は、反復器が作成された後、反復器自体のremoveメソッドを使用しない限り、構造的にマッピングを変更すると、反復器は
ConcurrentModificationExceptionを放出します.したがって、反復器は、将来の不確定な時間に任意の不確定な行為が発生するリスクを冒さずに、同時修正に直面してすぐに完全に失敗する.反復器の急速な失敗挙動は保証されず、一般的に非同期の同時修正がある場合、いかなる断固たる保証もできないことに注意してください.高速障害反復器は、C o n c u r r r e ntModificationExceptionを放出するために最善を尽くします.したがって、この例外に依存するプログラムを記述する方法は間違っており、反復器の迅速な失敗行為は、プログラムエラーの検出にのみ使用されるべきであることが正しい.
注意点:
HashMapはkey,valueからなるEntryオブジェクトを配列方式で格納し,容量制限なし
HashMapはkey hashに基づいてEntryオブジェクトが配列に格納されている場所を探し,hash競合に対してチェーンテーブルで解決する.
HashMapは、要素を挿入するときに配列の容量を拡張し、容量を拡大するときにhashを再計算し、新しい配列にオブジェクトをコピーする必要があります.
HashMapは非スレッドで安全です
TreeMap
TreeMapのソースコード:http://blog.csdn.net/lengyuhong/archive/2010/10/29/5973715.aspx
レッドブラックツリーに基づく
NavigableMapが実現される.マッピングは、そのキーの自然な順序に従ってソートされるか、またはマッピングの作成時に提供されるComparatorに従ってソートされる.このインプリメンテーションは、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.synchronizedSortedMapメソッドを使用してマッピングを「パッケージ」する必要があります.以下に示すように、マッピングへの予期しない非同期アクセスを防止するために、作成時にこの操作を完了することが望ましい. SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));collection(このクラスのすべての「collectionビューメソッド」から返される)のiteratorメソッドが返す反復器は、反復器の作成後、反復器自体のremoveメソッドを使用しない限り、構造的にマッピングを変更すると、反復器が
ConcurrentModificationExceptionを放出する可能性があります.したがって、反復器は、将来の不確定な時間に不確定な動作が発生するリスクを冒すことなく、同時修正に対してすぐに完全に失敗する.反復器の急速な失敗は保証されず、一般的には、非同期の同時修正がある場合、肯定的な保証はできません.高速障害反復器は、C o n c u r r r e ntModificationExceptionを放出するために最善を尽くします.したがって、この例外に依存するプログラムを記述する方法は間違っており、正しくは、反復器の急速な失敗行為はバグの検出にのみ使用されるべきである.
このようなメソッドとそのビュー内のメソッドが返すすべてのMap.Entryペアは、それらを生成するときのマッピング関係のスナップショットを表します.Entry.setValueメソッドはサポートされていません.(ただし、putを使用して関連マッピングのマッピング関係を変更することは可能であることに注意してください.)
注意点:
TreeMapは赤と黒のツリーに基づいて実現され、容量制限がない
TreeMapは非スレッドで安全です