数据结构
网络
关系型数据库管理系统
操作系统
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 阅读
广告