Manhattan life

クラス 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

クラス HashMap は、インタフェース Map の最も基本的な実装です。Map インタフェースは、キーと値の組の集まりであるデータ構造の振る舞いを規定するものであり、実装するクラスには、Attributes, HashMap, Hashtable, IdentityHashMap, RenderingHints, TreeMap, WeakHashMap が挙げられます。

クラス階層

クラス階層
java.lang.Object
  |
  +--java.util.AbstractMap
        |
        +--java.util.HashMap

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

概要

古いコレクションクラスである Hashtable を置き換えるのが HashMap です。HashMap に保持するデータは、キーと値の組です。 ArrayList などの List 型データ構造が、要素を番号で参照するのに対して、 Map 型データ構造では、要素をキーと呼ばれるオブジェクトで識別します。キーとなるオブジェクトのデータ型は任意であり、文字列でもなんでもかまいません。

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

Map インタフェースのハッシュテーブルに基づく実装です。この実装は、マップに関連するオプションのオペレーションをすべてサポートし、null 値および null キーを使用できます。HashMap クラスは Hashtable と同じと見なしてもかまいませんが、HashMap の方は同期がとられず、null の場合もあります。このクラスは、マップの順序については保証しません。特に、ある期間に渡って一定の順序を保つことを保証しません。

動作特性

コンストラクタ

三番目のコンストラクタをつかえば、Map を実装する任意のデータ構造のクラス型オブジェクトを引数に取れるということです。HashMap, TreeMap, WeakHashMap などの要素は、それぞれ動作特性が異なるので、このコンストラクタを使えば、異なる特性のデータ構造間の変換が容易になります。

ここで、容量というのは、バケット数のことです。バケットとは、キー項目から生成されるハッシュ値の数です。ハッシュ値は、キー項目から算出される 整数になりますが、異なるキー項目から同じハッシュ値が算出されることがあるため、バケット数（容量）よりもキー項目が多いことがありえます。つまり、 キー項目に一意的に対応する値が、同一のハッシュ値に従属する可能性がアルということを意味しています。同一のハッシュ値に従属する要素の集まりをバケッ トと呼び、一つのバケットに含まれる要素の個数をバケットのサイズと呼びます。

ハッシュテーブルでは、キー項目からハッシュ値というものを算出して、その他のデータはハッシュ値に従属させて保持します。従って、値として格納可 能なサイズは、容量（ハッシュコードの数）×バケット・サイズ（一つのハッシュ値に含まれる値の数）ということになります。「容量」が小さいということ は、通常の場合はキー項目の数が少ないということを意味します。

負荷係数というのは、現在の容量の負荷係数分だけ埋まったら、容量を拡張するという数値です。例えば、負荷係数が 0.75 であれば、現在の容量の 0.75 分だけ要素が埋まったら、バケット数を増やす (rehash の発生) ということを意味します。理想的な状況では、キー項目の個数と容量が同じになるので、その場合はキー項目として用意されている予約サイズの 0.75 だけキー項目で消費されたら、サイズ拡張が派生することになります。

HashMap では、要素の追加と取り出しに一定のコストを保証しますが、繰り返し処理では要素数に比例する時間が掛かるので、繰り返し処理の性能を追及すれば、「容量」を小さくして、「負荷係数」を大きくすることが重要です。

メソッド

サンプル

次のリストでは、クラスMapDemoとMapGetDemoを定義しています。クラスMapDemoでは、String型配列とint型配列をそ れぞれキーと値にしてHashMapを作り、HashMap型オブジェクトを引数にしてTreeMapを作っています。これらのオブジェクトは、メソッド MapGetDemo.get()に渡して、キーと要素を出力しています。

import java.util.*;
class MapGetDemo {
	public void get(Map map) {
		// map.keySet()からIteratorを取得
		Iterator it = map.keySet().iterator();
		Object obj;
		while (it.hasNext()) {	// 次の要素があるならブロック内を実行
			obj = it.next();	// 次の要素を取り出す
			System.out.println("\t" + obj + ": " + map.get(obj));
		}
	}
}
class MapDemo {
	public static void main(String[] args) {
		Map mountains = new HashMap();
		String[] names1 = {"Everest", "K2", "Kangchenjunga", "Lhotse", "Makalu"};
		String[] names2 = {"富士山", "北岳", "奥穂高岳", "間ノ岳", "槍ヶ岳"};
		int[] heights1 = {8848, 8611, 8586, 8511, 8463};
		int[] heights2 = {3776, 3192, 3190, 3189, 3180};
		
		System.out.println("HashMap: ");
		// HashMapへのput()
		for (int i = 0; i < 5; i++) {
			mountains.put(names1[i], new Integer(heights1[i]));
		}
		MapGetDemo getDemo = new MapGetDemo();
		getDemo.get(mountains);
		System.out.println("HashMap: ");
		// HashMapへのput()
		for (int i = 0; i < 5; i++) {
			mountains.put(names2[i], new Integer(heights2[i]));
		}
		getDemo.get(mountains);
		
		System.out.println("TreeMap: ");
		// HashMapからTeeMapへの変換
		mountains = new TreeMap(mountains);
		getDemo.get(mountains);
	}
}

