コレクション・フレームワークの Tips and Tricks

import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;

class TestIterator {
	public static void main(String[] args) {
		String[] products = {"TV", "Stereo", "Video", "Camera"};
		int prodLen = products.length;
		// ArrayListの生成
		List<String> prodList = new ArrayList<String>(prodLen);
		// リストへ要素を追加
		for (int i =0; i < prodLen; i++) {
		    prodList.add(products[i]);
		}
		dumpList(prodList);
	}
	static void dumpList(List<?> list) {
		// Iteratorの取得
		Iterator<?> itr = list.iterator();
		// Iteratorから要素を取得
		while (itr.hasNext()) {
		    System.out.println(itr.next().toString());
		}
	}
}

上記のコードのイタレーション部分は、次のようにも書けます。

for (Iterator<?> itr = list.iterator(); itr.hasNext(); ) {
    System.out.println(itr.next().toString());
}

この例では、リストの要素のインデックスにアクセスしていないので、拡張for文を使うこともできます。

for (Object obj : list) {
	System.out.println(obj.toString());
}

IteratorはEnumerationの後継です。Vectorを使う場合でもEnumerationは使わず、Iteratorを使います。Enumerationは、他のパッケージや古いクラスから要求されるときだけ使うことになります。

Iteratorはその途中にループの真偽判定メソッドを含みます。メソッド呼び出しはスタックからヒープを探索するため、多くの場合、少ない方がパフォーマンスは向上します。速度が重要なコードでは他の方法も検討してください。ArrayListの場合は、次のようにforループとget()メソッドの組み合わせが使えます。

for (int i = 0; i < proList.size(); i++) {
    System.out.println(prodList.get(i));
}

Q. ArrayListに挿入を繰り返すと遅くなる？

リストに対する挿入、削除を繰り返す場合、LinkedListを使うと動作速度が向上することがあります。リストの途中の要素に挿入／削除が繰り返される場合、ArrayListは再配列を必要とするため、パフォーマンスが悪化します。

LinkedListの要素は前後の要素への参照を持ち、2重にリンクされたデータ構造（リンク・リスト）です。その結果、任意の要素へのランダムアクセスではArrayListの方が高速であり、順次アクセスや要素の挿入／削除ではLinkedListの方が高速です。

また、LinkedListには特定の索引への挿入／削除に特化したメソッドも用意されています。add()/remove()やaddLast()/removeFirst()を使えば先入れ先出し(FIFO)キューになり、push()/pop()やaddFirst()/removeFirst()を使えば後入れ後出し(LILO)キュー（スタック）として実装できます。これらの機能は、インタフェースDequeの実装です。詳細はQueueを参照してください。

順次アクセス、途中への要素の挿入／削除が必要な場合はLinkedListの方が高速です。索引によるランダム・アクセスではArrayListが高速です。HashMapとLinkedHashMap、HashSetとLinkedHashSetでも同様のことが言えます。例えば、エントリー数が増える場合は、HashMapよりもLinkedHashMapの方が高速なことがあります。

Q. LinkedListとStackの違いは？

どちらもLIFOキューの実装です。Stackは古いクラスでLinkedListは新しいクラスです。

新しいクラスでは、追加／削除／参照の各操作に対して、要素数が操作に対して条件を見たい指定ない場合に、例外を返すメソッドと、特殊な値を返すメソッドが用意されています。古いクラスでは、一方しか用意されていません。

StackよりもLinkedListかArrayDequeを使うべきです。基本操作に対しては、ArrayDequeの方が高速です。

Q. IteratorとListIteratorの違いは？

コレクションはIteratorを使うためのインタフェースを備えていますが、List実装クラスではListIteratorインタフェースも使えます。ListIteratorでは、要素の削除／置換／追加のほか、2方向のカーソル移動をサポートします。

import java.util.List;
import java.util.ArrayList;
import java.util.ListIterator;
import java.util.Iterator;

class TestListIterator {
    public static void main(String[] args) {
        String[] products = {"TV", "Stereo", "Video", "Camera"};
        int prodLen = products.length;
        // ArrayListの生成
        List<String> prodList = new ArrayList<String>(prodLen);
        // リストへ要素を追加
        for (int i =0; i < prodLen; i++) {
            prodList.add(products[i]);
        }
        // ListIteratorの取得
        ListIterator<String> litr = prodList.listIterator();
         
        String s;
        litr.next();    // | TV
        s = litr.next();    // TV | Stereo
        // 直前のnext()が返した要素を削除
        litr.remove();  // TV | Video
        litr.next();    // TV Video | Camera
        // カーソルの直前に挿入
        litr.add(s);    // TV Video Stereo | Camera
        litr.next();    // TV Video Stereo Camera |
        s = litr.previous();    // TV Video Stereo | Camera
        // 直前のprevious()が返した要素を削除
        litr.remove();  // TV Video Stereo |
        litr.previous();    // TV Video | Stereo
        litr.previous();    // TV | Video Stereo
        litr.previous();    // | TV Video Stereo
        litr.add(s);    // Camera | TV Video Stereo
        // Iteratorの取得
        for (Iterator<String> pit = prodList.iterator(); pit.hasNext(); ) {
            System.out.println(pit.next());
        }
    }
}

