資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法學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]，則輸出為 3，因為第一個元素將被插入到 0，第二個元素被插入到 1，第三個元素被插入到 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
更新於：2022-03-30
344 閱讀
廣告