题目描述

将一个由若干个不同正整数构成的整数序列插入到一个哈希表中，然后输出输入数字的位置。

哈希函数定义为 H(key)=key%TSize，其中 TSize 是哈希表的最大大小。

利用只具有正增量的二次探测法来解决冲突。

注意，哈希表的大小最好是素数，如果用户给出的最大大小不是素数，则必须将表大小重新定义为大于用户给出的大小的最小素数。

输出格式

在一行中，输出每个输入数字的相应位置（索引从 0 开始），数字之间用空格隔开，行尾不得有多余空格。

如果无法插入某个数字，则输出 -。

样例

输入样例：
4 4
10 6 4 15
输出样例：
0 1 4 -

算法1

题⽬⼤意：给出散列表⻓和要插⼊的元素，将这些元素按照读⼊的顺序插⼊散列表中，其中散列函数
为h(key) = key % TSize，解决冲突采⽤只向正向增加的⼆次⽅探查法。如果题中给出的TSize不是素
数，就取第⼀个⽐TSize⼤的素数作为TSize
分析：先解决size是否为素数，不是素数就要重新赋值的问题
然后根据⼆次⽅探查法：
– 如果hashTable⾥⾯key % size的下标对应的hashTable为false,说明这个下标没有被使⽤过，直接输
出。否则step步⻓从1加到size-1，⼀次次尝试是否能使index = (key + step * step) % size;所对应的位置
没有元素，如果都没有找到就输出“-”，否则就输出这个找到的元素的位置～ – 注意 是(key + step *
step) % size ⽽不是(key % size + step * step)

C++ 代码

# include<bits/stdc++.h>
using namespace std;
const int MAXSize=(int)(1e5);//题目表长最大为10的4次方，可以建立一个10的5次方以内的素数表
//埃氏筛法建立素数表
bool prime[MAXSize];
void findPrime(){
    prime[0]=prime[1]=true;
    for(int i=2;i<MAXSize;++i)
        if(!prime[i])
            for(int j=i+i;j<MAXSize;j+=i)
                prime[j]=true;
}
int main(){
    findPrime();//建立素数表
    int N,M,a;
    scanf("%d%d",&M,&N);
    while(prime[M])
        ++M;
    int table[M]={0};//哈希表
    for(int j=0;j<N;++j){
        scanf("%d",&a);
        int k=a%M;
        for(int i=1;i<=M&&table[k]!=0;k=(a+i*i)%M,++i);//查找元素能够插入的位置
        if(table[k]==0){//该元素能插入
            table[k]=a;
            printf("%s%d",j>0?" ":"",k);
        }else//该元素不能插入
            printf("%s-",j>0?" ":"");
    }
    return 0;
}