哈希表又称散列表，一种以「key-value」形式存储数据的数据结构。所谓以「key-value」形式存储数据，是指任意的键值 key 都唯一对应到内存中的某个位置。只需要输入查找的键值，就可以快速地找到其对应的 value。可以把哈希表理解为一种高级的数组，这种数组的下标可以是很大的整数，浮点数，字符串甚至结构体。 —— 来自 OI Wiki
要让键值对应到内存中的位置，就要为键值计算索引，也就是计算这个数据应该放到哪里。这个根据键值计算索引的函数就叫做哈希函数，也称散列函数。 —— 来自 OI Wiki
以整数为例。假如我们有范围为 $[0,10^9]$ 的整数，并且需要统计其中不同的自然数个数，那我们就需要开 $10^9$ 大小的数组，空间消耗太大。但是如果我们对数字进行取模，那么就可以将数字大小控制在 $[0,\text{mod})$ 内，此时若两个数取模值相同，则认为它们相等。现在只需要开 $\text{mod }$大小的数组就够了。需要注意的是，为了保证数字均匀分布，通常使用质数作为模数。
#include <bits/stdc++.h>
#define mod 233333
using namespace std;
int n, x, ans = 0, a[mod + 2];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x;
x %= mod;
if (!a[x]) {
a[x] = 1;
ans++;
}
}
cout << ans;
return 0;
}
当然，可能会出现两个数取模结果相同但是本身值不同的情况，这就冲突了。至于冲突的处理方法，下文会介绍。
如何判断两个字符串是否相同呢？如果逐字符比对，当有大量字符串时效率必然很慢。但我们可以利用 ASCII 码，将字符串的每个字符都映射为一个数字。
例如，字符串 abAB01 可以映射为 $[97,98,65,66,48,49]$，将这个序列映射为 $[0,\text{mod}-1]$ 中的一个值，这个值就叫做字符串的哈希值。
ASCII 字符集总共有 $128$ 个字符，对应数字 $[0,127]$，不妨类比二进制的思想，将每个字符看作 $128$ 进制的数，就可以计算字符串的哈希值：
$$ \text{hash}=s[0]\times127^0+s[1]\times127^1+\dots+s[n-1]\times127^{n-1} $$
然后取一个大数进行取模，就完成了哈希操作。
不过，题目里的字符串一般是有范围的，比如只有小写字母，只有数字等，这就可以根据需求取进制，比如只有小写字母，取 $26$ 进制即可。