【Java】HashMapの基本動作と自作クラスをキーに指定する注意点など

Java
スポンサーリンク

Java で使用頻度の高い HashMap について内部動作や注意点などを簡単にまとめました。特に自作クラスをキーに使用したい場合は内部動作が分かっていないと危険ですね。

HashMapの内部動作

HashMap は内部にハッシュテーブル（配列）を保持していて、キーと値をputすると HashMap はキーを内部でハッシュ関数（HashMap#hash）に通します。そしてその出力結果をインデックスとして、キーと値はハッシュテーブルに格納されます。キーが null の場合は 0 がインデックスになります。

値を取得getする場合は、まずキーをハッシュ関数（HashMap#hash）に通して結果を得ます。この結果をハッシュテーブルのインデックス値とみなして、配列から要素を取り出します。この要素はキーと値のペアであり、まず最初にキーのハッシュコードが一致するかを判定して、最後にこのキーとgetで指定したキーが==又はequalsで一致すれば値を返します。ハッシュコードが一致するか判定している理由は「オブジェクトが等しいならば、ハッシュコードは等しい」という大前提があるためです。

HashMapの初期容量と負荷係数

ハッシュ関数の出力値の範囲は有限（ハッシュテーブルのサイズの範囲）です。つまり異なる値に対して同じハッシュ値になることがありえます。同じ値になった場合、HashMap は内部にバランス木が作成されるため、ハッシュ関数で求めたインデックスでハッシュテーブルから要素を取り出すと、バランス木をたどってキーの完全一致の比較で求める値を取得します。また、ハッシュテーブルはいっぱいになってくると自動的に拡張されるようになっていますが、ハッシュ関数の再計算が必要だったり、これらの処理は相対的に重い処理となります。

このような理由からハッシュテーブルのサイズは適切に指定する必要があるので、HashMap のコンストラクタで初期容量と負荷係数を指定します。初期容量のデフォルトは16で、負荷係数は0.75です。負荷係数が0.75というのは、初期容量が16の場合、16*0.75=12でハッシュテーブルが12個埋まったら拡張されるというものです。とはいえ基本的には初期設定のまま使っても問題ないと思いますが、大量に要素を格納することがわかっていたり、パフォーマンスが重要な場合は検討しましょう。

自作クラスをキーにする場合

HashMap のキーには自作クラスを使用することもできますが、hashCodeメソッドとequalsメソッドを適切にオーバーライドする必要があります。ただしその場合、自作クラスは不変クラスであることが望ましいです。通常キーとして使用される String や Integer は元々不変クラスなので問題ありません。

不変クラスとは以下のような特徴を持っています。

  • メンバ変数を private にする。
  • メンバ変数を final にして値の再代入を防ぐ。
  • メンバ変数はコンストラクタで初期化する。
  • メンバ変数の変更メソッドを実装しない。
  • final クラスにして拡張継承させない。

HashMap のキーに使用するクラスのサンプルは以下のようになります。

import java.util.Objects;

public final class SearchKey {
    private final int id;
    private final String name;

    public SearchKey(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof SearchKey) {
            SearchKey key = (SearchKey) obj;
            return this.id == key.id && this.name.equals(key.name);
        } else {
            return false;
        }
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }

}

HashMap のキーに使用しても値が取得できていることがわかります。ここでhashCodeを実装していなかったとしたら、Object#hashCodeが使われる事になり、インスタンスが違うだけでハッシュ関数の結果も変わってくるので、equalsの結果が true でも取得できなくなってしまいます。

SearchKey key = new SearchKey(1, "太郎");
Map<SearchKey, String> test = new HashMap<>();
test.put(key, "test");
System.out.println(test.get(new SearchKey(1, "太郎")));

// 結果
test

注意する点として、例えば以下のようにputした後にキーの値を変えた場合、ハッシュ値は変わらないため値が取得できなくなってしまいます（HashMap で保持しているハッシュ値は「太郎」のまま）。このような事が起こるので不変クラスにするべきというわけですね。

SearchKey key = new SearchKey(1, "太郎");
Map<SearchKey, String> test = new HashMap<>();
test.put(key, "test");

key.setName("山田");   // Setterが実装されている場合
System.out.println(test.get(key));
System.out.println(test.get(new SearchKey(1, "山田")));

// 結果
null
null

また、Java8 からは自作クラスをキーに使う場合は Comparable を実装した方がパフォーマンス面で大分違うみたいです。
 Java8からはHashMapの性能のためにComparableを実装しておいた方がいい - interprism's blog