HashMapの注意点

Java コレクションフレームワーク

HashMapを使う上での注意点について説明します。

Map型変数を使う

HashMapオブジェクトを格納するには、HashMap型変数ではなくMap型変数を使います。

// HashMapオブジェクトの生成
Map<String, String> map = new HashMap<String, String>();

HashMapはMapの実装の一つに過ぎません。HashMapをMapとして使っているのであればMap型変数に格納した方が自然です。また、パフォーマンス上の問題で他のマップ（TreeMapなど）と差し替えることが容易になるなど、プログラムの汎用性が上がります。HashMap独自の操作が必要である場合（あまり思いつきませんが）を除いてMap型変数を使いましょう。

初期容量と負荷係数

HashMap生成時のパラメータとして、初期容量と負荷係数があります。


初期容量は、HashMapが内部的に保持しているハッシュテーブル自体のサイズ（デフォルトで16）です（ハッシュテーブルの仕組みについてはhttp://www.geocities.jp/ky_webid/algorithm/014.htmlを参照）。格納する要素の数に対してテーブルのサイズが著しく小さいと、ハッシュテーブルのパフォーマンスが劣化してしまいます。そのため、ハッシュテーブルがある程度いっぱいになると、自動的にハッシュテーブルの拡張（新たに大きなテーブルを生成して、要素を格納しなおす作業）が行われます。ハッシュテーブルがどの程度埋まるとテーブルの拡張を行うかという割合を表したものが負荷係数（デフォルトで0.75）です。

なぜハッシュテーブルがいっぱいになってから拡張を行わないのかというと、ハッシュテーブルのキーとなるハッシュ値は基本的に重複するものだからです。サイズ100のハッシュテーブルに100個の要素を挿入したとしても、ハッシュテーブルがすべて埋まることはまずありません*1。ハッシュ値の重複が起こっても要素が置き換えられるようなことは起こりませんが、パフォーマンスが劣化します。そのため、ハッシュテーブルがある程度埋まってきた段階でテーブルを拡張する必要があります。


基本的には初期設定のまま*2で使って問題ありません。

// 初期容量16、負荷係数0.75でHashMapを生成
Map<String, String> map = new HashMap<String, String>();


大量の要素を挿入したい場合は、初期容量を挿入する要素数 * 4 / 3に設定すると良いでしょう。この要素数 * 4 / 3というのは、この値に負荷係数0.75をかけたときにちょうど1となる値です。要素数が大体でしかわからない場合は、少し大きい目の値 * 4 / 3を目安にすると良いでしょう。

// 挿入する要素数n
int n = 100000;

// 初期容量n * 4 / 3、負荷係数0.75でHashMapを生成
Map<String, String> map = new HashMap<String, String>(n * 4 / 3);


挿入する要素の数がわかっていて、それ以上の要素を追加することがないのであれば負荷係数を大きく設定しても良いでしょう。

// 挿入する要素数n
int n = 100000;

// 初期容量n、負荷係数1.0でHashMapを生成
Map<String, String> map = new HashMap<String, String>(n, 1.0f);

ハッシュテーブルのサイズとIterator

ハッシュテーブルの性質を考えると、メモリが許せば容量を大きく設定しておけばパフォーマンスが高くなるように思えます。しかし、そこに落とし穴があります。

ハッシュテーブルから全要素を取り出す場合（Iteratorなどを用いる場合）、要素数に比べてハッシュテーブルのサイズが著しく大きいと、パフォーマンスが著しく低下します。これは、ハッシュテーブルから全要素を取り出すためにはテーブル全体を走査しなければならないためです。


ですので、初期容量を要素数に対して大きく設定しすぎない*3ように注意が必要です。挿入（put）、参照（get）、削除（remove）しか行わないのであれば、少々初期容量が大きくてもパフォーマンスに大きな劣化はありません。

同期化（スレッドセーフなHashMap）

Collections.synchronizedメソッドを用いることでスレッドセーフなHashMapを得ることができます。同期化を目的としてHashtableを使うのは望ましくありません（詳細はこちら）。

Map<String, String> map = Collections.synchronizedMap(new HashMap<String, String>());

TreeMapとの性能比較

