JavaScriptでHashTableクラスを自作する！完全実装コードと使い方を解説

ハッシュテーブル（Hash Table）は、キーと値のペアを高速に管理できる代表的なデータ構造です。キーをハッシュ関数に通して得られた「ハッシュ値」をインデックスとして使うため、平均O(1)の計算量で要素の追加・検索・削除が行えます。

JavaScriptには標準でMapやObjectが用意されていますが、ここではハッシュテーブルの内部構造を理解するために、HashTableクラスをゼロから実装します。以下の実装では、チェイン法（Separate Chaining）を採用しており、ハッシュ値の衝突（コリジョン）が発生しても、複数の要素を同じバケットに格納できるようになっています。もちろん、より効率的なデータ構造や衝突解決アルゴリズムを採用すれば、さらに改良することも可能です。

HashTableクラスの完全な実装コード

class HashTable {
    constructor() {
        this.container = [];
        // コンテナを空の配列（バケット）で埋める。
        // 衝突が起きた場合に、この中へさらに要素を追加できる
        for (let i = 0; i < 11; i++) {
            this.container.push([]);
        }
    }

    display() {
        this.container.forEach((value, index) => {
            let chain = value
                .map(({ key, value }) => `{ ${key}: ${value} }`)
                .join(" --> ");
            console.log(`${index}: ${chain}`);
        });
    }

    put(key, value) {
        let hashCode = this.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));
    }

    get(key) {
        let hashCode = this.hash(key);
        for (let i = 0; i < this.container[hashCode].length; i++) {
            // チェインの中から該当する要素を探す
            if (this.container[hashCode][i].key === key) {
                return this.container[hashCode][i];
            }
        }
        return undefined;
    }

    remove(key) {
        let hashCode = this.hash(key);

        for (let i = 0; i < this.container[hashCode].length; i++) {
            // チェインの中から該当する要素を探す
            if (this.container[hashCode][i].key === key) {
                this.container[hashCode].splice(i, 1);
                return true;
            }
        }
        return false;
    }

    hash(key) {
        return key % 11;
    }

    forEach(callback) {
        // 各チェインに対して
        this.container.forEach(elem => {
            // 各チェイン内のKVペアごとにコールバックを呼び出す
            elem.forEach(({ key, value }) => callback(key, value));
        });
    }

    static join(table1, table2) {
        // 引数がどちらもHashTableであることを確認
        if (!table1 instanceof HashTable || !table2 instanceof HashTable) {
            throw new Error("Illegal Arguments");
        }

        let combo = new HashTable();
        table1.forEach((k, v) => combo.put(k, v));
        table2.forEach((k, v) => combo.put(k, v));
        return combo;
    }
}

HashTable.prototype.KVPair = class {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
};

各メソッドの解説

constructor（コンストラクタ）

コンストラクタでは、空の配列を11個持つcontainerを作成します。この各配列が「バケット」となり、ハッシュ値の衝突が発生した場合でも、同じバケット内に複数のキーと値のペアを連結して保持できます。

hash（ハッシュ関数）

hash()は、キーを11で割った余り（剰余）をハッシュ値として返す、最もシンプルなハッシュ関数です。バケット数と同じ11を使うことで、結果が必ず0〜10の範囲に収まります。なお、この実装は数値キーを前提としているため、文字列キーを扱いたい場合は、文字コードを合計するなどの別のハッシュ関数を用意する必要があります。

put（要素の追加・更新）

put()は、キーからハッシュ値を計算し、対応するバケットに新しいKVペアを追加します。まず既存のチェインを走査し、同じキーが見つかった場合は値を上書きして終了します。これにより、重複キーによる不整合を防いでいます。

get（要素の取得）

get()は、ハッシュ値で特定したバケット内だけを線形探索し、一致するキーを持つペアを返します。テーブル全体を検索する必要がないため高速です。該当する要素が存在しない場合はundefinedを返します。

remove（要素の削除）

remove()は、get()と同様にバケット内を探索し、一致するキーを見つけたらsplice()で取り除きます。削除に成功すればtrue、キーが存在しなければfalseを返します。

display（内容の表示）

display()はデバッグ用のメソッドで、すべてのバケットの中身を「{ キー: 値 } --> …」という形式でコンソールに出力します。チェイン法の動きを視覚的に確認できて便利です。

forEach（全要素の反復処理）

forEach()は、テーブルに格納されたすべてのキーと値のペアに対して、指定したコールバック関数を実行します。ネストしたforEachによって、外側のバケットと内側のチェインを順番にたどっています。

join（静的メソッド：テーブルの結合）

静的メソッドjoin()は、2つのHashTableを受け取り、両方の要素を含む新しいHashTableを返します。内部的にはforEach()で各テーブルの要素を取り出し、新しいテーブルへput()しています。同じキーが両方に存在する場合は、後から渡したテーブル（table2）の値で上書きされます。

※注意：元のコードのif (!table1 instanceof HashTable || ...)は、演算子の優先順位の関係で意図どおりに動作しません。正しくはif (!(table1 instanceof HashTable) || !(table2 instanceof HashTable))のように括弧を付ける必要があります。

KVPair（キーと値のペアクラス）

KVPairは、キーと値のセットを保持するための小さな補助クラスです。HashTable.prototypeに登録することで、クラス定義の外に置かれていてもthis.KVPair経由でアクセスできるようになっています。

使用例

const ht = new HashTable();

// 要素の追加（キー % 11 でバケットが決まる）
ht.put(10, 94); // バケット10へ
ht.put(17, 76); // バケット6へ
ht.put(34, 18); // バケット1へ
ht.put(24, 8);  // バケット2へ

ht.display();
// 0:
// 1: { 34: 18 }
// 2: { 24: 8 }
// ...

// 衝突の発生：21 % 11 = 10 なので、バケット10に連結される
ht.put(21, 5);
ht.display();
// 10: { 10: 94 } --> { 21: 5 }

// 取得
console.log(ht.get(17)); // { key: 17, value: 76 }
console.log(ht.get(99)); // undefined

// 削除
console.log(ht.remove(34)); // true
console.log(ht.remove(99)); // false

まとめ

この記事では、チェイン法による衝突処理を備えたHashTableクラスをJavaScriptで実装しました。ハッシュ関数・バケット・チェインといったハッシュテーブルの基本要素がひととおり含まれているため、データ構造の学習教材としても最適です。実際の開発では標準のMapを使うのが一般的ですが、その裏側で何が起こっているのかを理解する良い題材になるでしょう。