b_pat_哈希-平均查找时间（新知识之-平方探测法）

注意，哈希表的大小最好是素数，如果用户给出的最大大小不是素数，则必须将表大小重新定义为大于用户给出的大小的最小素数。
最后一行输出 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.\n", 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;
}

b_pat_哈希-平均查找时间（新知识之-平方探测法）

原文：https://www.cnblogs.com/wdt1/p/13719089.html