JavaScriptでハッシュテーブルを作成する方法

まず、各種メソッドを定義するためのシンプルなクラスを用意しましょう。ハッシュテーブル本体を格納するコンテナオブジェクトを作成し、テーブルの内容を出力するための display 関数も一緒に実装していきます。

なお、キーの衝突(コリジョン)が発生した場合の対処には、「チェイニング」と呼ばれる手法を採用します。チェイニングでは、同じハッシュ値を持つ複数の要素を連結リスト(配列)として同じスロットに格納できるため、衝突が起きてもデータを失うことなく管理できます。

クラスの基本構造

display 関数は、テーブル内の各エントリ(ハッシュ値)を順番に取り出し、そのスロットに関連付けられているすべてのキーと値のペアをコンソールに出力します。

また、個々のキーと値のペアを保持するために、プロトタイプ上に新しいクラス(KVPair)も定義します。

サンプルコード

class HashTable {
  constructor() {
    this.container = [];
    // コンテナに空の配列を入れておくことで、
    // 衝突が発生した場合でも
    // 追加の要素を格納できるようにしています
    for(let i = 0; i < 11; i++) {
      this.container.push([]);
    }
  }

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

  hash(key) {
    return key % 11;
  }
}

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

コードのポイント解説

1. コンストラクタでの初期化

コンストラクタ内では、this.container として空の配列を用意し、さらにその中に11個の空配列を格納しています。この「配列の中に配列」を持つ構造こそが、チェイニング方式の衝突解決を実現する土台となります。同じハッシュ値に対応する要素は、同じ内部配列にどんどん追加されていきます。

2. ハッシュ関数

hash(key) メソッドは、受け取ったキーを11で割った余りを返すシンプルなものです。これにより、任意のキーが0〜10の範囲のインデックスにマッピングされ、対応するスロットへ振り分けられます。

3. 分割代入の活用

display メソッドでは、分割代入(destructuring)といったモダンなJavaScriptの機能を使用しています。.map(({ key, value }) => ...) のように書くことで、オブジェクトからプロパティを一つずつ取り出すための定型コード(ボイラープレート)を書く手間が省け、コードが簡潔で読みやすくなります。

このように、コンテナ・ハッシュ関数・表示用メソッド・ペア保存用クラスの4つの要素を組み合わせるだけで、JavaScriptでも基本的なハッシュテーブルを簡単に自作できます。次のステップとしては、put(要素の追加)や get(要素の取得)、remove(要素の削除)といった操作メソッドをこのクラスに追加していくとよいでしょう。