これがハッシュ衝突であるインデックスを見つけるためのC++コード

数pとn個の要素を持つ別の配列Xがあるとします。 p個のバケットを持つハッシュテーブルがあります。バケットには0からp-1までの番号が付けられています。 Xからn個の数値を挿入します。X[i]の場合、そのバケットはハッシュ関数h（X [i]）によって選択されると想定しています。ここで、h（k）=kmodpです。 1つのバケットに複数の要素を保持することはできません。すでにいっぱいになっているバケツに数字を挿入したい場合、「衝突」が発生すると言います。衝突が発生したインデックスを返す必要があります。衝突がない場合は、-1を返します。

したがって、入力がp=10のような場合。 X =[0、21、53、41、53]の場合、出力は3になります。これは、最初の1つが0に挿入され、2番目が1に挿入され、3番目が3に挿入されるためですが、4番目は1に挿入しようとしますが衝突があり、ここではインデックスは3です。

ステップ

これを解決するには、次の手順に従います-

n := size of X
Define an array arr of size: p and fill with 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   x := X[i]
   if arr[x mod p] is non-zero, then:
      return i
   increase arr[x mod p] by 1
return -1

例

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

#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