| ToC |

インタフェースMapの実装クラス

Revised: May/10th/2008; Since: Feb./23rd/2003

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

HashMapの継承階層

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

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

HashMapの概要

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

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

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

HashMapの動作特性

Map型クラスは、キーによる検索に対して最適化されています。値による検索は低速になります。例えば、containsKey()よりもcontainsValue()の方が低速です。

キーの順序は一般に保証されません。キーの順序を保証する必要がある場合は、SortedMapインタフェースの実装クラスを使います。TreeMapが代表的です。SortedMapではキーの順序が保証されているので、firstKey(), lastKey(), tailMap()など、キーの順序に依存したメソッドが追加されています。

HashMap, LinkedHashMap, TreeMapの動作特性は、ArrayListに対するその他のListと同じです。

LinkedHashMapでは、TreeMap関連の負担の増大を負わずに、HashMapおよびHashtableによる、無指定された一般には無秩序な順序からクライアントを守ります。この実装を使用して、当初のマップの実装にかかわらず、当初と同じ順序を持つマップのコピーを生成することができます。

void foo(Map m) {
Map copy = new LinkedHashMap(m);
         ...
     }

TreeMapでは、Comparatorによって明示的にキーをソートできます。

EnumMapは、Enumクラスをキーにとることができて、順序は自然順序付けされます。キーは内部実装では配列として保持されます。

HashMapのコンストラクタ

コンストラクタの概要
HashMap()
          デフォルトの初期容量 (16) とデフォルトの負荷係数 (0.75) で空の HashMap を作成します。
HashMap(int initialCapacity)
          指定された初期容量とデフォルトの負荷係数 (0.75) で空の HashMap を作成します。
HashMap(int initialCapacity, float loadFactor)
          指定された初期容量と負荷係数で空の HashMap を作成します。
HashMap(Map<? extends K,? extends V> m)
          指定された Map と同じマッピングで新規 HashMap を作成します。

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

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

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

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

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

Java API仕様の記述も参照してください。

サンプル

HashMapとTreeMapの例

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

import java.util.Map;
import java.util.HashMap;
import java.util.TreeMap;

class MapGetDemo {
	public void get(Map<String, Integer> map) {
		// J2SE 5.0以上
		for (String str : map.keySet()) {
			System.out.println("\t" + str + ": " + map.get(str));
		}
	}
}
class TestMap {
	public static void main(String[] args) {
		// HashMapのインスタンス化
		// J2SE 5.0以上
		Map<String, Integer> mountains = new HashMap<String, Integer>();

		String[] names1 = {"Everest", "K2", "Kangchenjunga", "Lhotse", "Makalu"};
		int[] heights1 = {  8848,      8611, 8586,            8511,     8463};
		String[] names2 = {"富士山", "北岳", "奥穂高岳", "間ノ岳", "槍ヶ岳"};
		int[] heights2 = {  3776,     3192,   3190,       3189,     3180};
		
		System.out.println("HashMap: ");
		// HashMapへのput()
		for (int i = 0; i < heights1.length; i++) {
			mountains.put(names1[i], heights1[i]);
		}
		MapGetDemo getDemo = new MapGetDemo();
		getDemo.get(mountains);

		System.out.println("HashMap: ");
		// HashMapへのput()
		for (int i = 0; i < heights2.length; i++) {
			mountains.put(names2[i], heights2[i]);
		}
		getDemo.get(mountains);
		
		System.out.println("TreeMap: ");
		// HashMapからTeeMapへの変換
		// J2SE 5.0以上
		mountains = new TreeMap<String, Integer>(mountains);
		getDemo.get(mountains);
	}
}

Mapの型パラメータは、カンマ区切りで二つになります。

Map<String, Integer> mountains = new HashMap<String, Integer>();

実行結果リストにより、HashMapでは明示的な順序付けがされていないのに対して、TreeMapではキーの文字コード順にソートされていることが分かります。TreeMapは、キーの自然順序付けに従って、またはマップ作成時に提供されるComparatorによってソートされます。

TestMap.javaの実行結果:

D:\java>javac -Xlint TestMap.java

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

D:\java>

EnumMapの例

J2SE 5.0以上で追加された言語仕様Enumを用いてコレクションクラスは拡張されています。Map型のクラスはEnumMapです。

import java.util.EnumMap;

enum Shortcuts {
	FIND,
	FIND_NEXT,
	SMALLER,
	LARGER,
	UNDO,
	COPY,
	CUT,
	PAST,
	WINDOW_NEW,
	PRINT,
	RELOAD,
	LIST_BOOKMARK,
	LIST_HISTORY,
	TAB_OPEN,
	TAB_CLOSE,
	TAB_NEXT
}

class TestEnumMap {
	public static void main(String[] args) {
		EnumMap<Shortcuts, String> firefoxKeys = new EnumMap<Shortcuts, String>(Shortcuts.class);
		firefoxKeys.put(Shortcuts.FIND,          "Ctrl-f");
		firefoxKeys.put(Shortcuts.FIND_NEXT,     "Ctrl-g");
		firefoxKeys.put(Shortcuts.COPY,          "Ctrl-c");
		firefoxKeys.put(Shortcuts.CUT,           "Ctrl-x");
		firefoxKeys.put(Shortcuts.PAST,          "Ctrl-v");
		firefoxKeys.put(Shortcuts.PRINT,         "Ctrl-p");
		firefoxKeys.put(Shortcuts.RELOAD,        "Ctrl-r");
		firefoxKeys.put(Shortcuts.TAB_OPEN,      "Ctrl-t");
		firefoxKeys.put(Shortcuts.TAB_CLOSE,     "Ctrl-w");
		firefoxKeys.put(Shortcuts.TAB_NEXT,      "Ctrl-tab");
		firefoxKeys.put(Shortcuts.WINDOW_NEW,    "Ctrl-n");
		firefoxKeys.put(Shortcuts.UNDO,          "Ctrl-z");
		firefoxKeys.put(Shortcuts.SMALLER,       "Ctrl--");
		firefoxKeys.put(Shortcuts.LARGER,        "Ctrl-+");
		firefoxKeys.put(Shortcuts.LIST_BOOKMARK, "Ctrl-b");
		firefoxKeys.put(Shortcuts.LIST_HISTORY,  "Ctrl-h");
		
		for (Shortcuts key : Shortcuts.values()) {
			System.out.println(key + "\t : \t" + firefoxKeys.get(key));
		}
	}
}

D:\java>javac -Xlint TestEnumMap.java

D:\java>
D:\java>java TestEnumMap
FIND     :      Ctrl-f
FIND_NEXT        :      Ctrl-g
SMALLER  :      Ctrl--
LARGER   :      Ctrl-+
UNDO     :      Ctrl-z
COPY     :      Ctrl-c
CUT      :      Ctrl-x
PAST     :      Ctrl-v
WINDOW_NEW       :      Ctrl-n
PRINT    :      Ctrl-p
RELOAD   :      Ctrl-r
LIST_BOOKMARK    :      Ctrl-b
LIST_HISTORY     :      Ctrl-h
TAB_OPEN         :      Ctrl-t
TAB_CLOSE        :      Ctrl-w
TAB_NEXT         :      Ctrl-tab

D:\java>

<<PREV | ToC | NEXT>>

Copyright © 2003-2008 SUGAI, Manabu. All Rights Reserved.