本文主要是介绍1078 Hashing (25 分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Hashing
其中平方探测的k通常小于等于m/2
版本1
//1.判断给定的table size是否为素数，不是的话寻找大于该数最小的素数作为替代
//2.平方探测
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int H[maxn]={0};
bool isPrime(int x){if(x<=1) return false;int sqr = sqrt(x);for(int i=2;i<=sqr;i++){if(x%i==0) return false;}return true;
}
int main(){int m,n,x;cin>>m>>n;while(isPrime(m)==false) m++;while(n--){cin>>x;bool flag = false;for(int k=0;k<m;k++){int now = (x+k*k)%m;if(H[now] == 0){cout<<now;H[now]=1;flag=true;break;}}if(flag==false) cout<<"-";if(n) cout<<" ";else cout<<endl;}return 0;
}
版本2
#include<bits/stdc++.h>
using namespace std;
bool isPrime(int x){if(x <= 1) return false;if(x == 2) return true;int sqr = sqrt(x);for(int i = 2; i <= sqr; i++){ //不要从0开始 if(x % i == 0) return false;}return true;
}
const int maxn = 1e4+5;
bool st[maxn]={false};
int main(){int M, N, x;cin >> M >>N;while(!isPrime(M)) M++;for(int i = 0; i < N; i++){cin >> x;int j;if(i) cout<<" ";for(j = 0; j < N; j++){if(!st[(x + j*j)%M]){st[(x + j*j)%M] = true;cout<<(x + j*j)%M;break; }}if(j == N) cout<<"-";} return 0;
}
这篇关于1078 Hashing (25 分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
