JavaにおけるHashMapの内部動作を徹底解説

はじめに

JavaでHashMapがどのようにデータを管理しているのか、その内部動作を理解することは、パフォーマンスの最適化やトラブルシューティングにおいて非常に重要です。本記事では、hashCode()とequals()の役割、バケット（bucket）の仕組み、インデックスの計算方法について、サンプルコードを交えながら詳しく解説します。

hashCode()メソッドとは

Javaでは、hashCode()関数を使用してオブジェクトのハッシュコードを取得します。このメソッドはすべてのクラスの親であるObjectクラスで定義されており、オブジェクト参照のメモリ情報を整数値（int）として返します。

hashCode()はネイティブ（native）メソッドとして実装されているため、Javaのコードから直接オブジェクトの参照（メモリアドレス）を取得することはできません。

public native int hashCode();

HashMapのパフォーマンスを最大限に引き出すためには、このhashCode()を適切に実装・活用することが重要です。基本的に、この関数はバケットとインデックスの計算に使用されます。

バケット（bucket）とは

バケットとは、HashMap内でノード（要素）を格納するための入れ物となる要素です。1つのバケットには複数のノードが格納される場合があり、その場合ノード同士は連結リスト（Linked List）のデータ構造によって連結されます。

HashMapの容量は、バケット数と負荷係数（load factor）から以下の式で計算できます。

容量 = バケット数 × 負荷係数

equals()メソッドとは

equals()関数は、2つのオブジェクトが等しいかどうかを判定するために使用されます。こちらもObjectスーパークラスで提供されているメソッドですが、独自のクラスでカスタマイズした実装にオーバーライドすることが可能です。

この関数は、比較対象の2つのオブジェクトが等しければtrue、等しくなければfalseを返します。

インデックスの計算方法

HashMapでは、配列のサイズが必要以上に大きくならないよう、またOutOfMemoryExceptionを回避するために、インデックス値が生成されます。配列のインデックスを求める公式は以下の通りです。

Index = hashCode(key) & (n-1)　※ n はバケット数を表す

実装例

それでは、実際のコード例を見てみましょう。

import java.util.HashMap;
class hash_map {
    String key;
    hash_map(String key) {
        this.key = key;
    }
    @Override
    public int hashCode() {
        int hash = (int) key.charAt(0);
        System.out.println("The hash code for key : " + key + " = " + hash);
        return hash;
    }
    @Override
    public boolean equals(Object obj) {
        return key.equals(((hash_map) obj).key);
    }
}
public class Demo {
    public static void main(String[] args) {
        HashMap my_map = new HashMap();
        my_map.put(new hash_map("This"), 15);
        my_map.put(new hash_map("is"), 35);
        my_map.put(new hash_map("a"), 26);
        my_map.put(new hash_map("sample"), 45);
        System.out.println("The value for key 'this' is : " + my_map.get(new hash_map("This")));
        System.out.println("The value for key 'is' is: " + my_map.get(new hash_map("is")));
        System.out.println("The value for key 'a' is: " + my_map.get(new hash_map("a")));
        System.out.println("The value for key 'sample' is: " + my_map.get(new hash_map("sample")));
    }
}

実行結果

The hash code for key : This = 84
The hash code for key : is = 105
The hash code for key : a = 97
The hash code for key : sample = 115
The hash code for key : This = 84
The value for key 'this' is : 15
The hash code for key : is = 105
The value for key 'is' is: 35
The hash code for key : a = 97
The value for key 'a' is: 26
The hash code for key : sample = 115
The value for key 'sample' is: 45

コードの解説

この例では、hash_mapという名前のクラスが定義され、文字列型のフィールドとコンストラクタを持っています。

まず、hashCode()メソッドがオーバーライドされています。ここでは、キー文字列の先頭文字を整数値に変換してハッシュコードとして返し、その値をコンソールに出力しています。

次に、equals()メソッドもオーバーライドされており、渡されたオブジェクトのキーが現在のキーと一致するかどうかを判定します。

Demoクラスのmainメソッドでは、HashMapの新しいインスタンスを作成し、put()メソッドを使って要素を追加しています。その後、get()メソッドで各キーに対応する値を取得し、コンソールに出力しています。

実行結果から分かるように、キーの取得時にもhashCode()が呼び出され、同じキーに対しては常に同じハッシュコードが返されることで、正しく値を取り出せる仕組みになっています。