哈希(HASH)
哈希(HASH)本质上是一种映射。
引入1
给定 $n$ 个正整数,这些正整数的值域均为 $[1,10^6)$,让你把这些数去重后按从小到大排序后输出。
方法
用一个桶来统计每一个数的次数,最后循环值域,如果次数不为 $0$,就输出即可。
时间复杂度:$O(n)$,空间复杂度:$O(10^6)$。
引入2
给定 $n$ 个正整数,这些正整数的值域均为 $[1,10^9)$,让你把这些数去重后按从小到大排序后输出。
这题发现值域到了 $10^9$,很明显无法用桶排来做。
方法1
用STL-unique来写,时间复杂度大概为 $O(n)$,可以过。
不过大部分题目都无法用unique,就有了新的算法-哈希。
方法2-哈希算法
我们用一个函数 $H$,将一个很大的数 $x$ 变为一个可以用数组存下的数。
一般都将哈希函数 $H(x)$ 定义为 $x\bmod P$($P$为一个质数)。
最后将哈希之后的数做桶排即可。
哈希冲突
我们发现如果两个数 $x,y$ 使 $H(x)=H(y)$,此时发现哈希之后冲突了,答案就错误。此时就叫哈希冲突、
解决哈希冲突
我们用一个链表处理 $0\sim P-1$ 的模数情况。即,将 $x$ 插入到 $H(x)$ 的链表下。
每次插入时遍历 $H(x)$ 的链表,如果没有重复就插入,否则就不插入链表。
时间复杂度
$ O(n\cdot len) \approx O(n\cdot \dfrac{n}{P}) $
$\text{当}P\approx n\text{时,}O(n\cdot \dfrac{n}{P})\approx \Theta(n)$。
此时的时间复杂度就十分优秀了。
模板代码
#include <bits/stdc++.h>
using namespace std;
const int MOD = 999983;
int n, x, ans;
vector <int> G[MOD + 5];
int Hash (int x) {
return x % MOD;
}
int insert (int x) {
int val = Hash(x);
for (int i = 0; i < G[val].size(); ++i) {
if (G[val][i] == x) return 0;
}
G[val].push_back(x);
return 1;
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> x;
ans += insert(x);
}
cout << ans << endl;
return 0;
}
例题
这题定义哈希函数 $H(x)=x\bmod P$,如果过不了,别忘了考虑负数的情况。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
const int MOD = 999983;
int T, n, ans;
int a[N];
vector <int> G[MOD + 5];
int Hash (int x) {
return (x % MOD + MOD) % MOD;
}
int insert (int x) {
int val = Hash(x);
for (int i = 0; i < G[val].size(); ++i) {
if (G[val][i] == x) return 0;
}
G[val].push_back(x);
return 1;
}
int main() {
cin >> T;
while (T--) {
cin >> n;
ans = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
for (int i = 0; i < MOD; ++i) {
G[i].clear();
}
for (int i = 1; i <= n; ++i) {
if (insert(a[i]) == 1) {
cout << a[i] << " ";
}
}
cout << endl;
}
return 0;
}
首先先看题目,看到有 $x_i=x_j$ 时,就想到了用图论的并查集来做。即,先将所有 $e=1$ 的情况中的 $(i,j)$ 合并,最后合并完再枚举 $e=0$ 的情况看是否在同一个连通块就行了。
可发现数据范围中的
$1\leq i,j\leq 10^9$
就知道用纯的并查集过不去。于是想到了用哈希将数的范围缩小,随后并查集维护即可。哈希函数一样是 $H(x) = x\bmod P$。时间复杂度:$O(n\cdot\alpha(n))\approx O(n) $
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int MOD = 990887;
int T, n;
int x[N], y[N], opt[N];
int fa[MOD + 5];
int Hash (int x) {
return x % MOD;
}
int find (int x) {
if (x == fa[x]) return x;
else return fa[x] = find(fa[x]);
}
void unionn (int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) fa[fx] = fy;
return ;
}
int main() {
cin >> T;
while (T--) {
cin >> n;
for (int i = 0; i < MOD; ++i) {
fa[i] = i;
}
for (int i = 1; i <= n; ++i) {
cin >> x[i] >> y[i] >> opt[i];
if (opt[i] == 1) unionn(Hash(x[i]), Hash(y[i]));
}
bool flag = false;
for (int i = 1; i <= n; ++i) {
if (opt[i] == 0) {
if (find(Hash(x[i])) == find(Hash(y[i]))){
puts("NO");
flag = true;
break;
}
}
}
if (flag == false) puts("YES");
}
return 0;
}
样例输入(POJ):
2 1 2 3 4 5 6 4 3 2 1 6 5
样例输出(POJ):
Twin snowflakes found.