JavaScriptのハッシュテーブル：データ構造の基礎と実装方法を徹底解説

ハッシュテーブル（Hash Table）は、データを連想形式で格納するデータ構造です。ハッシュテーブルでは、データは配列形式で保持され、それぞれのデータ値に固有のインデックス値が割り当てられます。目的のデータのインデックスさえ分かれば、データへのアクセスは非常に高速に行えます。

そのため、ハッシュテーブルはデータサイズの大小にかかわらず、挿入操作も検索操作も非常に高速に実行できるデータ構造となっています。ハッシュテーブルは配列を記憶領域として利用し、要素を挿入または検索すべきインデックスを生成するために「ハッシュ」という技法を用います。

ハッシュ化（Hashing）とは

ハッシュ化とは、キー値の範囲を配列のインデックスの範囲へ変換する手法のことです。ここでは、モジュロ演算子（%）を使ってキー値からインデックスを算出します。

例として、サイズ20のハッシュテーブルに次のアイテムを格納するケースを考えてみましょう。各アイテムは (key, value) の形式で表されます。

ここでは、キーを受け取りテーブル用のインデックスを生成するハッシュ関数を使用しています。生成されたインデックスにより、値がどこに格納されているかが判明します。あるキーに関連付けられた値を検索したい場合も、そのキーに対して再度ハッシュ関数を実行するだけで、ほぼ一定時間（O(1)）で値を取得できます。

ただし、適切なハッシュ関数を設計するのは決して簡単ではありません。具体的な例を見てみましょう。

具体例：衝突（コリジョン）の発生

たとえば、次のようなハッシュ関数を用意したとします。

function modBy11(key) {
    return key % 11;
}

この関数を、格納したいキーと値のペアに対して実行すると、結果は次のようになります。

• (15, 20) → ハッシュコード：4
• (25, 39) → ハッシュコード：3
• (8, 55) → ハッシュコード：8
• (26, 84) → ハッシュコード：4

ここで問題が発生しています。(15, 20) を先に格納した後、同じハッシュ関数でキー26を処理すると、インデックス4という同じ場所にエントリを格納しようとします。この現象を「衝突（コリジョン）」と呼びます。

衝突に対処するためには、あらかじめ衝突処理の仕組みを定義しておく必要があります。代表的なシンプルな衝突解決アルゴリズムとして、次の2つがよく知られています。

線形探査法（Linear Probing）

このアルゴリズムでは、空きセルが見つかるまで配列の次のセルを順番に調べていくことで、格納先となる空き位置を探索します。上記の例では、インデックス4がすでに埋まっているため、隣のインデックス5に格納します。

分離チェーン法（Separate Chaining）

この実装方式では、ハッシュテーブルの各位置にリスト（連結リストなど）を関連付けます。衝突が発生するたびに、そのリストの末尾へキーと値のペアを追加していきます。ただし、チェーンが伸び続けると検索時間が大幅に増大する可能性がある点に注意が必要です。

HashTableクラスの実装

ハッシュテーブルの仕組みと衝突解決の方法が理解できたところで、実際にHashTableクラスを実装してみましょう。

実装するメソッド一覧

• put(key, value)：新しいキーと値のペアをハッシュテーブルに追加します
• get(key)：指定したキーに関連付けられた値を取得します
• remove(key)：テーブルから指定したキーのペアを削除します
• forEach()：すべてのキーと値のペアを反復処理できるようにします
• static join()：2つのハッシュテーブルを結合して新しいテーブルを生成する静的メソッドです