洛谷题单指南-集合-P3370 【模板】字符串哈希

原题链接：https://www.luogu.com.cn/problem/P3370

题意解读：本题要求理解哈希的原理，自行建立哈希表解题，如果直接使用map，就不推荐。

解题思路：

先介绍哈希的原理

1、什么是哈希？什么是哈希表？

先从一个问题出发：给定不超过10⁵个整数（取值1~10⁹）,要统计不重复整数的数量。

首先，如果取值范围是1~10⁵，可以借助计数排序的思想，定义数组int a[N]，N在1e5规模，遍历所有整数，对出现的整数标记a[i] = 1，最后统计>0的个数；

但是，由于取值范围是1~10⁹，如果定义数组int a[N]，N在1e9规模，内存会爆掉，能不能用更小的数据结构来搞定呢?

可以定义vector<int> a[M]，M在1e5规模内即可

对于每一个整数i，先计算i % M，取模之后必然落到[0~M)区间，然后将i存入a[i % M].push_back(i)

在存入i之前，可以判断a[i % M]这个vector里是否已经存在了i，存在则不加入

最后，遍历所有a[k]，累加a[k].size()即得不重复的整数数量。

把一个大的整数映射到一个小整数的过程叫做哈希，如i % M；

而用来存储元素的vector<int> a[M]则称为哈希表。

2、字符串如何哈希？

字符串也可以转化为整数，只需把字符串当做p进制数来处理即可

例如：ABC，转成数字：'A' * p² + 'B' * p¹ + 'C' * p⁰

再对一个合适的M取模：('A' * p2 + 'B' * p1 + 'C' * p0) % M

就完成了字符串的哈希

通常：P取一个素数会减少冲突，常见选择如：131、13331

M则根据实际数据量进行选择即可。

100分代码：

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

const int N = 10005, M = 10000, P = 131;

vector<string> h[N];
int n, ans;
string s;

int main()
{
    cin >> n;
    while(n--)
    {
        cin >> s;
        int hashcode = 0;
        for(int i = 0; i < s.size(); i++)
        {
            hashcode = (hashcode * P + s[i]) % M; //类似二进制转十进制的操作计算hashcode，每次都要%M以免溢出
        }
        bool exist = false; //s是否已经存在
        for(int i = 0; i < h[hashcode].size(); i++) //在h[hashcode]中查找s是否存在
        {
            if(h[hashcode][i] == s)
            {
                exist = true;
                break;
            } 
        }
        if(!exist)
        {
            h[hashcode].push_back(s); //如果s不存在则添加
            ans++;
        } 
    }
    cout << ans;

    return 0;
}