Mã C ++ để tìm chỉ mục nơi đây là xung đột băm

Giả sử chúng ta có một số p và một mảng X khác với n phần tử. Có một bảng băm với p xô. Các nhóm được đánh số từ 0 đến p-1. Chúng ta muốn chèn n số từ X. Chúng ta đang giả sử đối với X [i], nhóm của nó sẽ được chọn bởi hàm băm h (X [i]), trong đó h (k) =k mod p. Một thùng không thể chứa nhiều hơn một phần tử. Nếu chúng tôi muốn chèn một số vào một thùng đã được lấp đầy, chúng tôi nói rằng một "va chạm" sẽ xảy ra. Chúng tôi phải trả lại chỉ mục nơi va chạm đã xảy ra. Nếu không có va chạm, trả về -1.

Vì vậy, nếu đầu vào giống như p =10; X =[0, 21, 53, 41, 53], thì đầu ra sẽ là 3, vì đầu tiên sẽ được chèn vào 0, thứ hai ở 1, thứ ba ở 3, nhưng đầu ra thứ 4 sẽ cố gắng chèn vào 1 nhưng có xung đột, chỉ số ở đây là 3.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

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

Đầu ra

3