JavaのHashMapの仕組み – 内部メカニズムを解説

HashMapはJavaで最もよく使われるデータ構造の一つで、その効率の良さで知られています。HashMapのデータはキーと値のペアの形で格納されます。

この記事では、JavaのHashMapを紹介します。HashMapの一般的な操作について説明した後、内部的にどのように動作するのかを掘り下げていきます。ハッシュ関数とインデックス計算がどのように行われるかを理解します。

Javaにおける `HashMap`とは

HashMapは、Javaコレクションフレームワークの一部であるMapインターフェイスを実装しています。

ハッシュは、ハッシュ関数を使用して、任意のサイズの入力を固定サイズの出力に変換する技術です。生成された出力はハッシュコードと呼ばれ、Javaでは整数値で表されます。

一般的な操作

上で説明したように、HashMap内のデータはキーと値のペアの形で格納されます。

HashMapでサポートされる一般的な操作を以下に示します。

挿入

このメソッドは新しいキーと値のペアをHashMapに挿入します。
キーと値のペアの插入順序は保証されません。
插入中、既にキーが存在している場合、引数として渡された新しい値に既存の値が置き換えられます。
HashMapには null キーを一度だけ插入できますが、null 値は複数指定できます。

この操作の方法のシグネチャは以下に示されます。その後、例があります。

public V put(K key, V value)

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);

上のコードでは、String型のキーとInteger型の値を追加するHashMapの例があります。

取得:

指定されたキーに割り当てられた値を取得します。
HashMapにキーが存在しない場合は nullを返します。

この操作の方法のシグネチャは以下に示されます。その後、例があります。

public V get(Object key)

Integer value = map.get("apple"); // 1を返す

上のコードでは、appleキーに割り当てられた値を取得しています。

他にも一般的な操作があります。

remove：指定されたキーのキーと値のペアを削除します。キーが見つからない場合はnullを返します。
containsKey：指定されたキーがHashMapに存在するかどうかを確認します。
containsValue：指定された値がHashMapに存在するかどうかを確認します。

`HashMap`の内部構造

HashMapは、バケツまたはビンの配列を内部的に使用します。各バケツは、Node型のリンクリストであり、HashMapのキーと値のペアを表します。

static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

上記では、HashMapのキーと値のペアを格納するために使用されるNodeクラスの構造が示されています。

Nodeクラスには、以下のフィールドがあります：

hash：キーのhashCodeを参照します。
key：キーと値のペアのキーを参照します。
value：キーに関連付けられた値を参照します。
next: 次のノードへの参照を行います。

HashMapは根本的にhash tableの実装に基づいており、性能は初期容量と荷重係数に依存します。Hash tableクラスの原始的なjavadocsでは、これらの2つのパラメーターを以下のように定義しています。

容量はhash table内のバケットの数であり、初期容量はhash tableを作成したときの容量です。
荷重係数は、hash tableが自動的に拡大される前に满たすことができる程度の hash tableの満杯率を表します。

次に、HashMapにおける基本的な操作、putとgetの仕組みを理解しましょう。

ハッシュ関数

关键字と値のペアを插入（`put`）した際に、`HashMap`はまずキーのハッシュコードを計算します。このハッシュ関数は、キーに対する整数を計算します。クラスは`Object`クラスの`hashCode`メソッドを使用するか、このメソッドをオーバライドして独自の実装を提供することができます。ハッシュコードの約束についてはここを読むことができます。その後、ハッシュコードは位数の16ビットをXOR（排他的OR）运算して、より均等な分布を実現します。

XORは、2つのビットを比較し、異なる場合は1、同じ場合は0になるビット演算です。この場合、ハッシュコードとその上位16ビット（unsigned right shift `>>>>` 演算子を使用して得られる）の間でビット演算のXOR运算を行い、ビットを混ぜることで、より均等に分布するハッシュコードを得ます。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

上記は、`HashMap`クラスの静的なハッシュメソッドを示しています。

このアイデアは、各キーに固有のハッシュコードを持つことですが、ハッシュ関数は異なるキーに同じハッシュコードを生成することもあります。これは衝突と呼ばれる状況に導きます。衝突を処理する方法は次の節で説明します。

インデックス計算

キーのハッシュコードが生成された後、`HashMap`はバケットの配列内のインデックスを計算し、キーと値のペアが格納される場所を決定します。これは、配列の長さが2の幂である場合、模运算を効率的に行うためのビット演算として行われます。

int index = (n - 1) & hash;

ここで、

バケット配列の長さをnとして計算しています。インデックスを計算した後、キーはそのインデックスにバケット配列に保存されます。しかし、複数のキーが同じインデックスになると衝突が発生します。このような状況下で、HashMapは2つの方法のいずれかで处理します。

Chaining/Linking: 配列内の各バケットはノードの LinkedList です。特定のインデックスに既にキーが存在し、もう一つのキーが同じインデックスにハッシュされた場合、それはリストに追加されます。
Treeify: ノードの数が一定の閾値を超えると、リンクリストが树状结构として変換されます（これは Java 8 で導入されました）。

static final int TREEIFY_THRESHOLD = 8;

これは treeification を決定する閾値です。

したがって、良いハッシュ関数を持っておくことは、キーをバケット間で平均的に分布させ、衝突の可能性を最小限にするために非常に重要です。

取得（get）と削除（remove）操作は、挿入（put）操作と同様に行われます。以下はその方法です。

取得（get): ハッシュ関数を使用してハッシュコードを計算する -> ハッシュコードを使用してインデックスを計算する -> LinkedList または树状结构を穿越して、一致するキーのノードを找到する。
削除（remove）：ハッシュ関数を使用してハッシュコードを計算し、その後、ハッシュコードを使用してインデックスを計算し、リンクリストまたは树からノードを削除する。

時間的な复杂度

HashMapの基本的な操作、put、get、removeなどは、キーが均等に分布されることを前提に、常にO(1)の定数時間の性能を提供する。キーの分布が悪く、多くの衝突が発生する場合、これらの操作は線形時間の Complexity O(n)に衰える可能性があります。

トリー化によって、長い衝突の连锁をバランスのある树に変換することにより、Lookup操作の効率をより良い対数時間 Complexity O(log n)に改善することができます。

同期

HashMapの実装は同期されていません。複数のスレッドが同一のHashMapインスタンスに并发してアクセスし、マップを巡回している場合、スレッドの中の1つがマップ上でキー-値のマッピングを追加または削除する structural modificationを行うと、ConcurrentModificationExceptionが発生します。

これを防止するためには、Collections.synchronizedMapメソッドを使用してスレッド Safeなインスタンスを作成することができます。

結論

要するに、HashMapの内部工作机制を理解することは、開発者が情報を持って決定をしたりすることが非常に重要です。键との対応、衝突の発生や避け方を知ることができるために、HashMapを効果的に、効率的に使用することができます。

Javaにおける HashMapとは