Java コレクション フレームワーク

Javaコレクションフレームワークは、一般的に再利用可能なコレクションデータ構造を実装するクラスとインターフェースのセットです。^[1]

フレームワークと呼ばれていますが、ライブラリのように機能します。コレクション フレームワークは、さまざまなコレクションを定義するインターフェイスと、それらを実装するクラスの両方を提供します。

Collectionと配列は、どちらもオブジェクトへの参照を保持し、グループとして管理できるという点で似ています。ただし、配列とは異なり、Collectionインスタンス化時に特定の容量を割り当てる必要はありません。Collectionオブジェクトが追加または削除されると、サイズは自動的に拡大または縮小されます。

Collectionintは、、、longなどのプリミティブデータ型を保持できませんdouble。^[2]代わりに、は、、、、などのラッパークラスCollectionを保持できます。^[3]java.lang.Integerjava.lang.Longjava.lang.Double

Collectionはジェネリックであり、したがって不変ですが、配列は共変です。これは、配列と比較した場合のジェネリックオブジェクトの利点と考えることができますCollection。なぜなら、状況によっては、配列の代わりにジェネリックを使用すると、Collection代わりにコンパイル時例外をスローして開発者にコードを修正するように通知することにより、実行時例外を防ぐことができるからです。たとえば、開発者がオブジェクトを宣言しObject[]、特定の容量を持つObject[]新しいインスタンスによって返された値にオブジェクトを割り当てるとLong[]、コンパイル時例外はスローされません。開発者がStringこのLong[]オブジェクトに を追加しようとすると、Javaプログラムは をスローしますArrayStoreException。一方、開発者が の新しいインスタンスを として宣言した場合Collection<Object>、ArrayList<Long>Javaコンパイラは（正しく）コンパイル時例外をスローして、コードが互換性のない間違った型で記述されていることを通知し、潜在的な実行時例外を防止します。開発者は、オブジェクトCollection<Object>としてインスタンス化することでコードを修正できます。コードがJava SE7以降のバージョンを使用している場合、開発者はダイヤモンド演算子^[2]を使用してオブジェクトとしてArrayList<Object>インスタンス化できます。Collection<Object>ArrayList<>

Collectionはジェネリックなので具体化されているが、配列は具体化されていない。^[2]

CollectionJDK 1.2以前のJava プラットフォームの実装には、データ構造クラスがいくつか含まれていましたが、コレクション フレームワークは含まれていませんでした。^[4] Java オブジェクトをグループ化する標準的な方法は、配列Vector、、Hashtableクラスを介して行われていましたが、残念ながら拡張が容易ではなく、標準のメンバー インターフェイスを実装していませんでした。^{[5] [より適切なソースが必要]}

再利用可能なコレクションデータ構造の必要性に対応するために、いくつかの独立したフレームワークが開発されました。^[4]最もよく使用されているのはDoug LeaのCollectionsパッケージ、^[6]とObjectSpace Generic Collection Library（JGL）^[7]で、その主な目標はC++ 標準テンプレートライブラリ（STL）との一貫性でした。^{[8] [より良いソースが必要]}

コレクションフレームワークは主にJoshua Blochによって設計・開発され、JDK 1.2で導入されました。Doug LeaのCollectionsパッケージから多くのアイデアとクラスを再利用しましたが、その結果として非推奨となりました。^[6] Sun Microsystemsはコンパクトなフレームワークを望んでいたため、C++との一貫性は目標の1つではなかったため、JGLのアイデアを使用しないことを選択しました。^{[9] [より良いソースが必要]}

Doug Leaは後に、新しいコレクション関連のクラスを含む並行性 パッケージを開発しました。^[10]これらの並行性ユーティリティの更新バージョンは、JSR 166の時点でJDK 5.0に含まれていました。

Java のほぼすべてのコレクションは、java.util.Collectionインターフェースから派生しています。Collectionすべてのコレクションの基本部分を定義します。

