이것이 해시 충돌인 인덱스를 찾는 C++ 코드

<시간/>

숫자 p와 n개의 요소가 있는 또 다른 배열 X가 있다고 가정합니다. p 버킷이 있는 해시 테이블이 있습니다. 버킷은 0에서 p-1까지 번호가 지정됩니다. X에서 n개의 숫자를 삽입하려고 합니다. X[i]에 대해 버킷이 해시 함수 h(X[i])에 의해 선택된다고 가정합니다. 여기서 h(k) =k mod p입니다. 하나의 버킷은 둘 이상의 요소를 보유할 수 없습니다. 이미 채워진 버킷에 숫자를 삽입하려는 경우 "충돌"이 발생한다고 말합니다. 충돌이 발생한 인덱스를 반환해야 합니다. 충돌이 없으면 -1을 반환합니다.

따라서 입력이 p =10과 같으면; X =[0, 21, 53, 41, 53]이면 첫 번째 것은 0에, 두 번째는 1에, 세 번째는 3에 삽입되지만 네 번째는 1에 삽입을 시도하기 때문에 출력은 3이 됩니다. 충돌이 있습니다. 인덱스는 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 }