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

Revised: Feb./23rd/2003

コレクション・フレームワークとは何か

複数の要素からなるデータの集まりをコレクションと呼びます。コレクションは各々、リスト、セット、ツリー、ハッシュテーブルなどのデータ構造を持ちます。コレクション・フレームワークは J2SDK 1.2 で導入されたもので、JDK 1.2 未満で使われていたコレクション API の後継です。それまでの遅いコレクション・クラスを完全に新しくしたもので、インタフェースをベースに全体が設計されており、これを使うためには、共通のインタフェース・メソッドにのっとることになります。このような全体をフレームワークと呼びます。J2SDK 1.2 で、従来からあるコレクション・クラスも、フレームワークに含まれるものとして再設計されました。

コレクション・フレームワークの概要

万能のアルゴリズム／データ構造はありません。要件に応じたコレクション・クラスを使いこなすためには、要件の明確化とそれぞれのクラスの特性を理解することが重要です。ここではJava 2のコレクション・フレームワークの詳細を解説する余裕はありませんが、全体を概観してみましょう。

コレクション・フレームワークは、3つのインタフェース、java.util.List, java.util.Set, java.util.Mapと、その実装クラスで構成されています。ListとSetはCollectionインタフェースを継承しています。Listはシーケンシャル（直線的）なデータ構造を表します。Setは要素の重複を許さない集合を表します。Mapはキーとデータの組からなるハッシュテーブルのデータ構造です。

スタック Stack: 後入れ先出し(LIFO: Last In First Out)方式のデータ構造。先に入力されているものが次のものを自分の上に積んで、後で積まれたものの方が先に処理されて取り出されます。
キュー Queue: 待ち行列。FIFO (First In First Out)方式のデータ構造。先に入れたものが先に出力され、後で入れたものは後で出力されます。オンライン・システムなどで、入力と処理に時間差がある場合に使われます。
ハッシュ Hash: ハッシュ・アルゴリズムに従うデータ構造。一般に、ハッシュ法とは、データ探索を高速にするために開発されたもので、格納データ自身から、その格納データ位置を生成する方法です。このデータ位置はハッシュ値と呼ばれ、ハッシュ値を求める処理をハッシュ関数と呼びます。ハッシュテーブルは、キーとデータの組からなるデータ構造で、キーからハッシュ値を求め、そのハッシュ値を索引としてデータを探索します。ハッシュ関数によっては、複数の異なるキーから同じハッシュ値が求められることもあります。この状態をシノニム（同義語）と呼びます。この場合は、一つのハッシュ値に複数のデータが対応付けられることになり、同じハッシュ値内に含まれるデータの集まりのことをバケットと呼びます。

図2は、コレクション・フレームワークのjava.utilパッケージにおける、代表的なインタフェース／クラスの階層図です。矢印は実践が継承、点線が実装です。クラス名が斜線になっているものは抽象クラスです。抽象度の高いクラスや特殊なクラス、意味が重複する矢印は含まれていません。

図2. コレクション・フレームワークの階層

Vector, Stack, Hashtable は、Java 2以前から存在し、今でも広く使われています。それぞれ、可変長配列、スタック、ハッシュテーブルを実装します。Java 2では、これらの古いクラスも、コレクション・フレームワークの枠組みで改良されています。

古いコレクション・クラスには、処理速度が遅いという問題がありました。その最大の原因は、オブジェクトが常に「同期化」されることです。同期化とは、1つのオブジェクトが同時に最大でも1つのスレッドだけから更新されるように実装することです。データ整合性を確保するために、同期化の仕組みは不可欠である一方で、オブジェクトの生成／破棄と並び、Javaプログラムの実行速度を下げるものの代表格でもあります。

Java 2で導入されたコレクション・フレームワークのクラスは、同期化されないものとして設計されました。現在では、複数スレッド間で競合がない場合は、同期化されたコードによる無用なパフォーマンス上の劣化はほとんどありませんが、必要なときだけ同期化するという怠惰(lazy)な設計思想が踏襲されています。　表3に、インタフェースList、Map、Setとその実装クラスの詳細を示しました。

