将较大的内容转换成较小的值或数的算法
有两种
- 进行特定办法求值
- 按照权值计算
特定方法求值
比方说，将 \(x\) (\(1\) ~ \(10^{18}\))，不是用STL的情况下，判断出现几次。
可以运用hash。
int hashs(int x) { //hash是关键词
return (x % Mod + Mod) % Mod;
}
按照权值计算
令权值为 \(p\)，给定字符串 \(s\)。
遍历每一位，转换成数值， 乘上位权，增加。
cin >> s;
for(int i = 0; i < s.size(); i++) {
a[j] = a[j] * p + int(s[i]);
}
通常使用ull
hash冲突
hash不是很稳定，有可能出现冲突，但概率很低。
#include <iostream>
#define ull unsigned long long
using namespace std;
const int p = 261, kMaxN = 10005;
ull a[kMaxN], n, cnt;
string s;
int main() {
cin >> n;
for (int j = 1; j <= n; j++) {
cin >> s;
for(int i = 0; i < s.size(); i++) {
a[j] = a[j] * p + int(s[i]); //转换
}
}
for (int i = 1; i <= n; i++) {
bool b = 0;
for (int j = i + 1; j <= n; j++) { //因为很大，开不了数组，只能O(n * n) 比较
if (a[i] == a[j]) {
b = 1;
break;
}
}
if (!b) {
cnt++;
}
}
cout << cnt;
return 0;
}