出力結果は次のようになります。

D:\java>javac TestListIterator.java

D:\java>java TestListIterator
Camera
TV
Video
Stereo

D:\java>

Q. Setは何に使える？

Setは数学における集合の概念を定義します。特定のオブジェクトが、既存のオブジェクトの集合に含まれるかどうかを調べるときに便利です。

HashSetとTreeSetは、どちらも重複を許さない集まりである集合を定義するSetインタフェースの実装クラスであり、TreeSetは要素がソートされる点が異なります。SetがListと異なるのは、その要素に重複を含まないことであり、数学上の集合の概念を実装するものです。そのため、オブジェクトが集合に含まれるかどうかをチェックするには、HashSet.contains()の方がArrayList.contains()などよりも、高速に実装されています。

EnumSetはEnum定数（列挙型）のSet実装を提供します。内部ではlong型のビットベクトルで保持されているため、軽量かつ高速です。フラグを保持して操作したい場合、従来はlong型に16進数で値を保持して、論理演算子で操作していましたが、J2EE 5.0以上では、EnumSetを使うべきです。

要素の順序付けが行いたい場合はSortedSet、もしくはTreeSetを使ってください。定数の列挙が行いたい場合はEnumSetを使ってください。

Q. コレクションの一部分だけ扱える？

コレクションの一部分を取り出して操作するためには、各々のクラスのメソッドを使います。

Listの場合

部分リストのビューを取得するメソッドが用意されています。

subList(int fromIndex, int toIndex)

fromIndex以上、toIndex未満の範囲の部分リストのビューを返します。

Setの場合

順序を持つTreeSetでだけ、部分集合のビューを取得できます。

headSet(Object toElement)

toElement（含まない）未満の要素からなる部分集合のビューを返します。

tailSet(Object fromElement)

fromElement（含む）以上の要素からなる部分集合のビューを返します。

subSet(Object fromElement, Object toElement)

fromElement（含む）以上、toElement（含まない）未満の要素からなる部分集合のビューを返します。

Mapの場合

TreeMapでだけ、ハッシュ全体の部分ハッシュのビューを取得できます。そのメソッドはTreeSetの場合とほぼ同じです。というのも、TreeSetのコンストラクタでは、実はTreeMapを使ってインスタンス化しているからです。

headMap(Object toKey)

toKeyより小さいキーを持つ部分のハッシュのビューを返します。

tailMap(Object fromKey)

fromKeyより大きいキーを持つ部分のハッシュのビューを返します。

tailMap(Object fromKey, Object toKey)

キーがfromKey（含む）からtoKey（含まない）までの部分のハッシュのビューを返します。

最後に配列の場合を紹介します。部分配列の取得には、System.arraycopy()が使えます。System.arraycopy()は5つの引数を持ち、それぞれ、順番にソース配列、ソース配列の要素の索引の開始位置、転送先配列、転送先配列内の開始位置、コピーされる要素の個数になります。これは別の配列の生成なので、ソース配列と転送先配列の間に関係はありません。forメソッドでも同じことができますが、こちらの方が高速です。

class TestArrayCopy {
	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);
		String str = "";
		for (int i = 0; i < length; i++) {
			if (i < length - 1) {
				System.out.print(dest[i] + " ");
			} else {
				System.out.println(dest[i] + ".");
			}
		}
	}
}

出力結果は次のようになります。

there was light.

上記の例であれば、クラスjava.util.ArraysのcopyOf(), copyOfRange()の方が簡単です。

// 配列srcから長さ3の配列を生成（生成する配列の方が長い場合は0パディング）
Object[] dest = Arrays.copyOf(src, 3);

// 配列srcのインデックス7以上src.length以下の要素を配列で生成
Object[] dest = Arrays.copyOfRange(src, 6, src.length);

Q. コレクションを同期化するには？

