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 の場合もあります。このクラスは、マップの順序については保証しません。特に、ある期間に渡って一定の順序を保つことを保証しません。
HashMap() |
デフォルトの初期容量 (16) とデフォルトの負荷係数 (0.75) で空の HashMap を作成します。 |
HashMap(int initialCapacity) |
指定された初期容量とデフォルトの負荷係数 (0.75) で空の HashMap を作成します。 |
HashMap(int initialCapacity, float loadFactor)
| 指定された初期容量と負荷係数で空の HashMap を作成します。 |
HashMap(Map m) |
指定された Map と同じマッピングで新規 HashMap を作成します。 |
三番目のコンストラクタをつかえば、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