インターフェースには、に要素を追加したり、 から要素を削除したりするための メソッドadd(E e)とメソッドがあります。また、を 内の要素の配列に変換する メソッドもあります(戻り値の型は です)。^[11]最後に、 メソッドは に指定された要素が存在するかどうかを確認します。 remove(E e)CollectiontoArray()CollectionObjectCollectionObject[]contains(E e)Collection

インターフェースCollectionは のサブインターフェースなjava.lang.Iterableので、任意の をfor-eachCollection文のターゲットにすることができます。(インターフェースは、 for-each 文で使用される メソッドを提供します。) すべての には、 内のすべての要素を通過する があります。 Iterableiterator()Collectionjava.util.IteratorCollection

Collectionはジェネリックです。任意Collectionの を格納できますObject。たとえば、 の任意の実装にはオブジェクトがCollection<String>含まれます。の実装からオブジェクトをString使用する場合、キャストは必要ありません。^[12]山括弧には、が保持する型を指定する型引数を含めることができることに注意してください。^[13]StringCollection<String>< >Collection

キュー、マップ、リスト、セットなどCollection、いくつかの一般的なタイプがあります。

キューを使用すると、プログラマーは特定の順序でアイテムを挿入し、同じ順序でそれらのアイテムを取得できます。例としては、待機リストがあります。キューの基本インターフェイスは と呼ばれますQueue。

辞書/マップは、オブジェクトの値にアクセスするための検索キーを持つオブジェクトへの参照を格納します。キーの 1 つの例は、ID カードです。辞書/マップの基本インターフェイスは と呼ばれますMap。

リストは、同じ値を複数回保存できる有限のコレクションです。

集合は順序のないコレクションで、反復処理が可能で、各要素を最大1回しか含みません。集合の基本インターフェースはと呼ばれますSet。^[3]

リストは、コレクション フレームワークでインターフェイスを介して実装されますjava.util.List。リストは、本質的には配列のより柔軟なバージョンとして定義されます。要素には特定の順序があり、重複する要素が許可されます。要素は特定の位置に配置できます。また、リスト内で検索することもできます。

とその対応するすべてのサブクラス、およびListを含む、を実装する具体的なクラスがいくつかあります。 AbstractListCopyOnWriteArrayList

AbstractListクラスの直接のサブクラスにはAbstractSequentialList、、ArrayListおよびが含まれますVector。

AbstractListはスケルトン実装の一例であり、インターフェースと抽象クラスの利点を活用して組み合わせることで、開発者が特定のインターフェースに対して独自の実装を簡単に開発できるようにしています。^[14]

クラスjava.util.ArrayListは をList配列として実装します。 に固有の関数がList必要な場合は、クラスはそれを実行するため、配列内の要素を移動します。

クラスjava.util.LinkedListは、それぞれがクラス内の前のノードと次のノードへのポインタを持つノードに要素を格納しますList。クラスはListポインタをたどることで走査でき、ポインタを変更してノードを適切な場所に配置するだけで要素を追加または削除できます。^[15]

このVectorクラスには直接のサブクラスがあります。これは、 Javaプラットフォームライブラリの継承よりも構成Stackの原則に違反する例です。コンピュータサイエンスでは、ベクトルは一般にスタックではないためです。^[16]このシナリオでは、構成の方が適切でした。^[16]

Stack クラスextendsには、を として扱うjava.util.Vectorことができる 5 つの操作があります。スタックは を使用して作成されます。 は、新しいオブジェクトを に配置するメソッド(メソッド) と、 からオブジェクトを取得するメソッド(メソッド) を提供します。 は、後入れ先出し(LIFO)に従ってオブジェクトを返します。つまり、 に最後に配置されたオブジェクトが最初に返されます。は、Java が提供するスタックの標準実装です。 VectorStackjava.util.StackStackStackpush(E e)Stackpop()StackStackjava.util.Stack