同期をとるオブジェクトの生成にはCollectionsクラスのファクトリ・メソッドを使います。 コレクション・クラスは同期化されていないから早いのだと強調してきましたが、複数のスレッド間で共有したいこともあります。複数スレッドからの同時更新による不整合から保護するためには、synchronized()ブロックでくくっても良いのですが、生成時に同期化オブジェクトにラップすることで、煩雑な作業を減らし、同期化し忘れることにも備えられます。

同期化されたビューを取得するメソッドは、Collections.synchronizedXxx()です。このメソッドが返した参照は、元のオブジェクトの同期ラッパーと呼びます。

コードの混乱を避けるために、コレクション・オブジェクトの生成直後に行うのが良いでしょう。

SortedSet ids = new TreeSet();
SortedSet unmodIds = Collections.synchronizedSortedSet(ids);
// 実際は、次のように書くべきです
// SortedSet unmodIds = Collections.synchronizedSortedSet(new TreeSet());

ここで生成されたunmodIdsはスレッド・セーフです。マルチスレッドの共有オブジェクトとして使うときにはunmodIds、同期化の必要がなければidsと使い分けることもできます。多くの場合は、共有オブジェクトだけが必要です。

但し、こうして作ったオブジェクトは、Iteratorによる操作に対してはスレッド・セーフではありません！従って、Iteratorを使うときには、明示的に元のオブジェクトに対するsynchronized()ブロックを使わなければなりません。

SortedSet ids = new TreeSet();
SortedSet unmodIds = Collections.synchronizedSortedSet(ids);
synchronized(ids) {
	Iterator itr = unmodIds.iterator();
	while (itr.hasNext()) {
		:
	}
}

さもないと、繰り返し処理中に他のスレッドによって要素が追加／削除されたとき、イタレーションの繰り返し処理に影響が及びます。

import java.util.Collections;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.Iterator;

class TestSynchronizedCollection {
    public static void main(String[] args) {
        // 同期オブジェクトの取得
        SortedMap<String, Integer> customers = Collections.synchronizedSortedMap(new TreeMap<String, Integer>());
        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<String> i = customers.keySet().iterator();
            // イタレーション
            while (i.hasNext()) {
                obj = i.next();
                System.out.println(obj + ":\t " + customers.get(obj));
            }
        }
    }
}

結果は次のようになります。

D:\java>javac TestSynchronizedCollection.java

D:\java>java TestSynchronizedCollection
Ito:     5543
Kawai:   2742
Sugai:   1066
Ueda:    9581

D:\java>

Q. コレクションを不変オブジェクトにするには？

不変オブジェクトの生成にもCollectionsクラスのファクトリ・メソッドを使います。

不変オブジェクトは、その名のとおりsetterメソッドなどの変更のためのAPIを持たないオブジェクトです。変更したければ、別のオブジェクトを生成して代入し直す他なく、不用意に作ると負荷が高くなるので、取り扱いには注意が必要です。ともあれ、生成したオブジェクトを外部から保護したいことも良くあります。

不変オブジェクトの取得は同期化オブジェクトの取得と同様、Collectionsクラスを使います。

SortedSet branches = new TreeSet();
...branchesオブジェクトの編集
// 変更不能なビューの取得
SortedSet unmodBranches = Collections.unmodifiableSortedSet(branches);

例えば、外部にはunmodBranchesだけ提供して変更を許さず、内部ではbranchesを変更するというように使い分けができます。そのような使い分けが必要なく、一切の変更を禁止するためには、代入先をunmodBranchesではなくbranchesにすれば、変更不可能なオブジェクトだけが存在することになります。

Q18. リストの検索は高速化できる？

並べ替えや検索のアルゴリズムは古くから研究されており、コレクション・フレームワークでもいくつか利用できます。ここでは、リストの要素の検索を高速にする2分探索法を紹介します。

2分探索法は、データがソートされているときに有効な探索法です。まず、データの中央の値と目的の値を比較し、上半分と下半分のどちらに含まれているかを決定します。仮に上半分であれば、先ほど中央に合った値の一つ上から最大の値までの間で中央の値をとり、目的の値と比較し、同じことを繰り返していきます。

CollectionsクラスのbinarySearch()は、同じくCollectionsクラスのsort()メソッドなどでソート済みのリスト・オブジェクトに対して、2分探索を実行します。ソート済みのリスト・オブジェクトの場合、通常はindexOf()よりも非常に高速です。

void insert(List list, Object obj) {
    // ソート
    Collections.sort(list);
    // 2分探索法
    // 存在すれば索引(≧0)。
    // 存在しなければ"- 挿入位置 - 1" (<0)。
    int index = Collections.binarySearch(list, obj);
    // 存在しない場合、挿入位置に挿入
    if (index < 0) {
        list.add(- index - 1, obj);
    }
}

<<PREV | ToC | NEXT>>