写在最前面：

此系列中的所有模板全为大佬所写，我只是一个搬运工（？）。

本次算法均为用数组模拟STL，这样的速度更快而且可操作性更强。

记录

总体概述

把一个庞大的数据映射到一个总数小于1e5的集合中去。

存储结构

一般情况直接取模。一般情况下删除也不是真正删除，而是把要求删除的元素做一个记号。

h=x%q(q尽量取质数而且离二的整数幂尽可能远)。在取模的过程中，可能存在多个点映射到一个点的情况。下面有两种解决方案。

拉链法

在同一位置的数用一条链子串成一串。如图所示。

alt

下面是模板：


#include <iostream>
#include <cstdio>
#include <cstring>
//这个N一般是操作数
const int N=1e5+3;//该数字是1e5之后第一个质数
using namespace std;
int idx=0,e[N],ne[N];
int h[N];


void insert1(int x)
{
    int k=(x%N+N)%N;//保证取模之后出来是正数
    e[idx]=x;
    ne[idx]=h[k];
    h[k]=idx++;
}
bool find1(int x)
{
    int k=(x%N+N)%N;
    for(int i=h[k];i!=-1;i=ne[i])//遍历链表
    {
        if(x==e[i]) return true;
    }
    return false;
}

int main()
{
    int n;
    scanf("%d",&n);

    memset(h,-1,sizeof(h));//把所有h都指向-1（空节点）,初始化函数

    while (n--)
    {
        char  op[2];
        int x;
        scanf("%s%d",op,&x);
        if(op[0]=='I') insert1(x);
        else
        {
            if(find1(x)) printf("Yes\n");
            else printf("No\n");
        }

    }
    return 0;
}

开放寻址法

只开一个数组，一般数组大小是题目要求的两到三倍。

如果计算模之后的数字为k，如果该处已经有数字了那么久顺序插入到下一个，即k+1处，如果该处仍然有数字，则继续往下查找。如果到最后依然没有查到而且依然不为空，则从第一个开始继续寻找空位。

下面是模板：

#include <iostream>
#include <cstring>
#include <cstdio>
const int N=2e5+3,null=0x3f3f3f3f;//0x表示十六进制
int h[N];
using namespace std;
int ffind(int x)
{
    int k=(x%N+N)%N;

    while (h[k]!=null&&h[k]!=x)
    {
        k++;
        if(k==N) k=0;//遍历到最后一个以后就从第一个开始查找
    }
    return k;//如果找到返回位置，没找到返回要插入的位置
}
int main()
{
    int n;
    scanf("%d",&n);
    memset(h,0x3f,sizeof(h));//初始化是按字节分的，int有四个字节，也就是说一共有四个3f

    while (n--)
    {
        char op[2];
        int num;
        scanf("%s%d",op,&num);
        int k=ffind(num);
        if(op[0]=='I') h[k]=num;
        else
        {
            if(h[k]!=null) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

字符串哈希方式（用来快速判断两个字符串是否相同）

举个例子：比如说这里有字符串“abcdefg”,用h[N]表示字符串的哈希值。 h[0]=“a”的哈希值。 h[1]=“ab”的哈希值。 h[2]=“abc”的哈希值。 h[3]=“abcd”的哈希值。 ……

实现方法：

1.把字符串当做p进制的数字。 例如： alt 2.把算出来的数字取模Q。映射进h[N]中。

3.求[l,r]区间子字符串的方法，如下图所示。 alt 注意：

  1. 不能映射成0。
  2. 一般来说P=131/P=13331,Q=2^64（可以用unsigned long long 表示，越出就直接取模了）。一般不会冲突。

3.除了求循环节y用kmp外，其他的一般都是用这个方法。

下面是模板：

#include <iostream>
#include <cstdio>
using namespace std;
typedef unsigned long long ULL;
const int N=1e5+10,P=131;

int n,m;
char s[N];
int h[N],p[N];//用p来存p的n次方

ULL get(int l,int r)//求区间哈希的过程(所以l要取l-1)
{
    return h[r]-h[l-1]*p[r-l+1];
}

int main()
{
    scanf("%d%d%s",&n,&m,s+1);//字符串存储要从1开始

    p[0]=1;

    for(int i=1;i<=n;i++)
    {
        p[i]=p[i-1]*P;
        h[i]=h[i-1]*P+s[i];
    }
    while(m--)
    {
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(get(l1,r1)==get(l2,r2))
            puts("Yes");
        else puts("No");
    }
    return 0;
}