クラスStackは、オブジェクトの後入れ先出し (LIFO) スタックを表します。Stack クラスには、Vectorを として扱うことができる 5 つの追加操作がありますStack。通常の操作push(E e)とpop()操作の他に、 のpeek()一番上の項目を確認するメソッド ( )、Stackが空かどうかをテストするメソッドStack( )、 で項目を検索し、それが一番上からどのくらい離れているかを調べるempty()メソッド( ) が提供されています。 が最初に作成されたときは、項目は含まれていません。 Stacksearch(Object o)Stack

はクラスCopyOnWriteArrayListを拡張しObject、他のクラスを拡張しません。CopyOnWriteArrayList過剰な同期を実行せずにスレッドセーフを可能にします。^[17]

いくつかのシナリオでは、同期は必須です。たとえば、メソッドが静的フィールドを変更し、そのメソッドが複数のスレッドから呼び出される必要がある場合、同期は必須であり、などの並行性ユーティリティはCopyOnWriteArrayList使用しないでください。^[17]

しかし、同期はパフォーマンスのオーバーヘッドを引き起こす可能性があります。同期が必須でないシナリオでは、マルチコアプロセッサを活用し、 CPU使用率を高める、同期に代わるCopyOnWriteArrayList実行可能なスレッドセーフな代替手段があります。 ^[17]

インターフェイスjava.util.Queueは、挿入された順序で要素を格納するキュー データ構造を定義します。新しく追加された要素は行の末尾に移動し、要素は先頭から削除されます。これは先入先出システムを作成します。このインターフェイスはjava.util.LinkedList、、、java.util.ArrayDequeおよびによって実装されますjava.util.PriorityQueue。

AbstractQueueクラスの 直接 のサブクラスにはArrayBlockingQueue、、、、、、など があります。 ConcurrentLinkedQueueDelayeQueueLinkedBlockingDequeLinkedBlockingQueueLinkedTransferQueuePriorityBlockingQueue

ArrayDequeと はConcurrentLinkedDeque両方とも を拡張しますAbstractCollectionが、 などの他の抽象クラスは拡張しないことに注意してくださいAbstractQueue。

AbstractQueueスケルトン実装の例です。

クラスjava.util.PriorityQueueはを実装するjava.util.Queueだけでなく、それを変更します。^[18] PriorityQueueには追加のcomparator()メソッドがあります。^[18]要素は挿入された順序で並べられるのではなく、優先順位で並べられます。優先順位を決定するために使用されるメソッドは、java.lang.Comparable#compareTo(T)要素内のメソッド、またはコンストラクタで指定されたメソッドのいずれかです。クラスは、アイテムをソートした状態に保つためにヒープを使用してこれを作成します。^[19]

クラスjava.util.concurrent.ConcurrentLinkedQueueはを拡張し、インターフェースを実装します。^[20]java.util.AbstractQueueConcurrentLinkedQueuejava.util.Queue

クラスConcurrentLinkedQueueはスレッドセーフなコレクションです。これは、クラス内に配置された任意の要素についてConcurrentLinkedQueue、Javaコレクションライブラリが、任意のスレッドがコレクションから要素を取得できるようにすることで、要素が安全に公開されることを保証するためです。 ^[21]オブジェクトの状態が同時に他のすべてのスレッドに見える場合、そのオブジェクトは安全に公開されていると言われます。 ^[21]安全な公開には通常、公開スレッドと消費スレッドの同期が必要です。^[21]

インターフェース java.util.concurrent.BlockingQueueはを拡張しますQueue。^[20]

インターフェースBlockingQueueには、次の直接サブインターフェースがあります:BlockingDequeおよびTransferQueue。BlockingQueue通常の のように動作しますQueueが、 への追加と からの削除はBlockingQueueブロッキングです。^[22]remove(Object o)が空の で呼び出された場合 BlockingQueue、 にアイテムが表示されるまで指定された時間または無期限に待機するように設定できますBlockingQueue。同様に、 メソッドを使用してアイテムを追加すると、add(Object o)のオプションの容量制限が適用されBlockingQueue、 メソッドは に戻る前に にスペースが空くのを待つことができますBlockingQueue。インターフェースは、の先頭を削除して取得し、必要に応じて が空でなくなるまで待機するBlockingQueueメソッドを導入します。 ^{[23] [24]}take()BlockingQueueBlockingQueue

