<<PREV | ToC | NEXT>>

HashMap クラス

Revised: Aug./4th/2003; Since: Feb./23rd/2003

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

<<PREV | ToC | NEXT>>