PAT 1145 Hashing - Average Search Time

这一题的大意是给出一个哈希表的大小，如果不是质数，就把它变成和它最近的大的质数。
然后给出N个数，把这N个数插入到哈希表中，如果不能插入输出：x cannot be inserted.
然后给出M个数，判断它们在不在哈希表中，并且统计找到它们需要查询的次数的平均值。
当出现哈希冲突的时候，采用平方探测法
这一题我们只需要清楚平方探测法就好写，剩下就是模拟哈希表的过程。
平方探测法：

for(intk=0;k<msize;k++){if(hash[(x+k*k)%msize]==x){cnt++;returncnt;}elseif(hash[(x+k*k)%msize]==0){cnt++;returncnt;}else{cnt++;}}

就是加上一个k*k的平方。
最终的代码按题意模拟即可：
完整代码如下：

#include<bits/stdc++.h>#include<iostream>usingnamespacestd;intMSize;intN;intM;boolisprime(intx){if(x==0||x==1){returnfalse;}if(x==2){returntrue;}for(inti=2;i<sqrt(x)+1;i++){if(x%i==0){returnfalse;}}returntrue;}intprime(intx){if(isprime(x)){returnx;}else{//找离x最近的质数for(inti=x+1;i<=1e5;i++){if(isprime(i)){returni;}}}}intquery(intx,intmsize,inthash[]){intcnt=0;for(intk=0;k<msize;k++){if(hash[(x+k*k)%msize]==x){cnt++;returncnt;}elseif(hash[(x+k*k)%msize]==0){cnt++;returncnt;}else{cnt++;}}if(cnt==msize){returncnt+1;}if(cnt==0){return0;}}intmain(){cin>>MSize>>N>>M;intmsize=prime(MSize);//因此哈希表的大小是5inthash[msize];memset(hash,0,sizeof(hash));for(inti=0;i<N;i++){intkey;cin>>key;if(hash[key%msize]==0){hash[key%msize]=key;}else{//说明发生哈希碰撞intk=1;boolflag=0;while(hash[(key+k*k)%msize]!=0){if(k>=msize){flag=1;break;}k++;}if(flag==1){cout<<key<<" cannot be inserted."<<endl;}else{hash[(key+k*k)%msize]=key;}}}intans=0;for(inti=0;i<M;i++){intx;cin>>x;intt=query(x,msize,hash);ans+=t;}printf("%.1f\n",(double)ans/M);return0;}

注意如果查找某一个值的时候，发现在哈希表中的位置为空，说明这个值不在哈希表中，如果查询了所有可能的值，但仍然没有查到某一个元素，那么查询次数应该是哈希表大小+1.