解法:
线性探测是一种解决哈希冲突的方法,当发生哈希冲突时,它会依次往后查找空的槽位,直到找到一个空的槽位或者达到数组的末尾。
下面是处理哈希冲突的线性探测的步骤:
- 创建一个哈希表,里面包含一定数量的槽位。
- 当需要插入一个新的元素时,计算它的哈希值,得到一个位置,如果该位置为空,则直接将元素插入到该位置。
- 如果计算得到的位置已经被占用,发生了哈希冲突,那么就从当前位置开始往后查找,直到找到一个空的槽位或者达到数组的末尾。
- 将元素插入到找到的空的槽位中。
- 当需要查找一个元素时,首先计算它的哈希值,得到一个位置,如果该位置处的元素与要查找的元素相等,则返回该元素。
- 如果计算得到的位置处的元素与要查找的元素不相等,那么就从该位置开始往后查找,直到找到要查找的元素或者找到一个空的槽位或者达到数组的末尾。
- 如果找到要查找的元素,则返回该元素,否则表示没有找到。
需要注意的是,线性探测可能会导致哈希表的填装因子过高,从而影响性能。因此,当哈希表中的槽位被占用的比例达到一个阈值时,可以考虑进行扩容,重新哈希所有的元素,以保持哈希表的性能。
用-1初始化表明该位置为空。
#include<iostream>
#include<vector>
using namespace std;
void find(vector<int>& a) {
int x;
cin >> x;
int pos = x % a.size();
int cnt = 0;
for (int i = pos; i < a.size(); i++) {
cnt++;
if (x == a[i]) {
cout << pos << "," << cnt;
return;
}
}
cout << -1;
}
int main() {
int m, n, a;
cin >> m >> n;
vector<int> vec(m,-1);
for (int i = 0; i < n; i++) {
cin >> a;
int pos = a % m;
if (vec[pos] == -1) vec[pos] = a;
else {
int sta = pos + 1;
while (vec[sta] != -1&&sta<m) {
sta++;
}
vec[sta] = a;
}
}
find(vec);
return 0;
}