<<PREV | ToC | NEXT>>

HashSet クラス

Revised: Mar./2nd/2003; Since: Feb./23rd/2003

クラス HashSet は、インタフェース Set の最も基本的な実装です。Set インタフェースは、重複を許さない要素の集合であるデータ構造の振る舞いを規定するものであり、実装するクラスには、HashSet, LinkedHashSet, TreeSet が挙げられます。

クラス階層

クラス階層
java.lang.Object
  |
  +--java.util.AbstractCollection
        |
        +--java.util.AbstractSet
              |
              +--java.util.HashSet

HashSet クラスは java.util パッケージに含まれるので、利用するファイルではパッケージをインポートしておく必要があります。

概要

重複を許さない要素の集合であり、数学における集合の概念を表します。例えば、オブジェクトの集合のなかに、あるオブジェクトが存在するかどうか判定するために使うことができます。

API 仕様書では次のように説明されています：

このクラスは、ハッシュテーブル (実際には HashMap のインスタンス) を基にし、Set インタフェースを実装します。このクラスでは、セットの繰り返し順序について保証しません。特に、その順序を一定に保つことを保証しません。このクラスは、null 要素を許容します。

動作特性

HashSet は重複を許さない要素の集まりです。内部的には HashMap を使っており、動作特性も HashMap に準じます。LinkedHashSet の場合は LinkedList によって、要素の挿入順序が維持されます。 TreeSet の場合は完全二分木の一種である Red-Blask ツリー型データ構造をなしており、要素が昇順にソートされます。

三つのセット中では、HashSet が一番高速です。続いて、 TreeSet, LinkedHashMap の順番になります。探索に掛かる時間は、要素の個数に対して、HashSet と LinkedSet では一定のパフォーマンスを維持しますが、TreesSet の場合は、要素のサイズの対数に比例します。

HashSet は、イタレーションに対して高速なアクセスを提供しません。これに適しているのは、LinkedHashSet です。

コンストラクタ

二番目のコンストラクタ引数の Collection というのは、コレクション・フレームワークの List と Set のスーパー・インタフェースです。 List と Set を実装するデータ構造のクラス型オブジェクトを引数に取れるということです。このコンストラクタを使えば、異なる特性のデータ構造間の変換も容易です。

HashSet でも初期容量を指定して初期化することが可能です。デフォルトでは、「デフォルトの初期容量(16)およびデフォルトの負荷係数 (0.75)」といなります。ここで、「容量」や「負荷係数」という語は、HashMap の場合と同義です。HashSet でも、メソッド iterator() による繰り返し処理については、容量に比例した時間が必要になるため、初期容量は小さく、負荷係数は大きくとることが重要です。

メソッド

要素の追加 (add()) と削除(remove())、繰り返し (iterator()) 、指定した要素が含まれるかどうかの判別 (contains()) などが実装されています。他にも、インタフェース Set や抽象クラス AbstractSet の実装として、retainAll(), containsAll(), toArray() などの興味深いメソッドが実装されています。

サンプル

次のサンプルは、HashSet と LinkedHashSet, TreeSet の間で、要素の挿入順序を比較するものです。

import java.util.*;

class SetSortedDemo {
	static Set elapsed(Set set, int MAX) {
		for (int i = MAX; i >= 0; i -= 1) {
			int j = (int) (Math.random() * 10);
			set.add(new Integer(j));
			System.out.print(j + " ");
		}
		System.out.println("");
		return set; 
	}

	public static void main(String[] args) {
		Set setHash, setLinked, setTree;
		setHash = elapsed(new HashSet(), 5);
		System.out.println("HashSet:\t" + setHash);
		setLinked = elapsed(new LinkedHashSet(), 5);
		System.out.println("LinkedHashSet:\t" + setLinked);
		setTree = elapsed(new TreeSet(), 5);
		System.out.println("TreeSet:\t" + setTree);
	}
}

実行結果は次のようになります。HashSet は順番がデタラメに出力されています。LinkedHashSet は挿入順を維持し、TreeSet は要素の持つ順番に基づき昇順に並んでいることが分かります。

C:\java>javac SetSortedDemo.java
C:\java>java SetSortedDemo
0 1 8 9 6 7
HashSet:        [9, 8, 6, 1, 7, 0]
9 5 8 8 3 6
LinkedHashSet:  [9, 5, 8, 3, 6]
0 2 1 8 9 5
TreeSet:        [0, 1, 2, 5, 8, 9]

次のサンプルは、各 Set 間のパフォーマンスを比較するものです。

import java.util.*;
class SetPerformanceDemo {
	static void elapsed(Set set, int MAX) {
		long start = System.currentTimeMillis();
		for (int i = MAX; i > 0; i--) {
			set.add(new Integer(i));
		}
		long end = System.currentTimeMillis();
		long def = (end - start)/MAX;
		System.out.println("Elapsed Time: " + def);
	}
	public static void main(String[] args) {
		if (args.length != 2 || !args[0].equals("HashSet")
		& !args[0].equals("LinkedHashSet") & !args[0].equals("TreeSet")) {
			System.out.println("Arguments are invalid!");
			System.exit(1);
		}
		try {
			Set set = (Set) Class.forName("java.util." + args[0]).newInstance();
			elapsed(set, Integer.parseInt(args[1]));
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

経過時間は実行マシンのスペックに依存しますが、HashSet < TreeSet < LinkedHashSet の順番になります。要素数を増減させて試してみてください。おおむね一定のパフォーマンスで推移することが確認できると思います。

C:\java>java SetPerformanceDemo HashSet 1000
Elapsed Time: 20

C:\java>java SetPerformanceDemo HashSet 10000
Elapsed Time: 50
C:\java>java SetPerformanceDemo HashSet 100000
Elapsed Time: 901

C:\java>java SetPerformanceDemo LinkedHashSet 1000
Elapsed Time: 20
C:\java>java SetPerformanceDemo LinkedHashSet 10000
Elapsed Time: 60
C:\java>java SetPerformanceDemo LinkedHashSet 100000
Elapsed Time: 1242
C:\java>java SetPerformanceDemo TreeSet 1000
Elapsed Time: 40
C:\java>java SetPerformanceDemo TreeSet 10000
Elapsed Time: 100

C:\java>java SetPerformanceDemo TreeSet 100000
Elapsed Time: 952

<<PREV | ToC | NEXT>>