ハッシュ衝突が発生したインデックスを見つけるC++コードの解説

数値 p と、n 個の要素を持つ配列 X があるとします。ここで、バケット（格納領域）を p 個持つハッシュテーブルを考えます。各バケットには 0 から p-1 までの番号が振られており、配列 X の n 個の数値を順番に挿入していきます。

X[i] の挿入先はハッシュ関数 h(X[i]) によって決まります。ここでは h(k) = k mod p と定義されています。なお、1 つのバケットに格納できる要素は最大 1 つです。すでに要素が入っているバケットに新しい数値を挿入しようとした場合、「衝突（コリジョン）」が発生したとみなします。

求められるのは、衝突が発生した際の挿入元のインデックスを返すことです。最後まで衝突が一度も発生しなかった場合は -1 を返します。

動作例

例として、p = 10、X = [0, 21, 53, 41, 53] という入力を考えてみましょう。この場合の出力は 3 になります。

• 1 番目の要素 0 → バケット 0 へ挿入（0 mod 10 = 0）
• 2 番目の要素 21 → バケット 1 へ挿入（21 mod 10 = 1）
• 3 番目の要素 53 → バケット 3 へ挿入（53 mod 10 = 3）
• 4 番目の要素 41 → バケット 1 へ挿入しようとするが、すでに 21 が存在するため衝突が発生

衝突が起きたのは 4 番目の処理、すなわちインデックス 3 の時点なので、答えは 3 となります。

解決のための手順

この問題は、以下の手順で解くことができます。

n := X のサイズ
サイズ p・すべて 0 で初期化した配列 arr を用意
i := 0 から開始し、i < n の間、i を 1 ずつ増やしながら繰り返す:
    x := X[i]
    もし arr[x mod p] が 0 以外ならば:
        i を返す
    arr[x mod p] の値を 1 増やす
-1 を返す

各要素について、対応するバケットがすでに使用済みかどうかを確認するだけなので、非常にシンプルな線形探索で処理できます。計算量は時間 O(n)、空間 O(p) であり、効率的なアルゴリズムです。

C++ 実装例

理解を深めるために、実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(int p, vector<int> X){
    int n = X.size();
    int arr[p] = { 0 };
    for (int i = 0; i < n; i++){
        int x = X[i];
        if (arr[x % p]){
            return i;
        }
        arr[x % p]++;
    }
    return -1;
}
int main(){
    int p = 10;
    vector<int> X = { 0, 21, 53, 41, 53 };
    cout << solve(p, X) << endl;
}

入力

10, { 0, 21, 53, 41, 53 }

出力

3

まとめ

このコードでは、バケットの使用状況を記録する配列 arr を用意し、各要素のハッシュ値に対応する位置がすでに埋まっているかどうかを順にチェックしています。埋まっていた時点でそのインデックスを即座に返すことで、最初に衝突が発生した位置を効率よく特定できます。ハッシュテーブルの基本的な仕組みと衝突検出の考え方を学ぶのに、とても良い例題といえるでしょう。