インターフェースはインターフェースDequeを拡張しますQueue。^{[25] は} Deque両端キューを作成します。通常のキューではQueue後ろへの挿入と前への削除のみが許可されますが、ではDeque前と後ろの両方で挿入または削除を行うことができます。 は前方または後方、または両方を同時に使用できる にDeque似ていますQueue。さらに、前方イテレータと後方イテレータの両方を生成できます。インターフェースはとDequeによって実装されます。^[26]java.util.ArrayDequejava.util.LinkedList

LinkedListもちろん、 もListインターフェースを実装しており、インターフェースとして使用することもできます。しかし、Queueメソッドも持っています。はインターフェースLinkedListを実装しておりjava.util.Deque、より柔軟性があります。^[27]

ArrayDequeQueueは配列として実装します。 と同様にLinkedList、ArrayDequeもjava.util.Dequeインターフェースを実装します。^[27]

インターフェースjava.util.concurrent.BlockingDequeは を拡張しますjava.util.concurrent.BlockingQueue。^[25] BlockingDequeは に似ていますBlockingQueue。 は、挿入または削除が可能になるまで待機するための時間制限付きの挿入と削除の同じメソッドを提供します。 ただし、 インターフェースは の柔軟性も提供しますDeque。 挿入と削除は両端で行うことができます。 ブロッキング機能は 機能と組み合わされていますDeque。^[28]

Java のjava.util.Setインターフェースは を定義しますSet。Setには重複する要素を含めることはできません。また、Setには順序が設定されていません。そのため、要素をインデックスで検索することはできません。 は、、Setによって実装されます。 java.util.HashSetjava.util.LinkedHashSetjava.util.TreeSet

Set インターフェースには、AbstractSetとそのサブクラス、および最終的な静的内部クラス(ここで、 とは正式な型パラメータ) を含む複数の実装があります。 ConcurrentHashMap.KeySetView<K,V>KV

AbstractSetインターフェースの骨格実装であるSet。^[14]

の直接 のサブクラスには、、、、が含まれAbstractSetます。ConcurrentSkipListSetCopyOnWriteArraySetEnumSetHashSetTreeSet

クラスEnumSetはを拡張しますAbstractSet。EnumSetクラスにはパブリックコンストラクタはなく、静的ファクトリメソッドのみが含まれます。^[29]

EnumSetには静的ファクトリメソッドが含まれています。^[30]このメソッドは集約メソッドです。^[29]このメソッドは複数のパラメータを受け取り、パラメータの型を考慮して、適切な型のインスタンスを返します。^[29] 2018年現在、Java SE8のOpenJDK実装では、クライアントからは見えない2つの実装、およびが使用されています。^[29]が小さな列挙型に対してパフォーマンス上の利点をもたらさなくなった場合は、Javaコレクションライブラリに悪影響を与えることなくライブラリから削除できます。^[29]EnumSet.of()EnumSetRegularEnumSetJumboEnumSetRegularEnumSet

EnumSetは、以下に説明する集合の一種であるビットフィールドの良い代替物である。 ^[30]

従来、開発者は列挙型の要素をセットに配置する必要がある場合は常に、すべての定数に異なる2の累乗を割り当てるint enumパターンを使用していました。 ^{[30]このビット表現により、開発者はビットごとのOR演算を使用できるため、定数を}ビットフィールドとも呼ばれるセットに組み合わせることができます。このビットフィールド表現により、開発者は効率的なセットベースの演算や、交差や結合などのビットごとの算術演算を行うことができます。^[30]

