AcWing 1564：哈希 ← 只具有正增量的二次探测法

【题目来源】
https://www.acwing.com/problem/content/1566/

【题目描述】
将一个由若干个不同正整数构成的整数序列插入到一个哈希表中，然后输出输入数字的位置。
哈希函数定义为 H(key)=key%TSize，其中 TSize 是哈希表的最大大小。
利用只具有正增量的二次探测法来解决冲突。
注意，哈希表的大小最好是素数，如果用户给出的最大大小不是素数，则必须将表大小重新定义为大于用户给出的大小的最小素数。

【输入格式】
第一行包含两个整数 MSize 和 N，分别表示用户定义的表的大小以及输入数字的数量。
第二行包含 N 个不同的正整数，数字之间用空格隔开。

【输出格式】
在一行中，输出每个输入数字的相应位置（索引从 0 开始），数字之间用空格隔开，行尾不得有多余空格。
如果无法插入某个数字，则输出 -。

【数据范围】
1≤MSize≤10^4,
1≤N≤MSize,
输入数字均在 [1,10^5] 范围内。

【输入样例】
4 4
10 6 4 15

【输出样例】
0 1 4 -

【算法分析】
本算法涉及多个细节，分述如下：
** 散列表（哈希表）
散列表，即哈希表，是根据给定关键字（Key）来计算出该关键字在表中存储地址的数据结构。也就是说，散列表建立了关键字与存储地址之间的一种直接映射关系。将关键字映射到表中记录的地址，这加快了查找速度。
模拟实现散列表的代码，详见：https://blog.csdn.net/hnjzsyjyj/article/details/132179868

** 二次探测法
本题陈述表示采用“只具有正增量的二次探测法”解决冲突。
所谓“只具有正增量的二次探测法”，即 p=(H(key)+di*di) mod m 。其中：
m 为哈希表长度；
di 为增量序列 1^2，2^2，3^2，…，k^2（k≤m-1）；
H(key) 为哈希函数，常采用“除留余数法”构造，即 H(key)=key%p 。除留余数法，方便编程实现。一般情况下，常选 p 为小于哈希表长度 m 的最大质数。
求小于给定数的最大素数代码，参见：https://blog.csdn.net/hnjzsyjyj/article/details/127699346

** 大于给定数的最小素数
由于本题有段陈述“哈希表的大小最好是素数，如果用户给出的最大大小不是素数，则必须将表大小重新定义为大于用户给出的大小的最小素数”，所以需要判断给定的数 MSize 是否为素数，若不是，则需要求大于给定的数 MSize 的最小素数。
求大于给定数的最小素数的代码详见：
https://blog.csdn.net/hnjzsyjyj/article/details/132182788

#include <bits/stdc++.h>
using namespace std;bool isPrime(int n) {if(n==1) return false;for(int i=2; i<=sqrt(n); i++) {if(n%i==0) return false;}return true;
}int getPrime(int n) { //Get least prime bigger than nfor(int i=n+1; ;i++) {if(isPrime(i)) {return i;break;}}
}int main(){int n;cin>>n;cout<<getPrime(n)<<endl;return 0;
}/*
in:100
out:101in:1000
out:1009
*/

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int maxn=1e4+5;
int h[maxn];
int msize,n;bool isPrime(int x) {if(x==1) return false;for(int i=2; i<=sqrt(x); i++) {if(x%i==0) return false;}return true;
}int getPrime(int x) { //Get least prime bigger than nfor(int i=x+1; ; i++) {if(isPrime(i)) {return i;break;}}
}int find(int x) {int t=x%msize;for(int k=0; k<msize; k++) { //二次探测法int p=(t+k*k)%msize;if(!h[p]) return p;}return -1;
}int main() {scanf("%d %d",&msize,&n);if(!isPrime(msize)) msize=getPrime(msize);for(int i=0; i<n; i++) {int x;scanf("%d",&x);int t=find(x);if(t==-1) printf("-");else {h[t]=x;printf("%d",t);}if(i!=n-1) printf(" ");}return 0;
}/*
in:
4 4
10 6 4 15out:
0 1 4 -
*/

【参考文献】
https://blog.csdn.net/qq_43733499/article/details/120093683
https://www.acwing.com/solution/content/55930/