基本的にHashMapはTreeMapより速いです。TreeMapの性質（要素をソートして取り出す）が必要にならない限り、HashMapを用いた方が良いでしょう。パフォーマンス比較の結果については
ハッシュは二分木（ツリー）より速い（ハッシュとツリーの速度比較）
をご覧下さい。

自作クラスをキーにする場合（equalsメソッドとhashCodeメソッドのオーバーライド）

PHPの連想配列などと違い、HashMapのキーはStringでなければならないわけではありません。Javaでは任意のクラスのインスタンスをキーにとることができます。ただし、正確かつ高速な動作を期待するためには、equalsメソッドとhashCodeメソッドを適切にオーバーライドすることが必要となります。


hashCodeメソッドとequalsメソッドはObjectクラスで定義されているメソッドで、すべてのクラスが持っているメソッドです（すべてのクラスはObjectを継承しています）。

equalsメソッド（戻り値はboolean）は、二つのインスタンスが同一のものである場合にtrueを返すように定義（オーバーライド）する必要があります。例えば、Stringクラスでは、同一の文字列に対してtrueを、Integerクラスでは同一の値に対してtrueを返すように定義されています。

hashCodeメソッド（戻り値はint）はハッシュ値*4を返すメソッドで、equalsメソッドがtrueを返す（同一の内容を表す）インスタンス同士は必ず同じ値を返す必要があります。ただし、equalsメソッドがfalseを返す（異なる内容を表す）インスタンス同士が同じ値を返しても構いません。あくまで、同一の内容を表すインスタンス同士が同じ値を返すことが規定されているだけです。とはいえば、異なる内容を表すインスタンス同士は異なるハッシュ値を返した方がHashMapのパフォーマンスが向上します。


例えば、年と月（2008年8月など）を表すクラス、YearMonthを考えてみましょう。年と月が等しいYearMonthは同一の内容を表すYearMonthとなります。equalsメソッドとhashCodeメソッドは次のように定義すれば良いでしょう。

// 年、月を表すクラス
class YearMonth {
	// 年
	private int year;
	// 月
	private int month;

	public YearMonth(int year, int month) {
		this.year = year;
		this.month = month;
	}

	// 自分自身とobjが同じYearMonthである場合のみtrueを返す。
	public boolean equals(Object obj) {
		// 対象がYearMonthオブジェクトか判別する。
		if (obj instanceof YearMonth) {
			// YearMonth型にキャストする。
			YearMonth yearMonth = (YearMonth) obj;
			// year、month共に等しい場合のみtrueを返す。
			return this.year == yearMonth.year && this.month == yearMonth.month;
		} else {
			// YearMonthオブジェクトでなければ異なるオブジェクトなのでfalseを返す。
			return false;
		}
	}

	// equalsメソッドがtrueになる二つのYearMonthオブジェクトは必ず同じ値を返す。
	// ただし、equalsメソッドがfalseとなる二つのYearMonthオブジェクトが
	// 必ず異なる値を返さなければならないわけではない。
	public int hashCode() {
		// このようにすれば、異なるYearMonthでは異なるハッシュ値を返す。
		return year * 12 + month;
	}
}

結論

  • HashMapオブジェクトはできるだけMap型変数に格納する。
  • 初期容量と負荷係数を適切に設定する。
  • 同期化を行う場合はCollections.synchronizedメソッドを用いる。
  • 自作クラスをキーにする場合には、equalsメソッドとhashCodeメソッドのオーバーライドを忘れずに。

*1:ハッシュテーブルの仕組みについてはhttp://d.hatena.ne.jp/jamey_star/20080225/1203879426、http://www.yuge.ac.jp/home/~nagao/teaching/algo_2003/Search/hash/、http://d.hatena.ne.jp/jamey_star/20080225/1203879426などが参考になる。

*2:引数なしコンストラクタでHashMapを生成すると、初期容量16、負荷係数0.75となる。

*3:一概にこのくらいとは言えないが、要素数の10倍、20倍になるような設定は良くないだろう。要素数が事前にわかっているのであれば要素数 * 4 / 3が望ましい。

*4:厳密には、hashCodeメソッドをさらに操作した値がHashMap内部で計算され、ハッシュテーブルのキーとして用いられている。