1078. Hashing (25)（哈希规则）

PAT-A 1078，题目地址：https://www.patest.cn/contests/pat-a-practise/1078
这道题主要是要搞清楚“平方探测”的规则以及表大小的选取，注意：

1. 2是最小的素数，所以表的大小不能为1
2. 平方探测的规则是，当num插不进哈希表时，分别对num+1^2, num+2^2 ... num+k^2位置进行尝试，其中，k是哈希表的大小

代码如下：

#include <iostream>
#include <string.h>
#define MAX 10100

bool prime[MAX];
int hash[MAX];

//建立素数表，max是随便挑的数，当然要保证10000~MAX之间必须存在至少存在一个素数。这个建立素数表的方法很常见，看不懂可以百度一下
void build_prime(){
    prime[0] = prime[1] = false;
    for(int i = 2; i <= MAX; i++){
        if(prime[i] == true){
            for(int j = i * i; j < MAX; j += i){
                prime[j] = false;
            }
        }
    }
    return ;
}

//插入一个元素k到hash表，成功则返回下标，失败返回-1
int insert(int size, int k){
    int origin = k;
    k %= size;
    int count = 1;
    while(hash[k] != -1){
        k = origin + count * count;
        count++;
        k %= size;
        if(count > size){
            return -1;
        }
    }
    hash[k] = origin;
    return k;
}

int main(){
    int m, n;
    int num;
    std::cin >> m >> n;
    memset(hash, -1, sizeof(int) * MAX);
    memset(prime, 1, sizeof(bool) * MAX);
    build_prime();
    while(!prime[m])
        m++; //找出>=m的最小素数

    for(int i = 0; i < n; i++){
        std::cin >> num;
        int res = insert(m, num);
        if(i != 0)
            std::cout << " ";
        if(res == -1)
            std::cout << "-";
        else
            std::cout << res;
    }
    std::cout << std::endl;
    return 0;
}