将较大的内容转换成较小的值或数的算法

有两种

• 进行特定办法求值
• 按照权值计算

特定方法求值

比方说，将 \(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;
}