注意,哈希表的大小最好是素数,如果用户给出的最大大小不是素数,则必须将表大小重新定义为大于用户给出的大小的最小素数。
最后一行输出 M 次查找的平均查找时间,保留一位小数。
注意: 如果查找了 TSize 次,每次查找的位置上均有数,但都不等于要查找的数,则认为查找时间是 TSize+1。
思路
模拟;平方探测法:pos=(x+j*j)%tsz,j∈[0,tsz)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int mp[N];
bool is_prime(int n) {
if (n<=1) return false;
for (int i=2; i<=n/i; i++) if (n%i==0)
return false;
return true;
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int msz,n,m; cin>>msz>>n>>m;
int tsz=msz; while (!is_prime(tsz)) tsz++;
for (int i=0; i<n; i++) {
int x,inserted=0; cin>>x;
for (int j=0; j<tsz; j++) {
int hash=(x+j*j)%tsz;
if (mp[hash]==0) {
mp[hash]=x, inserted=1;
break;
}
}
if (!inserted) printf("%d cannot be inserted.
", x);
}
int stime=0;
for (int i=0; i<m; i++) {
int x,cnt=0; cin>>x;
for (int j=0; j<=tsz; j++) { //不清楚为什么,将≤改为<,再解开注释后写法是错的
int hash=(x+j*j)%tsz;
cnt++;
if (mp[hash]==0 || mp[hash]==x) break;
}
// if (cnt==tsz) cnt=tsz+1;
stime+=cnt;
}
printf("%.1f", (double) stime*1.0/m);
return 0;
}