Setの実装クラスRevised: May/10th/2008; Since: Feb./23rd/2003
クラス HashSet は、インタフェース Set の最も基本的な実装です。Set インタフェースは、重複を許さない要素の集合であるデータ構造の振る舞いを規定するものであり、実装するクラスには、HashSet, LinkedHashSet, TreeSet, EnumSetなどが挙げられます。
HashSetの継承階層クラス階層
java.lang.Object
|
+--java.util.AbstractCollection
|
+--java.util.AbstractSet
|
+--java.util.HashSet
HashSet クラスはjava.utilパッケージに含まれるので、利用するファイルではパッケージをインポートしておく必要があります。
HashSetの概要重複を許さない要素の集合であり、数学における集合の概念を表します。例えば、オブジェクトの集合のなかに、あるオブジェクトが存在するかどうか判定するために使うことができます。add()の戻り値型はbooleanで、同じ要素をadd()しても例外は発生しませんが、falseが返ります。remove()についても同様です。
API 仕様書では次のように説明されています：
このクラスは、ハッシュテーブル (実際には HashMap のインスタンス) に連動し、Set インタフェースを実装します。このクラスでは、セットの繰り返し順序について保証しません。特に、その順序を一定に保つことを保証しません。このクラスは、null 要素を許容します。
HashSetの動作特性HashSetは重複を許さない要素の集まりです。内部的にはHashMapを使っており、動作特性もHashMapに準じます。LinkedHashSetの場合LinkedListによって、要素の挿入順序が維持されます。TreeSetの場合はComparatorを用いて明示的に順序付けができます。
キーの順序は一般に保証されません。キーの順序を保証する必要がある場合は、SortedSetインタフェースの実装クラスを使います。TreeSetが代表的です。SortedSetではキーの順序が保証されているので、first(), last(), tailSet()など、キーの順序に依存したメソッドが追加されています。
HashSet, LinkedHashSet, TreeSetの動作特性は、ArrayListやHashMapに対するその他のクラスと同じです。
HashSetは、基本的な操作に対しては高速ですが、イタレーションに対して高速なアクセスを提供しません。これに適しているのは、LinkedHashSetです。LinkedHashSetはHashSetのサブクラスで、値の挿入順序を保ちます。但し、基本的な操作に対しては、HashSetよりも低速です。
TreeSetでは、Comparatorによって明示的にキーをソートできます。
EnumSetは、Enumクラスをキーにとることができて、順序は自然順序付けされます。キーは内部実装では配列として保持されます。
HashSetのコンストラクタ| コンストラクタの概要 | |
|---|---|
TreeSet()
要素の自然順序付けに従ってソートされた、新しい空のツリーセットを作成します。 |
|
TreeSet(Collection<? extends E> c)
指定されたコレクション内の要素を持ち、要素の「自然順序付け」に従ってソートされた新しいツリーセットを作成します。 |
|
TreeSet(Comparator<? super E> comparator)
指定されたコンパレータに従ってソートされた、新しい空のツリーセットを作成します。 |
|
TreeSet(SortedSet<E> s)
指定されたソートセットと同じ要素を持ち、同じ順序付けを使用する新しいツリーセットを作成します。 |
|
二番目のコンストラクタ引数のCollectionというのは、コレクション・フレームワークのListとSetのスーパー・インタフェースです。ListとSetを実装するデータ構造のクラス型オブジェクトを引数に取れるということです。このコンストラクタを使えば、異なる特性のデータ構造間の変換も容易です。
HashSetでも、HashMapと同様に初期容量を指定して初期化することが可能です。デフォルトでは、「デフォルトの初期容量(16)およびデフォルトの負荷係数 (0.75)」といなります。ここで、「容量」や「負荷係数」という語は、HashMapの場合と同義です。HashSetでも、メソッドiterator()による繰り返し処理については、容量に比例した時間が必要になるため、初期容量は小さく、負荷係数は大きくとることが重要です。
HashSetのメソッド要素の追加 (add()) と削除(remove())、繰り返し (iterator()) 、指定した要素が含まれるかどうかの判別 (contains()) などが実装されています。他にも、インタフェース Set や抽象クラスAbstractSetの実装として、retainAll(), containsAll(), toArray() などの興味深いメソッドが実装されています。
Setの例次のサンプルは、HashSetとLinkedHashSet, TreeSetの間で、要素の挿入順序を比較するものです。要素はMath.random()を使って生成しています。
import java.util.Set;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.TreeSet;
class TestSortedSet {
static Set<Integer> elapsed(Set<Integer> set, int MAX) {
for (int i = MAX; i >= 0; i -= 1) {
int j = (int)(Math.random() * 10);
set.add(j);
System.out.print(j + " ");
}
System.out.println("");
return set;
}
public static void main(String[] args) {
Set<Integer> setHash, setLinked, setTree;
setHash = elapsed(new HashSet<Integer>(), 5);
System.out.println("HashSet:\t" + setHash);
setLinked = elapsed(new LinkedHashSet<Integer>(), 5);
System.out.println("LinkedHashSet:\t" + setLinked);
setTree = elapsed(new TreeSet<Integer>(), 5);
System.out.println("TreeSet:\t" + setTree);
}
}
実行結果は次のようになります。Setなので、同じ値がadd()されると一意な値にuniqueされていることが分かります（例：{3, 0, 5, 8, 3, 7} -> {0, 3, 5, 7, 8}）。また、HashSetは順番がデタラメに出力されています（この実行結果では、自然順序付けに従っていますが、実装依存です）。LinkedHashSetは挿入順を維持し、TreeSetは要素の持つ順番に基づき昇順に並んでいることが分かります。
D:\java>javac -Xlint TestSortedSet.java D:\java>java TestSortedSet 3 0 5 8 3 7 HashSet: [0, 3, 5, 7, 8] 6 8 5 2 2 5 LinkedHashSet: [6, 8, 5, 2] 2 0 4 3 5 7 TreeSet: [0, 2, 3, 4, 5, 7] D:\java>
次のサンプルは、各 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();
}
}
}
経過時間は実行マシンのスペックに依存しますが、add()の処理速度はHashSet < LinkedHashSet < LinkedHashSet の順番になります。要素数を増減させて試してみてください。要素数の増加に対して、おおむね一定のパフォーマンスO(1)で推移することが確認できると思います。
D:\java>javac -Xlint TestSetPerformance.java
TestSetPerformance.java:27: 警告:[unchecked] 無検査変換です
検出値 : java.util.Set
期待値 : java.util.Set<java.lang.Integer>
elapsed(set, Integer.valueOf(args[1]));
^
警告 1 個
D:\java>java -Xmx768m TestSetPerformance HashSet 1000000
Elapsed Time: 1094
D:\java>java -Xmx768m TestSetPerformance HashSet 5000000
Elapsed Time: 4613
D:\java>java -Xmx768m TestSetPerformance HashSet 10000000
Elapsed Time: 12120
D:\java>java -Xmx768m TestSetPerformance LinkedHashSet 1000000
Elapsed Time: 1470
D:\java>java -Xmx768m TestSetPerformance LinkedHashSet 5000000
Elapsed Time: 6866
D:\java>java -Xmx768m TestSetPerformance LinkedHashSet 10000000
Elapsed Time: 11995
D:\java>java -Xmx768m TestSetPerformance TreeSet 1000000
Elapsed Time: 1548
D:\java>java -Xmx768m TestSetPerformance TreeSet 5000000
Elapsed Time: 8586
D:\java>java -Xmx768m TestSetPerformance TreeSet 10000000
Elapsed Time: 17328
D:\java>
リフレクションで型パラメータを指定できないため、コンパイル時に無検査変換の警告が出されています。実行時に、OutOfMemoryErrorが発生してしまうので、オプション-Xmxでヒープの最大サイズを768MBに指定しています。
EnumSetの例J2SE 5.0以上で追加された言語仕様Enumを用いてコレクションクラスは拡張されています。Set型のクラスはEnumSetです。
import java.util.EnumSet;
enum Ranks { DEUCE, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING, ACE }
class TestEnumSet {
public static void main(String[] args) {
// EnumSetのインスタンス化
EnumSet<Ranks> ranks = EnumSet.allOf(Ranks.class);
// EnumSetのインスタンス化2 - 絵札のみ
EnumSet<Ranks> courtCards = EnumSet.of(Ranks.JACK, Ranks.QUEEN, Ranks.KING);
// EnumSetのインスタンス化3 - 絵札以外
EnumSet<Ranks> noCourtCards = EnumSet.complementOf(EnumSet.of(Ranks.JACK, Ranks.QUEEN, Ranks.KING));
System.out.println("Ranks: " + ranks.size());
for (Ranks r : ranks) {
System.out.println("\t" + r);
}
System.out.println("Courts: " + courtCards.size());
for (Ranks r : courtCards) {
System.out.println("\t" + r);
}
System.out.println("Non Courts: " + noCourtCards.size());
for (Ranks r : noCourtCards) {
System.out.println("\t" + r);
}
}
}
D:\java>javac TestEnumSet.java
D:\java>java TestEnumSet
Ranks: 13
DEUCE
THREE
FOUR
FIVE
SIX
SEVEN
EIGHT
NINE
TEN
JACK
QUEEN
KING
ACE
Courts: 3
JACK
QUEEN
KING
Non Courts: 10
DEUCE
THREE
FOUR
FIVE
SIX
SEVEN
EIGHT
NINE
TEN
ACE
D:\java>
この例では、ファクトリメソッドとして、allOf(), of(), complementOf()を使いました。EnumSetは内部ではlong型ビット配列で保持されているので、軽量で高速に動作します。ビット演算が必要なときに、利用を検討してください。上記のサンプルでは扱いませんでしたが、他のSet型と同様、contains()などで評価します。