Revised: Feb./23rd/2003
Javaに限らず、プログラミングではデータ構造が重要な役割を果たします。コレクション・フレームワークとは、Java 2でデータ構造を取り扱うための設計のことです。J2SE 1.3/1.4には、コレクション・フレームワークに基づいたクラス／インタフェースが大量に実装されていますが、数が多いので最初は戸惑うことも多いでしょう。
古いAPIは処理が遅く、データ構造の変更負荷が高くなります。
古いデータ構造のインタフェース／クラスは、コレクション・フレームワークの導入に伴い、以下のように後継となるインタフェース／クラスが追加されました。
古いコレクション・クラス自身も、それまでのJDKとの互換性を保ちつつ、コレクション・フレームワークの枠組みを満たすように再設計されたうえでパッケージに含められています。
古いデータ構造の特徴は、同期化されていることと、コレクション・フレームワーク以前のAPIをサポートされていることです。その結果、古いデータ構造は、動作が遅く、ほかのデータ構造に変換しようとした際に手間がかかるかもしれません。このことから、データ構造を扱う際には、Java 2 SDK以降で導入されたコレクション・クラスの利用を検討するべきでしょう。
例えば、クラスVectorを使いたい場合は、配列やクラスArrayListなどを使えないかどうかを検討します。VectorもArrayListも、サイズが自動的に拡張される可変長配列ですが、サイズの拡張が不要ならば配列のほうが高速ですし、同期化の必要がないのならばArrayListを使ったほうが高速なことがあります。
また、古いコレクション・クラスで古いAPIを使う場合は、別のデータ構造への変更負荷が大きくなります。コレクション・フレームワークにのっとることで、共通のインタフェースに従うことになるため、データ構造を変更する際に、コードの変更範囲を最小限度に抑えることが可能になります。
パフォーマンス、変更、一貫性の観点から、古いAPIではなくコレクション・フレームワークを使うことを強くお勧めします。
コレクション・クラスの方が高機能で柔軟ですが、配列の方が早いことがあります。
Listと配列の最大の違いはサイズが拡張可能であることです。事前にサイズの拡張を回避できるのであれば、ArrayListオブジェクトと配列オブジェクトにはデータ構造上は、大きな違いはありません。クラスVectorでもArrayListでも、サイズの拡張は一次オブジェクトの生成と破棄を含む負荷の高い処理なので、最初にオブジェクトを生成するときに、要素サイズを適切に見積もり、拡張を伴わないように配慮してください。
実運用時に近い環境でプロファイリングを行ったうえで、コレクション・フレームワークの一貫性と、配列の速さの間のトレードオフを考慮して、どちらを使うかを判断するということになります。
なお、配列でもクラスArraysを使うことで、二分探索（バイナリ・サーチ）や並べ替え（ソート）などのアルゴリズムを利用することができます。
Enumerationは古いAPIです。コレクション・フレームワークではIteratorを使います。Vectorなどの古いAPIでEnumerationが使えますが、他のコレクションへの変更時には、その部分のコードが使えなくなるので不便です（リスト3）。
▼リスト3
String[] products = {"TV", "Stereo", "Video", "Camera"};
int prodLen = products.length;
// ArrayListの生成
List prodList = new ArrayList(prodLen);
// リストへ要素を追加
for (int i =0; i < prodLen; i++) {
prodList.add(products[i]);
}
// Iteratorの取得
Iterator prodIt = prodList.iterator();
// Iteratorから要素を取得
while (prodIt.hasNext()) {
System.out.println(prodIt.next());
}
IteratorはEnumerationの後継です。Vectorを使う場合でもEnumerationは使わず、Iteratorを使います。Enumerationは、他のパッケージや古いクラスから要求されるときだけ使うことになります。
Iteratorはその途中にwhileループの真偽判定メソッドを含みます。メソッド呼び出しはスタックからヒープを探索するため、多くの場合、少ない方がパフォーマンスは向上します。速度が重要なコードでは他の方法も検討してください。ArrayListの場合は、次のようにforループとget()メソッドの組み合わせが使えます。
for (int i = 0; i < proList.size(); i++) {
System.out.println(prodList.get(i));
}
リストに対する挿入、削除を繰り返す場合、LinkedListを使うと動作速度が向上することがあります。リストの途中の要素に挿入／削除が繰り返される場合、ArrayListは再配列を必要とするため、パフォーマンスが悪化します。
LinkedListの要素は前後の要素への参照を持ち、2重にリンクされたデータ構造（リンク・リスト）です。その結果、任意の要素へのランダムアクセスではArrayListの方が高速であり、順次アクセスや要素の挿入／削除ではLinkedListの方が高速です。
また、LinkedListには特定の索引への挿入／削除に特化したメソッドも用意されています。push()/pop()を使えばスタックになり、addLast()/removeFirst()を使えば先入れ先出し(FIFO)キューになり、addFirst()/removeLast()を使えば後入れ後出し(LILO)キューとして実装できます。
順次アクセス、途中への要素の挿入／削除が必要な場合はLinkedListの方が高速です。索引によるランダム・アクセスではArrayListが高速です。HashMapとLinkedHashMap、HashSetとLinkedHashSetでも同様のことが言えます。例えば、エントリー数が増える場合は、HashMapよりもLinkedHashMapの方が高速なことがあります。
コレクションはIteratorを使うためのインタフェースを備えていますが、List実装クラスではListIteratorインタフェースも使えます。ListIteratorでは、要素の削除／置換／追加のほか、2方向のカーソル移動をサポートします（リスト4）。
▼リスト4
import java.util.*;
class ListIteratorDemo {
public static void main(String[] args) {
String[] products = {"TV", "Stereo", "Video", "Camera"};
int prodLen = products.length;
// ArrayListの生成
List prodList = new ArrayList(prodLen);
// リストへ要素を追加
for (int i =0; i < prodLen; i++) {
prodList.add(products[i]);
}
// ListIteratorの取得
ListIterator plit = prodList.listIterator();
String s;
plit.next(); // | TV
s = (String)plit.next(); // TV | Stereo
// 直前のnext()が返した要素を削除
plit.remove(); // TV | Video
plit.next(); // TV Video | Camera
// カーソルの直前に挿入
plit.add(s); // TV Video Stereo | Camera
plit.next(); // TV Video Stereo Camera |
s = (String)plit.previous(); // TV Video Stereo | Camera
// 直前のprevious()が返した要素を削除
plit.remove(); // TV Video Stereo |
plit.previous(); // TV Video | Stereo
plit.previous(); // TV | Video Stereo
plit.previous(); // | TV Video Stereo
plit.add(s); // Camera | TV Video Stereo
// Iteratorの取得
Iterator pit = prodList.iterator();
while (pit.hasNext()) {
System.out.println(pit.next());
}
}
}
リスト4の出力結果は次のようになります。
Camera TV Video Stereo
Setは数学における集合の概念を定義します。特定のオブジェクトが、既存のオブジェクトの集合に含まれるかどうかを調べるときに便利です。
HashSetとTreeSetは、どちらも重複を許さない集まりである集合を定義するSetインタフェースの実装クラスであり、TreeSetは要素がソートされる点が異なります。SetがListと異なるのは、その要素に重複を含まないことであり、数学上の集合の概念を実装するものです。そのため、オブジェクトが集合に含まれるかどうかをチェックするには、HashSet.contains()の方がArrayList.contains()などよりも、高速に実装されています。
コレクションの一部分を取り出して操作するためには、各々のクラスのメソッドを使います。
subList(int fromIndex, int toIndex)fromIndex以上、toIndex未満の範囲の部分リストのビューを返します。
headSet(Object toElement)toElement（含まない）未満の要素からなる部分集合のビューを返します。
tailSet(Object fromElement)fromElement（含む）以上の要素からなる部分集合のビューを返します。
subSet(Object fromElement, Object toElement)fromElement（含む）以上、toElement（含まない）未満の要素からなる部分集合のビューを返します。
headMap(Object toKey)toKeyより小さいキーを持つ部分のハッシュのビューを返します。
tailMap(Object fromKey)fromKeyより大きいキーを持つ部分のハッシュのビューを返します。
tailMap(Object fromKey, Object toKey)キーがfromKey（含む）からtoKey（含まない）までの部分のハッシュのビューを返します。
最後に配列の場合を紹介します。部分配列の取得には、System.arraycopy()が使えます。System.arraycopy()は5つの引数を持ち、それぞれ、順番にソース配列、ソース配列の要素の索引の開始位置、転送先配列、転送先配列内の開始位置、コピーされる要素の個数になります。これは別の配列の生成なので、ソース配列と転送先配列の間に関係はありません。forメソッドでも同じことができますが、こちらの方が高速です（リスト5）。
▼リスト5
class ArrayCopyDemo {
public static void main(String[] args) {
// ソース配列
Object[] src = {"Let", "there", "be", "light",
";", "and", "there", "was", "light"};
int size = src.length;
int srcPos = 6;
int destPos = 0;
int length = size - srcPos;
// 転送先配列
Object[] dest = new Object[length];
// 配列のコピー
System.arraycopy(src, srcPos, dest, destPos, length);
for (int i = 0; i < length; i++) {
System.out.print(dest[i] + " ");
}
}
}
リスト5の出力結果は次のようになります。
there was light
同期をとるオブジェクトの生成にはCollectionsクラスのファクトリ・メソッドを使います。 コレクション・クラスは同期化されていないから早いのだと強調してきましたが、複数のスレッド間で共有したいこともあります。複数スレッドからの同時更新による不整合から保護するためには、synchronized()ブロックでくくっても良いのですが、生成時に同期化オブジェクトにラップすることで、煩雑な作業を減らし、同期化し忘れることにも備えられます。
同期化のラップはCollectionsクラスのsynchronizedXxx()メソッドを使うことで、簡単に実現できます。コードの混乱を避けるために、コレクション・オブジェクトの生成直後に行うのが良いでしょう。
SortedSet ids = new TreeSet(); SortedSet unmodIds = Collections.synchronizedSortedSet(ids);
ここで生成されたunmodIdsはスレッド・セーフです。マルチスレッドの共有オブジェクトとして使うときにはunmodIds、同期化の必要がなければidsと使い分けることもできます。多くの場合は、共有オブジェクトだけが必要です。このときは、代入先をunmodIdsではなくidsにすれば、同期化されたオブジェクトだけしか存在しなくなります。
但し、こうして作ったオブジェクトは、Iteratorによる変更に対してはスレッド・セーフではありません！従って、Iteratorを使うときには、明示的にsynchronized()ブロックを使わなければなりません（リスト6）。
▼リスト6
import java.util.*;
class SynchronizedDemo {
public static void main(String[] args) {
// 同期オブジェクトの取得
SortedMap customers = Collections.synchronizedSortedMap(new TreeMap());
String[] names = {"Sugai", "Ito", "Ueda", "Kawai"};
int[] ids = {1066, 5543, 9581, 2742};
// キーと値の代入
for (int i = 0; i < names.length; i++) {
customers.put(names[i], new Integer(ids[i]));
}
// 同期化開始
synchronized (customers) {
Object obj;
// Setビューで取得したキーのIterator取得
Iterator i = customers.keySet().iterator();
// イタレーション
while (i.hasNext()) {
obj = i.next();
System.out.println(obj + ": " + customers.get(obj));
}
}
}
}
リスト6の結果は次のようになります。
Ito: 5543 Kawai: 2742 Sugai: 1066 Ueda: 9581
不変オブジェクトの生成にもCollectionsクラスのファクトリ・メソッドを使います。
不変オブジェクトは、その名のとおりsetterメソッドなどの変更のためのAPIを持たないオブジェクトです。変更したければ、別のオブジェクトを生成して代入し直す他なく、不用意に作ると負荷が高くなるので、取り扱いには注意が必要です。ともあれ、生成したオブジェクトを外部から保護したいことも良くあります。
不変オブジェクトの取得は同期化オブジェクトの取得と同様、Collectionsクラスを使います。
SortedSet branches = new TreeSet(); ...branchesオブジェクトの編集 // 変更不能なビューの取得 SortedSet unmodBranches = Collections.unmodifiableSortedSet(branches);
例えば、外部にはunmodBranchesだけ提供して変更を許さず、内部ではbranchesを変更するというように使い分けができます。そのような使い分けが必要なく、一切の変更を禁止するためには、代入先をunmodBranchesではなくbranchesにすれば、変更不可能なオブジェクトだけが存在することになります。
並べ替えや検索のアルゴリズムは古くから研究されており、コレクション・フレームワークでもいくつか利用できます。ここでは、リストの要素の検索を高速にする2分探索法を紹介します。
2分探索法は、データがソートされているときに有効な探索法です。まず、データの中央の値と目的の値を比較し、上半分と下半分のどちらに含まれているかを決定します。仮に上半分であれば、先ほど中央に合った値の一つ上から最大の値までの間で中央の値をとり、目的の値と比較し、同じことを繰り返していきます。
CollectionsクラスのbinarySearch()は、同じくCollectionsクラスのsort()メソッドなどでソート済みのリスト・オブジェクトに対して、2分探索を実行します。ソート済みのリスト・オブジェクトの場合、通常はindexOf()よりも非常に高速です（リスト7）。
▼リスト7
void insert(List list, Object obj) {
// ソート
Collections.sort(list);
// 2分探索法
// 存在すれば索引(≧0)。
// 存在しなければ"- 挿入位置 - 1" (<0)。
int index = Collections.searchBinary(list, obj);
// 存在しない場合、挿入位置に挿入
if (index < 0) {
list.add(- index - 1, obj);
}
}