整型关键字的平方探测法散列 (25 分)【详细解析】

立志用最少的代码做最高效的表达

---

本题的任务很简单：将给定的无重复正整数序列插入一个散列表，输出每个输入的数字在表中的位置。所用的散列函数是 H(key)=key%TSize，其中 TSize 是散列表的表长。要求用平方探测法（只增不减，即H(Key)+i^2）解决冲突。

注意散列表的表长最好是个素数。如果输入给定的表长不是素数，你必须将表长重新定义为大于给定表长的最小素数。

输入格式：
首先第一行给出两个正整数 MSize（≤10^4）和N（≤MSize），分别对应输入的表长和输入数字的个数。随后第二行给出 N 个不重复的正整数，数字间以空格分隔。

输出格式：
在一行中按照输入的顺序给出每个数字在散列表中的位置（下标从 0 开始）。如果某个数字无法插入，就在其位置上输出 -。输出间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：
4 4
10 6 4 15

输出样例：
0 1 4 -

---

Hash平方探测法模板

注意：
何种情况下某值无法插入到序列中？
答：如果序列长度为7，则循环到7*7及以后，就会形成周期循环， 因此循环次数小于序列长度即可。

举例：x=1，n=7时， $x+0\ast 0$等价于$x+7\ast 7$ ；$x+1\ast 1$等价于$x+8\ast 8）$

证明：参考取余性质，有： (x+8*8)%7=(x+(1+7)*(1+7))%7=(x+(1+7+7+49))%7=(x+1)%7+7%7+7%7+49%7=(x+1)%7

---

#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <map> using namespace std; int is(int n) {if(n == 1)return 0;if(n == 2 || n == 3)return 1;if(n % 6 != 1 && n % 6 != 5)return 0;for(int i = 5;i * i <= n;i += 6) if(n % i == 0 || n % (i + 2) == 0)return 0;return 1; } int main() {int m,n;int s,p,v[10007] = {0};scanf("%d %d",&m,&n);while(!is(m))m ++;for(int i = 0;i < n;i ++) {p = -1;scanf("%d",&s);for(int j = 0;j < m;j ++) {if(!v[(s + j * j) % m]) {v[(s + j * j) % m] = 1;p = (s + j * j) % m;break;}}if(i)putchar(' ');if(p == -1)printf("-");else printf("%d",p);} }

---

弱小和无知不是生存的障碍，傲慢才是。       ——《三体》

总结

以上是生活随笔为你收集整理的整型关键字的平方探测法散列 (25 分)【详细解析】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。