Hash 表

Hash 表又称散列表，哈希表，其核心思想为映射。通常用一个整数来表示某种复杂信息。

字符串 Hash

下面介绍的方法可以将一个任意长度的字符串映射为一个非负整数：

取两个固定值 \(P\) 和 \(M\)，把字符串看作 \(P\) 进制数（每一位的值为 char 类型自动转换值即可），将其转化为十进制后对 \(M\) 取模，就可以得到一个非负整数。当 \(M\) 足够大时，哈希冲突概率基本为零。

下面是字符串哈希的代码实现：

洛谷 P3370 【模板】字符串哈希

参考代码：

#include <bits/stdc++.h>
using namespace std;

unsigned get_hash(string& s) {
    unsigned ret = 0;
    for (char& c : s) {
        ret = ((ret * 0x66ccff) + c); 
        // 取 P = 0x66ccff, M = unsigned int 最大值
    }
    return ret;
}

unsigned a[10005], n, ans;

signed main() {
    ios::sync_with_stdio(0);
    #ifndef ONLINE_JUDGE
    clock_t t0 = clock();
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
    #endif

    // Don't stop. Don't hide. Follow the light, and you'll find tomorrow. 

    cin >> n;
    for (int i = 1;i <= n;i++) {
        string s;
        cin >> s;
        a[i] = get_hash(s);
    }

    sort(a + 1, a + 1 + n);
    for (int i = 1;i <= n;i++) {
        if (i == 1 || a[i] != a[i - 1]) ans++;
    } // 判断有多少不同的 hash 值
    cout << ans << endl;

    #ifndef ONLINE_JUDGE
    cerr << "Time used:" << clock() - t0 << "ms" << endl;
    #endif
    return 0;
}