しかし、ビットフィールド表現アプローチには多くの問題があります。ビットフィールドはint enum定数よりも読みにくくなります。^[30]また、要素がビットフィールドで表現されている場合、これらすべての要素を反復処理することは不可能です。^[30]

推奨される代替アプローチは、ビットフィールドのEnumSet代わりに int enum を使用する を使用することです。^[30]このアプローチでは、 を使用して同じ型に属する値のセットを表します。^[30]はインターフェイスを実装し、ビット単位の演算を使用する必要がなくなったため、このアプローチはより型安全です。 ^[30]さらに、メソッド メソッドなど、オブジェクトのインスタンス化を可能にする静的ファクトリが多数あります。^[30]EnumSetEnumEnumSetSetEnumSet.of()

の導入後EnumSet、ビットフィールド表現アプローチは時代遅れになったと考えられています。^[30]

HashSetハッシュ テーブルを使用します。具体的には、java.util.LinkedHashMapハッシュと要素を保存し、重複を防ぐために を使用します。

このjava.util.LinkedHashSetクラスは、HashSetすべての要素を挿入順序でリンクする二重リンク リストを作成することによって拡張されます。これにより、反復順序Setが予測可能になります。

CopyOnWriteArraySetは、同期された の並行置換です。 が同期された の並行置換として機能するSetのと同様に、反復中に同期を実行したりオブジェクトのコピーを作成したりする必要がなくなるため、多くの状況で並行性が向上します。^[31] 一方、 と同様に、同期が必須の場合は を使用しないでください。 CopyOnWriteArrayListListCopyOnWriteArrayListCopyOnWriteArraySet

インターフェースはインターフェースjava.util.SortedSetを拡張しますjava.util.Set。通常の とは異なりSet、 内の要素はSortedSet、要素のcompareTo(T o)メソッド、または のコンストラクタに提供される メソッドによってソートされますSortedSet。 の最初と最後の要素は、それぞれとメソッドSortedSetを使用して取得でき、最小値と最大値、および の先頭または末尾で開始または終了することによってサブセットを作成できます。クラスはインターフェースを実装します。^[32]first()last()SortedSetjava.util.TreeSetSortedSet

インターフェースはインターフェースjava.util.NavigableSetを拡張しjava.util.SortedSet、いくつかの追加メソッドを持ちます。floor(E e)、、、およびメソッドは、パラメータに近いセット内の要素を検索します。さらに、 内の項目に対する降順反復子が提供されます。 と同様に、は を実装します。^[33]ceiling(E e)lower(E e)higher(E e)SetSortedSetjava.util.TreeSetNavigableSet

java.util.TreeSetは、によって実装された赤黒木を使用しますjava.util.TreeMap。赤黒木は重複がないことを保証します。さらに、TreeSetを実装することもできますjava.util.SortedSet。^[34]

ConcurrentSkipListSetは、同期された実装の並行置換として機能しますSortedSet。たとえば、メソッドTreeSetによってラップされたを置き換えますsynchronizedMap。^[35]

java.util.MapマップはJava のインターフェース によって定義されます。

マップは、キーを要素に関連付けるデータ構造です。これにより、マップは非常に柔軟になります。キーが要素のハッシュ コードである場合、 はMap基本的に ですSet。キーが増加するだけの数値である場合は、リストになります。

Map実装の例としてはjava.util.HashMap、、、java.util.LinkedHashMapなどがありますjava.util.TreeMap。

AbstractMapはスケルトン実装の一例である。^[14]

AbstractMapクラスの直接 のサブクラスにはConcurrentSkipListMap、、、、、およびが含まれます。EnumMapHashMapIdentityHashMapTreeMapWeakHashMap

EnumMapを拡張しますAbstractMap。EnumMap順序付きインデックス配列と同等の速度を持ちます。 [ ^{36 ]}EnumMapこれは、内部的に配列を使用し、実装の詳細を開発者から完全に隠蔽しているためです。[36] したがって、EnumMap は配列の型安全性と配列のパフォーマンス上の利点の両方を兼ね備えています。^[36]Map

