个人练习-PAT甲级-1078 Hashing

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805389634158592

哈希表，复习了一下平方探测法。
发生collision时，按照单元$h_0(X),h_1(X),h_2(X),...$相继试选，$h_{cnt}(X)=(Hash(X)+F(cnt))\%TableSize$
它的下标cnt为发生collision的次数，初始为0。平方探测法中，解决函数$F(cnt)=cn{t}^2$
由这个平方解决函数可知，$F(i)=F(i?1)+2i?1$

题目要求TableSize为所给的大于等于MSize的最小素数，这说明有可能需要填装数N有可能大于TableSize的一半，这时平方探测法无法保证每一个元素都能插入，如果找不到插入位置，要输出-

我们用一个known[]数组表示某个位置是否被探测过了，如果一个位置被探测了两次，说明无法找到插入位置，要跳出循环了。

int myHash(vector<int>& table, int val){
    int pos = val % table.size();int cnt = 0;while(table[pos] != -1){
    cnt++;pos += 2*cnt - 1;pos %= table.size();}table[pos] = val;return pos;
}

完整代码

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<map>
#include<set>
#include<queue>
#include<string.h>using namespace std;bool isPrime(int x){
       if (x == 2 || x == 3)return true;else if (x <= 1)return false;else if (x % 2 == 0)return false;else{
    for (int i = 4; i < sqrt(x); i++){
    if (x % i == 0)return fasle;}}return true;
}int myHash(vector<int>& table, int val){
    int pos = val % table.size();int cnt = 0;while(table[pos] != -1){
    cnt++;pos += 2*cnt - 1;pos %= table.size();}table[pos] = val;return pos;
}int main() {
    int M, N;scanf("%d %d", &M, &N);while (!isPrime(M))M++;vector<int> arr(N);vector<int> pos(N, -1);vector<int> table(M, -1);for (int i = 0; i < N; i++){
    scanf("%d", &arr[i]);pos[i] = myHash(table, arr[i]);}for (int i = 0; i < N; i++){
    if (i > 0)printf(" ");else;if (pos[i] >= 0)printf("%d", pos[i]);elseprintf("-");}return 0;
}