ハッシュ表の衝突（シノニム）とは？ mod演算・チェイン法・線形探索法を図解で理解する

01｜そもそもハッシュ表は何に使うのですか

ハッシュ表は、キーから値をすばやく探したい場面で使われます。例えば、会員番号から会員情報を探す、商品コードから在庫情報を探す、URLからキャッシュ済みのレスポンスを探す、といった場面です。

配列やリストを先頭から順番に探すと、件数が増えるほど時間がかかります。一方、ハッシュ表は「どこを見ればよいか」をハッシュ関数で先に絞れるため、平均的には非常に高速です。

02｜ハッシュ関数は『どこを見るか』を決めます

ハッシュ表では、キーを入力して格納先の添字を返す関数をハッシュ関数と呼びます。今回の問題で使われているのは、最も基本的なh(x) = x mod nです。

ここで、x はキー、n はハッシュ表の大きさです。mod は余りを求める演算なので、結果は 0 から n−1 の範囲に収まります。つまり、そのまま配列の添字として使いやすいです。

03｜シノニムとは何ですか

異なるキーなのに、ハッシュ関数を通すと同じ値になることがあります。このとき、そのキー同士をシノニムと呼びます。一般的には衝突（collision）という言い方もよく使います。

例えば 27 と 51 は違う数ですが、12 で割った余りはどちらも 3 です。したがって、h(x) = x mod 12では同じ bucket 3 に対応します。

04｜なぜ『差が n の倍数』だと衝突するのですか

2つのキー a、b が同じ余りを持つとき、a と b は次のように書けます。

a = pn + r
b = qn + r
-----------------
a - b = (p - q)n

右辺は n の整数倍なので、左辺である a−b も n の倍数です。逆に、a−b が n の倍数なら、a と b を n で割った余りは同じになります。したがって、次の関係が成り立ちます。

例えば a=51、b=27、n=12 なら、51−27=24 であり 12 の倍数です。したがって、この2つは衝突します。試験問題の正答が「a−b が n の倍数」になる理由はここです。

05｜合同式で見るとさらに短く書けます

数学では、余りが同じであることを合同と呼び、a ≡ b (mod n)と書きます。これは「a−b は n で割り切れる」という意味です。

3, 15, 27, 39, 51, 63, ...
→ いずれも 12 で割った余りは 3 です。

この見方に慣れておくと、ハッシュ表だけでなく暗号や数論の問題でも役立ちます。

06｜衝突したらどう保存するのですか

ハッシュ表は衝突を前提に設計します。つまり、「ぶつかったときにどう処理するか」まで含めてデータ構造です。代表的な方法として、チェイン法とオープンアドレス法があります。オープンアドレス法の中でも基本なのが線形探索法です。

07｜チェイン法は『同じ箱の中に並べる』方法です

チェイン法では、同じバケットに来た要素をリストや配列にまとめて格納します。例えば bucket 3 に 27 と 51 が来たら、bucket 3 の中に [27, 51] のように並べます。

検索するときは、まずハッシュ値で bucket 3 を求め、その中を順番に見ていきます。実装が分かりやすく、表が埋まっても追加しやすいのが利点です。

08｜線形探索法は『次の空き番地へ進む』方法です

線形探索法では、衝突したら次の番地、その次の番地、というように順番に空きを探します。例えば 27 と 51 がどちらも 3 を指しているとき、27 を 3 に入れた後で 51 を入れようとすると、3 は埋まっているので 4 を調べます。

51 mod 12 = 3
bucket 3 は使用中
→ bucket 4 を調べます
→ 空いていればそこへ格納します

配列だけで完結するため実装しやすい反面、使用済みの領域が連続すると探索回数が増えることがあります。これをクラスタリングと呼びます。

09｜検索時の流れを具体的に追ってみましょう

ハッシュ表は「一発で見つかる」ように見えますが、実際には次のような手順を踏んでいます。衝突がなければ非常に短い手順ですが、衝突があるとバケット内の比較や次の番地の確認が加わります。

10｜負荷率が高いと遅くなりやすいです

ハッシュ表の性能を考えるときは、負荷率（load factor）も重要です。これは、登録要素数 m をバケット数 n で割った値で、α = m / nと表します。

負荷率が大きいほど、同じバケットに要素が集まりやすくなります。チェイン法では1つのバケットの列が長くなり、線形探索法では空きが見つかりにくくなります。そのため、実装では一定以上になったら表を大きくして再ハッシュすることがあります。

11｜TypeScriptで基本形を確認します

まずはチェイン法によるシンプルな実装例です。同じハッシュ値になったキーは、同じバケット配列の中へ入れます。

class IntegerHashTable {
  private buckets: number[][];

  constructor(private readonly size: number) {
    this.buckets = Array.from({ length: size }, () => []);
  }

  private hash(key: number): number {
    return ((key % this.size) + this.size) % this.size;
  }

  add(key: number): void {
    const bucket = this.buckets[this.hash(key)];
    if (!bucket.includes(key)) {
      bucket.push(key);
    }
  }

  has(key: number): boolean {
    return this.buckets[this.hash(key)].includes(key);
  }
}

ここでは整数キーだけを扱っています。実際には文字列キーを数値へ変換するハッシュ関数を用意してから配列へ格納する場合も多いです。

12｜操作ラボで『ぶつかり方』を目で確認しましょう

次のラボでは、バケット数、キー、格納方式を変えながら、衝突の起こり方を確認できます。特に、同じ余りなら同じ場所へ向かうことと、チェイン法と線形探索法で保存のされ方が違うことに注目して試してみてください。

13｜まとめ

ハッシュ表は、キーから格納先をすばやく求めるためのデータ構造です。今回の問題のようにh(x) = x mod nを使う場合、a−b が n の倍数なら a と b は同じ余りを持ち、衝突します。

そのうえで、衝突時にはチェイン法なら同じ箱の中へ並べ、線形探索法なら次の空き番地へ進みます。数式だけでなく、用途と保存のイメージを合わせて理解しておくと、試験でも実務でも忘れにくくなります。