HashMapハッシュテーブルを使用します。キーのハッシュはさまざまなバケット内の要素を見つけるために使用されます。はHashMapハッシュベースのコレクションです。^[37]

LinkedHashMapは、要素間の二重リンクリストHashMapを作成することによって拡張され、マップに挿入された順序で要素にアクセスできるようになります。 には、新しいキーが に追加されるたびに メソッドによって呼び出される メソッドが含まれています。 ^[38]は、が true を返すたびに、最も古いエントリを削除します。 ^[38]メソッドはオーバーライドできます。^[38]LinkedHashMapprotected removeEldestEntryputMapMapremoveEldestEntryremoveEldestEntry

TreeMapHashMapは、やとは対照的にLinkedHashMap、赤黒木を使用します。キーは木内のノードの値として使用され、ノードは内の要素を指しますMap。^[39]

ConcurrentHashMapはに似ておりHashMap、ハッシュベースのコレクションでもあります。^[37]しかし、使用するロック戦略の違いなど、いくつかの違いがあります。

はConcurrentHashMap、スケーラビリティと並行性を向上させるために、まったく異なるロック戦略を使用します。^[37] ConcurrentHashMapは同じロックを使用するすべてのメソッドを同期しません。^[37]代わりに、ロックストライピングConcurrentHashMapと呼ばれるメカニズムを使用します。^[37]このメカニズムは、より細かい粒度のロックメカニズムを提供します。^[37]また、より高度な共有アクセスを許可します。^[37]

ConcurrentSkipListMapは、同期された の実装の並行置換として機能しますSortedMap。ConcurrentSkipListMapは と非常によく似ておりConcurrentSkipListSet、 はメソッドによってラップされたConcurrentSkipListMapを置き換えます。^[35]TreeMapsynchronizedMap

インターフェースはインターフェースjava.util.SortedMapを拡張しますjava.util.Map。このインターフェースは、Map提供されたキーによってソートされる を定義します。compareTo()のコンストラクタで提供される メソッドまたは メソッドを再度使用してSortedMap、キー要素のペアはキーによってソートされます。 の最初と最後のキーは、それぞれ メソッドとメソッドをMap使用して呼び出すことができます。さらに、 メソッドを使用して、最小キーと最大キーからサブマップを作成することができます。は によって実装されます。^[40]firstKey()lastKey()subMap(K fromKey, K toKey)SortedMapjava.util.TreeMap

インターフェースは様々な方法でjava.util.NavigableMap拡張されますjava.util.SortedMap。メソッドを呼び出して、指定されたキーに最も近いキーまたはマップエントリをいずれかの方向に検索することができます。マップを逆にすることもでき、逆順のイテレータをそこから生成することもできます。これはによって実装されますjava.util.TreeMap。^[41]

インターフェースはインターフェースjava.util.concurrent.ConcurrentMapを拡張しますjava.util.Map。このインターフェースはスレッドセーフインターフェースであり、Javaプログラミング言語のJava Collections Frameworkバージョン1.5Mapで導入されました。 ^[20]

JavaコレクションフレームワークはApache Commons Collectionsライブラリによって拡張され、バッグや双方向マップなどのコレクション型や、和集合や積集合を作成するためのユーティリティが追加されています。^[42]

Google は、 guava ライブラリの一部として独自のコレクション ライブラリをリリースしました。

• コレクション
• 容器
• 標準テンプレートライブラリ
• Java の並行性
• Java コンカレントマップ

• Bloch, Joshua (2018)。『Effective Java: プログラミング言語ガイド』（第 3 版）。Addison- Wesley。ISBN 978-0134685991。
• Goetz, Brian; Peierls, Tim; Bloch, Joshua; Bowbeer , Joseph; Holmes, David; Lea, Doug (2006)。Java Concurrency in Practice。Addison Wesley。ISBN 0-321-34960-1. OL  25208908M.