1.模拟散列表

开放寻址法

「解题思路：」用2 ~ 3倍的空间来存储，这样一般不会发生溢出问题。

#include <bits/stdc++.h>
using namespace std;
const int N = 200003,null = 0x3f3f3f3f;
int h[N];


// find 函数：如果是 x在h中不存在，则返回其该插入的位置
// 如果存在，则返回其所在的位置
int find(int x)
{
    int k = (x % N + N) % N;
    while(h[k] != null and h[k] != x)
    {
    
        k++;
        if(k == N)
        {
            k = 0;    
        }
        
    }
    return k;
}

int main()
{
    memset(h,0x3f,sizeof h);

    int n;cin >> n;
    for(int i = 0; i < n;i++)
    {
        
        string s1;
        int num;
        cin >> s1 >> num;
        int flag_num = find(num);
        if(s1 == "I")
        {
            h[flag_num]  = num;
        } else if(s1 == "Q") {
            
            if(h[flag_num] != null)
            {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        }
    }
    return 0;
}

拉链法

#include <bits/stdc++.h>
using namespace std;
const int N = 100003; // 取的 N  为第一个大于 范围的第一个质数
int e[N], h[N], ne[N], idx;

void insert(int x)
{
    int k = (x % N + N) % N; // 加 N 是为了 防止c++中取余出现负数
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

bool query_num(int x)
{
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i])
    {
        if (e[i] == x)
        {
            return true;
        }
    }

    return false;
}
int main()

{

    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    memset(h, -1, sizeof h); // 将 h 全部置为 -1

    for (int i = 1; i <= n; i++)
    {
        string s1;

        int num;
        cin >> s1 >> num;
        if (s1 == "I")
        {
            insert(num);
        }
        else if (s1 == "Q")
        {
            
            if (query_num(num))
            {
                cout << "Yes" << endl;
            }
            else
            {
                cout << "No" << endl;
            }
        }
    }

    return 0;
}

2.哈希字符串

给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式
第一行包含整数 n 和 m ，表示字符串长度和询问次数。

第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。

接下来 m 行，每行包含四个整数 l1,r1,l2,r2 ，表示一次询问所涉及的两个区间。

注意，字符串的位置从 1 开始编号。

输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

每个结果占一行。

数据范围
1≤n,m≤105
输入样例：

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输出样例：

1
2
3

Yes
No
Yes

「解题思路：」

让总字符串每一个字符变为 p 进制的一个数， p 可以为 131 或者 13331（别问为什么，经验！！）
例如字符串 USUISABCDEFABCJK ，从A开始依次到K，每一位都与前面数字化的哈希值进行累计前缀和（类似）
公式：h[i] = h[i - 1] * p + str[i] ， str[i] 为该位的 ascii 码值，只要不为 0就行。
然后题目要求判读两个区间进行对比，[l1,r1] 与 [l2,r2]，那么以 l1，r1为例，怎么求这个区间的哈希值呢？
我们通过前缀和方法知道了 1—-r1的前缀和，还知道了 1—–l1的前缀和，并且 1到r1的长度一定大于 1到l1，那么我们令1—–r1的哈希前缀和减去 1—–l1的哈希前缀和就可以得到 l1—-r1的哈希值，但是前提要求他们长度相同才能相减，这个怎么理解呢？
例如： USUISABCDEFABCJK 得到加粗部分ABC，是不是得 USUISABC 减去 USUIS，但是他们长度不同，不能直接比较，那么可以人为补足，怎么补足呢？
因为我们把字符串转换为了p进制的数对待，可以想想空缺部分变为0，例如121减去120，是不是得到了1，那么USUIS 变为 USUIS000（类比，把字母想想成数），是不是就得到了 ABC 。
想要补足空缺部分只要令 USUIS 乘以他缺的几位的进制的次方就行，那么他缺几位进制次方呢？答案是 r1 - （l1 - 1）位进制。也就是 p 的r1 - l1 + 1次方。
公式：h[r] - h[l - 1] * p[r - l + 1],p数组里已经提前处理好了进制的次方。
那么通过公式就可以轻松获取每段的哈希值，进行对比，甚至可以替代kmp算法。
注意：有些宝子肯定好奇 P[i] = P[i - 1] * p; 为啥p[1] 等于 1* p，可以这么这么想，一共10个数，我就要最后一个数的哈希值，公式肯定为 h[10] - h[9] * p^1 （1次方）。9位数与10位数对齐肯定要补一位，即p[1]等于 1 * p。

「完整代码：」

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N = 100010, p = 131; // 13331

int n, m;
char str[N];
ULL h[N], P[N];
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * P[r - l + 1];
}
int main()
{
    cin >> n >> m >> str + 1;
    P[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        P[i] = P[i - 1] * p;  
        h[i] = h[i - 1] * p + str[i];
        
    }

    while (m--)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if(get(l1,r1) == get(l2,r2))
        {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}