HashMapの最適化

参考資料
http://docs.oracle.com/javase/jp/8/api/java/util/HashMap.html

HashMapのインスタンスには、その性能に影響を与える2つのパラメータである初期容量および負荷係数があります。容量はハッシュ表のバケット数であり、初期容量は単純にハッシュ表が作成された時点での容量です。負荷係数は、ハッシュ表がどの程度いっぱいになると、その容量が自動的に増加されるかの基準です。ハッシュ表エントリ数が負荷係数と現在の容量の積を超えると、ハッシュ表のハッシュがやり直され (つまり、内部データ構造が再構築され)、ハッシュ表のバケット数は約2倍になります。

JavaのHashMapのコンストラクタは、HashMap内部にもつHashTableの初期容量と負荷係数の値を渡せるようになっている。
初期容量のデフォルトは16、負荷係数は0.75

ドキュメントには、HasmMapの要素数が初期容量と負荷係数の積を超えると内部データ構造が再構築されるとある。
この再構築(rehash)が結構コストが高い。

コンストラクタに何も渡さなかった場合、
16(初期容量のデフォルト) * 0.75(負荷係数のデフォルト) = 12
を超えた時点でrehashが実行される。

格納される要素数がある程度事前にわかっている場合、初期容量に対して適切な値を設定してインスタンスを生成すると効率的。
ただ大きい値を設定すれば良いというわけではない。
ドキュメントにも、

反復処理の性能が重要な場合は、初期容量をあまり高く(負荷係数をあまり低く)設定しないことが非常に重要

とある

初期容量の値は、以下の計算で求めると良い。

挿入される要素数(予想される要素数) * 4/3

この要素数 * 4/3という値は、負荷係数0.75を掛けた時にちょうど1になる値
負荷係数はほとんどの場合、変更する必要は無いと思う。

簡単に処理時間を計測してどの程度効果があるのか試してみる。

サンプルコード

package main;

import java.util.HashMap;

public class HashMapSample {

    public static void main(String[] args) {

        long start;
        long stop;
        HashMap<Integer, Integer> map;

        start = System.currentTimeMillis();
        map = new HashMap<Integer, Integer>();
        for (int i = 0; i < 100000; i++) {
            map.put(i, i);
        }
        stop = System.currentTimeMillis();
        System.out.println("デフォルト:" + (stop - start) + "msec");

        start = System.currentTimeMillis();
        map = new HashMap<Integer, Integer>(130000);
        for (int i = 0; i < 100000; i++) {
            map.put(i, i);
        }
        stop = System.currentTimeMillis();
        System.out.println("初期容量130000:" + (stop - start) + "msec");

    }

}

結果

デフォルト:44msec
初期容量130000:23msec

今回は要素数を多めにして試してみたので、時間的には大きめに出てる。
要素数少なめでも1msecぐらいは効果があったので、何回も実行されるような箇所なら地味に効いてきそう。