実行結果リスト8により、HashMapでは明示的な順序付けがされていないのに対して、TreeMapではキーの文字コード順にソートされていることが分かります。

MapDemo.javaの実行結果:

>javac MapDemo.java
>java MapDemo
HashMap:
        Everest: 8848
        Lhotse: 8511
        Kangchenjunga: 8586
        K2: 8611
        Makalu: 8463
HashMap:
        槍ヶ岳: 3180
        Everest: 8848
        北岳: 3192
        Lhotse: 8511
        Kangchenjunga: 8586
        富士山: 3776
        K2: 8611
        間ノ岳: 3189
        奥穂高岳: 3190
        Makalu: 8463
TreeMap:
        Everest: 8848
        K2: 8611
        Kangchenjunga: 8586
        Lhotse: 8511
        Makalu: 8463
        北岳: 3192
        奥穂高岳: 3190
        富士山: 3776
        槍ヶ岳: 3180
        間ノ岳: 3189

64 ビット浮動小数点数を表す基本データ型である double 型のラップクラスです。

クラス階層

java.lang.Object
  |
  +--java.lang.Number
        |
        +--java.lang.Double

概要

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

Double クラスは、プリミティブ型 double の値をオブジェクトにラップします。型 double のオブジェクトには、型が double の単一フィールドが入ります。

さらにこのクラスは、double を String に、String を double に変換する各種メソッドや、double の処理時に役立つ定数およびメソッドも提供します。

コンストラクタ

つまり、 Double クラスは double 型の変数/値、または文字列型の変数や値を受け取って、オブジェクトを作ります。

メソッド

メソッド、メンバ変数については、沢山あるので全ては紹介しません。詳細は API 仕様を直接ご確認ください。

ここに挙げたのは、次のサンプルで利用するメソッドのみです。

前に説明した Integer クラス と殆ど同じですが、 double 型の非数 (Not-a-Number) NaN と、正負の無限大 NEGATIVE_INFINITY, POSITIVE_INFINITY を扱えるところが新しい。 Java では、 0 割り (zero-devision) が起こっても、コンパイルエラーも例外（Exception: 実行時エラー）も起こらない。

サンプル

class TestInfinite{
	public static void main(String args[]){
		double d1=0.5, d2=1.0/0.0;
		System.out.println("d1: "+d1);
		System.out.println("  =>"+Double.isInfinite(d1));
		System.out.println("d2: "+d2);
		System.out.println("  =>"+Double.isInfinite(d2));
	}
}

ここでは、静的メソッド isInfinite() を用いて、引数に与えた変数が発散しているかどうか判定しています。このメソッドはオーバーロードされており、引数を持たないメソッドは、 Double 型の参照型変数にラップされたオブジェクトの発散を判定します。

C:\Java>javac TestInfinite.java

C:\Java>java TestInfinite
d1: 0.5
  =>false
d2: Infinity
  =>true

クラス階層

java.lang.Object
  |
  +--java.lang.Character

概要

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

Character クラスは、プリミティブ型 char の値をオブジェクトにラップします。Character 型のオブジェクトには、型が char の単一フィールドが入ります。

さらにこのクラスは、文字の型を判定し、文字を大文字から小文字 (またはその逆) に変換するための各種メソッドも提供します。

コンストラクタ

つまり、 Character クラスは char 型の変数/値を受け取って、オブジェクトを作ります。

メソッド

メソッド、メンバ変数については、沢山あるので全ては紹介しません。詳細は API 仕様を直接ご確認ください。

ここに挙げたのは、次のサンプルで利用するメソッドのみです。

サンプル

