PTA甲级—常用技巧与算法
散列
1078 Hashing (25 分)
Quadratic probing (with positive increments only) is used to solve the collisions.
这句话说的是使用平方探测法来解决哈希冲突，Linear Probing（线性探测法）、Quadratic probing（平方探测法）这种专业术语在平常的学习中应当认真记忆而不是认为不重要，因为这句话一开始看不懂，想当然认不重要就略过了，那结果多半WA。
知道了解决办法之后，需要处理的一个问题就是我们如何知道插入失败？
假设$x<y$，由$h(k) + x^2 = h(k) + y^2 \quad (mod \ p)$得：
$$ x^2 = y^2 \quad(mod \ p)$$
$$ (x-y)(x+y) = 0 \quad(mod \ p)$$
由上述式子推导可发现$p$是一个循环节，如果从$0 \sim p-1$进行枚举仍然找不到位置的话即可认为插入失败
这道题要求的是$with \ positive \ increments \ only$，去掉这个限制条件后，以增量序列$1^2, -1^2, 2^2, -2^2 \dots, x^2, -x^2$且$x<=p/2$循环试探下一个存储地址即可，证明同上可得（tips:大与2/p的部分可以由p减去小于2/p的部分得到）
还需要注意的一个点：1不是素数，需要在isPrime函数中加以判断
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <vector> #include <set> #include <map> #include <queue> #define ll long long #define inf 0x3f3f3f3f #define pb push_back #define pii pair<int,int> using namespace std; const int maxn = 1e6+100; int p, n, tmp; bool vis[maxn]; bool isPrime(int x){ if(x==1) return false; for(int i = 2; i*i <= x; i++) if(x%i==0) return false; return true; } int main(){ scanf("%d%d", &p, &n); while(!isPrime(p)) p++; while(n--){ scanf("%d", &tmp); int x = tmp%p, y = x, inc = -1; while(inc<p&&vis[y]) inc++, y = (x+inc*inc)%p; if(inc!=p) printf("%d", y), vis[y] = 1; else printf("-"); if(n) printf(" "); } }
View Code
补充资料：
线性探测是按线性方法一个一个找，只要表里有空位总能将元素填入；而二次探测有可能出现表中有空间但平方探测找不到的情况
线性探测容易聚集，二次探测聚集情况较线性探测要好。
二次探测有时候探测不到整个散列表空间，是其一大缺陷。但是经过数学家的研究，散列表长度TableSize是某个4k＋3（k是正整数）形式的素数时，平方探测法就可以探查到整个散列表空间.
Reference:
https://www.icourse163.org/learn/ZJU-93001?tid=1003997005#/learn/content?type=detail&id=1007588520
https://www.nowcoder.com/discuss/67780
https://en.wikipedia.org/wiki/Quadratic_probing
https://blog.csdn.net/qq_37142034/article/details/87903983
https://blog.csdn.net/pennyliang/article/details/5446961
1145 Hashing – Average Search Time (25 分)
这道题相当于1078的扩展，关键在于如何求不在散列表中的元素的平均查找次数。边界值显然为p+1，当查找到已经查找过的单元格后就知道查找失败了；在这个过程中如果发现有空位也能说明该元素不在单元格中
#include <cstdio> using namespace std; const int maxn = 1e6+100; int p, n, m, tmp, h[maxn]; bool vis[maxn]; bool isPrime(int x){ if(x==1) return false; for(int i = 2; i*i <= x; i++) if(x%i==0) return false; return true; } int main(){ scanf("%d%d%d", &p, &n, &m); while(!isPrime(p)) p++; while(n--){ scanf("%d", &tmp); int x = tmp%p, y = x, inc = 0; while(vis[y]&&++inc<p) y = (x+inc*inc)%p; if(inc!=p) h[y] = tmp, vis[y] = 1; else printf("%d cannot be inserted.\n", tmp); } int cnt = m, sum = 0; while(m--){ scanf("%d", &tmp); int x = tmp%p, y = x, inc = 0; while(h[y]!=tmp&&vis[y]&&++inc<p) y = (x+inc*inc)%p; sum += inc+1; } printf("%.1f", 1.0*sum/cnt); }
View Code