java.util.Listインタフェース

要素は索引によってアクセスされます。add(), remove(), indexOf(), get()など、実装クラスで利用される殆どのメソッドを宣言しています。

Vectorクラス: 同期。リサイズ可能な配列を実装します。
Stackクラス: 同期。後入れ先出し(FIFO)スタックを実装します。Vectorを継承し、push(), pop()などのメソッドが追加されています。
ArrayListクラス: 非同期。Vectorの後継。Linkの基本的な実装クラスです。リサイズ可能な配列を実装します。
LinkedListクラス: 非同期。Stackの後継。スタック／キューを実装します。要素順序を要素の前後2方向へのリンクで保持します。

java.util.Mapインタフェース

要素はキーによってアクセスされます。put(), get(), remove()などのメソッドを宣言しています。Dictionary抽象クラスの後継。

Hashtableクラス: 同期。キーと値の組からなるハッシュテーブルを実装します。Dictionary抽象クラスを継承します。
Propertiesクラス: 同期。キーと値がString型であるハッシュテーブルを実装します。A=B形式のプロパティの列挙、プロパティ・ファイルの読み込み／書き出しのために使います。Java 2では、java.util.prefsパッケージでPreferencesなどの新しいクラスが利用できます。
HashMapクラス: 非同期。Hashtableの後継。Mapの基本的な実装クラスです。ハッシュテーブルを実装します。
TreeMapクラス: 非同期。キーによってソートされたハッシュテーブルを実装します。
WeakHashMapクラス: 非同期。キーを弱参照オブジェクト(weak reference)で保持するハッシュテーブルを実装します。WeakHashMapオブジェクト自身は持続していても、キーを明示的に参照するスレッドがなくなると、当該キーが占有していたメモリ領域が再利用可能となります。内部管理上のオーバーヘッドと引き換えにメモリ効率が向上します。当該ハッシュから、そのキーのエントリーがなくなるので、持続的なデータの保持のためではなく、レジストリ、キャッシュのように利用します。弱参照はjava.lang.ref.WeakReference型オブジェクトであり、オブジェクトを破棄してメモリを再利用するために内部的に実行されているガベッジ・コレクタを、間接的に操作する仕組みです。詳細は次のURLを参照してください：http://java.sun.com/j2se/1.4/ja/docs/ja/guide/refobs/
LinkedHashMapクラス: J2SE v1.4。非同期。挿入順またはアクセス順を、要素の前後2方向へのリンクで保持したハッシュテーブルを実装します。

java.util.Setインタフェース

重複要素のない集合を表現します。このインタフェースの実装クラスは、内部的にはMapインタフェースの実装クラスに基づいており、動作特性も共通しています。

HashSetクラス: 非同期。Setの基本的な実装クラスです。集合を実装します。
TreeSetクラス: 非同期。順序を持つ集合を実装します。
LinkedHashSetクラス: J2SE v1.4。非同期。挿入順を、要素の前後2方向へのリンクで保持した集合を実装します。

全般にわたる注意

コレクション全般に渡る情報として、更に次のことを補足します：

コレクション・クラスは要素をObject型で出し入れします。そのため、取り出した要素を使うためには、目的の型へキャストする必要があります。
Vectorなどの同期がとられるスレッド・セーフなオブジェクトはパフォーマンスが悪く、Java 2で追加されたコレクション・クラスでは同期がとられないようになっています。
Vectorなどの古いクラスでは、後方互換のために、Java 2以前のAPIを実装しています。また、要素を順番に取り出すために、EnumerationとIteratorの両方が使えますが、新しいクラスではIteratorだけしか使えません。
java.util.Collectionsクラスは、コレクションを操作するユーティリティ・クラスで、スレッド・セーフなオブジェクトや不変オブジェクトの生成などが可能です。
java.util.Arraysクラスも、Collectionsクラスと同様、配列を操作するユーティリティ・クラスであり、検索、ソート、比較などが可能です。

SEO		[PR] ��!��u��O ��z�[��y�[�W�J�� C�u��