class TestCharacter{
	public static void main(String args[]){
		System.out.println("----インスタンスメソッドの利用----");
		//インスタンス化
		Character objChar1, objChar2;
		objChar1=new Character('a');
		objChar2=new Character('5');

		System.out.println("objChar1: "+objChar1.charValue());
		System.out.println("objChar2: "+objChar2.charValue());

		boolean bln=objChar1.equals(objChar2);
		System.out.println("objChar1=objChar2? "+bln);

		//static メソッドの利用
		System.out.println("----静的メソッドの利用------------");
		char ch='a';
		boolean bln1=Character.isLetterOrDigit(ch);
		boolean bln2=Character.isDigit(ch);

		System.out.println("ch: "+ch);

		if(bln1==false){
			System.out.println("汎用文字でも数字もありません。");
		}else if(bln2==false){
			System.out.println("汎用文字です。");

			boolean bln3=Character.isUpperCase(ch);
			if(bln3==false){
				char chU=Character.toUpperCase(ch);
				System.out.println("大文字にします: "+chU);
			}else{
				System.out.println("大文字です。");
			}

		}else{
			System.out.println("数字です。");
		}
	}
}

C:\Java>javac TestCharacter.java

C:\Java>java TestCharacter
----インスタンスメソッドの利用----
objChar1: a
objChar2: 5
objChar1=objChar2? false
----静的メソッドの利用------------
ch: a
汎用文字です。
大文字にします: A

32 ビット整数を表す基本データ型である int 型のラップクラスです。

クラス階層

java.lang.Object
  |
  +--java.lang.Number
        |
        +--java.lang.Integer

概要

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

Integer クラスは、プリミティブ型 int の値をオブジェクト内にラップします。Integer 型のオブジェクトには、型が int の単一のフィールドが入ります。

さらにこのクラスは、int を String に、String を int に変換する各種メソッドや、int の処理時に役立つ定数およびメソッドも提供します。

コンストラクタ

つまり、 Integer クラスは int 型か文字列型の変数/値を受け取って、オブジェクトを作ります。

メソッド

メソッド、メンバ変数については、沢山あるので全ては紹介しません。詳細は API 仕様を直接ご確認ください。

ここに挙げたのは、次のサンプルで利用するメソッドのみです。

サンプル

次のサンプルは、コマンドライン引数の文字列を Integer 型のオブジェクトにラッピングします。

• int 型、 double 型に変換します。
• 引数の文字列を、 static 型のメソッドを用いて 16 進、 8 進、 2 進での表現に変換します。
• 引数の文字列を、 static 型のメソッドを用いて int 型に変換します。

class TestInteger{
	public static void main(String args[]){
		//インスタンス化
		Integer objInt=new Integer(args[0]);
		System.out.println("objInt: "+objInt);

		//オブジェクトとの比較
		Integer objComp=new Integer(1011);
		boolean valBln=objInt.equals(objComp);
		System.out.println("objInt=1011? "+valBln);

		//int 型への変換
		int valInt=objInt.intValue();
		System.out.println("int: "+valInt);

		//double 型へ変換
		double valDbl=objInt.doubleValue();
		System.out.println("double: "+valDbl);

		//n 進数変換
		//int 型変数を n 進数に変換する
		String valBin, valHex, valOct;
		valBin=Integer.toBinaryString(valInt);
		valHex=Integer.toHexString(valInt);
		valOct=Integer.toOctalString(valInt);
		System.out.println("16進数: "+valHex);
		System.out.println(" 8進数: "+valOct);
		System.out.println(" 2進数: "+valBin);
		//文字列を n 進数の int 型に変換する
		int valInt2, valInt3;
		valInt2=Integer.parseInt(args[0]);
		valInt3=Integer.parseInt(args[0], 2);
		System.out.println("10 進数: "+valInt2);
		System.out.println(" 2 進数だと解釈したときの値: "+valInt3);
	}
}

引数を 2 進数表現だと解釈するメソッド parseInt(String s, 2) を使います。コマンドライン引数は 0 か 1 の組み合わせに限ってください。

C:\Java>javac TestInteger.java

C:\Java>java TestInteger 1011
objInt: 1011
objInt=1011? true
int: 1011
double: 1011.0
16進数: 3f3
 8進数: 1763
 2進数: 1111110011
10 進数: 1011
 2 進数だと解釈したときの値: 11

C:\Java>java TestInteger 11
objInt: 11
objInt=1011? false
int: 11
double: 11.0
16進数: b
 8進数: 13
 2進数: 1011
10 進数: 11
 2 進数だと解釈したときの値: 3

ここでは int 型のラップクラス、 Integer について紹介しましたが、他の整数値型 byte, short, long のラップクラス Byte, Short, Long についても同じです。