JavaScriptでハッシュテーブルに要素を追加する方法（チェイン法による衝突解決）

ハッシュテーブルへ要素を追加する際に最も重要なのが「衝突（コリジョン）」の解決です。本記事では、チェイン法（Chaining／連鎖法）と呼ばれる手法を使って衝突を処理する方法を解説します。

チェイン法以外にも、オープンアドレス法などさまざまな衝突解決アルゴリズムが存在します。興味のある方は Wikipedia の Hash table ページを参考にしてください。

ハッシュテーブルへの要素追加の実装

ここでは説明をシンプルにするため、整数のみを対象とするハッシュ関数を作成します。より複雑なハッシュアルゴリズムを採用すれば、任意のオブジェクトをキーとしてハッシュ化することも可能です。

以下は、キーと値のペアをハッシュテーブルに登録する put メソッドの実装例です。

put メソッドのコード例

put(key, value) {
    let hashCode = hash(key);

    for(let i = 0; i < this.container[hashCode].length; i ++) {

        // 同じキーがすでに存在する場合は
        // 既存の値を新しい値で上書きする
        if(this.container[hashCode][i].key === key) {
            this.container[hashCode][i].value = value; return;
        }
    }

    // キーと値のペアを配列の末尾に追加する
    this.container[hashCode].push(new this.KVPair(key, value));
}

コードのポイント

• ハッシュ値の計算：hash 関数を使ってキーから格納先のインデックス（バケット位置）を求めます。
• 既存キーのチェック：同じバケット内に同一のキーが存在する場合は、値だけを更新して処理を終了します。
• 新規ペアの追加：同じキーが存在しない場合は、KVPair オブジェクトをそのバケットの配列末尾に push します。

動作確認

実際にこのメソッドを使って、複数のデータをハッシュテーブルに追加してみましょう。

let ht = new HashTable();
ht.put(10, 94); ht.put(20, 72);
ht.put(30, 1);
ht.put(21, 6);
ht.put(15, 21);
ht.put(32, 34);
ht.display();

出力結果

このコードを実行すると、次のような出力が得られます。

0:
1:
2:
3:
4: { 15: 21 }
5:
6:
7:
8: { 30: 1 }
9: { 20: 72 }
10: { 10: 94 } -->{ 21: 6 } -->{ 32: 34 }

出力を見ると、キー 10・21・32 がすべて同じバケット（インデックス10）にマッピングされていることがわかります。このように、異なるキーが同じバケットに割り当てられる現象が「衝突」です。チェイン法では、連結リストのように要素をつなげて保存することで、この衝突を効率的に解決しています。