二次方探测解决冲突
一开始理解错了，难怪一直WA。
先寻找key%TSize的index处，如果冲突，那么依此寻找
(key+j*j)%TSize的位置，j=1~TSize-1
如果都没有空位，则输出'-'
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <cmath>
using namespace std;
const int maxn=; //之前设置的是10005，然后比10000大的第一个素数是10007
int isprime[maxn];
int prime[maxn];
int cnt=;
int hashing[maxn]; //hash表
/*
素数筛选法，筛选出素数，在存储
然后用二分查找，用来查找比MSize大的最小的素数
*/
void init(){
for(int i=;i<maxn;i++)
isprime[i]=;
isprime[]=;
for(int i=;i<maxn;i++){
if(isprime[i]){
for(int j=i*;j<maxn;j+=i)
isprime[j]=;
}
}
for(int i=;i<maxn;i++){
if(isprime[i]){
prime[cnt++]=i;
//printf("%d\n",i);
}
}
} /*
从素数中找出比给定的MSize大的最小素数
*/
int binarySearch(int val){
int l=,r=cnt-,mid;
while(l<r-){
mid=(l+r)>>;
if(val<=prime[mid])
r=mid;
else
l=mid;
}
return prime[r];
}
int main()
{
int m,n,TSize;
init();
scanf("%d %d",&m,&n);
if(m==)
m=; //如果m=1，则二分查找出来的是3，所以先要处理下
if(!isprime[m]){
TSize=binarySearch(m);
}
else
TSize=m; //printf("%d\n",TSize);
int a[maxn];
memset(hashing,,sizeof(hashing));
int pos,key;
for(int i=;i<n;i++){
scanf("%d",&key);
pos=-;
int idx;
for(int j=;j<TSize;j++){
idx=(key+j*j)%TSize;
if(!hashing[idx]){
hashing[idx]=;
pos=idx;
break;
}
}
if(i==){
printf("%d",pos);
}
else{
if(pos==-)
printf(" -");
else
printf(" %d",pos);
}
}
return ;
}