一.存储结构

分为两大类：开放寻址法和拉链法

主要作用

把一个比较庞大的空间（值域）映射到一个比较小的空间（值域），一般情况下映射到0~n，$n$ 可能是 $10^5$ 或 $10^6$

哈希函数能把一个数在 $-10^9$~$10^9$ 中的一个数映射到$10^5$

哈希函数的写法

1.将 $x$ $mod$ $10^5$ 可以把值域为 $10^9$ 的数映射成 $1$ ~ $10^5$ 其中的一个数

可能把若干个不同的数映射到同一个数，冲突了

处理冲突的方式：开放寻址法和拉链法

一.拉链法

设 $h(11)=3$ $h(21)=3$ $11$ 和 $21$ 冲突

开一个一维数组 $h$ 为哈希结果，每一个空间看作一个槽

如果 $11$ 为 $3$ 的话，在 $3$ 的底下拉一条链，如果 $23$ 也是 $3$ ，再在 $3$ 的末尾拉一条链 $23$，存下那个数，链就是单链表

是一个期望算法，每一条链的长度可以看得非常短

删除的话开一个布尔变量，在数上打标记

二.开放寻址法

只开了一维数组，大小要开到题目数据范围的两到三倍

思路

基本思路：从坑位开始找，如果坑上有人并且不是x的话，说明不能进去，找下一个坑位对应 $k++$ ，如果 $k$ 是最后一个位置的话，那k变为0，重新找。

$0x3f3f3f3f$ 是一个大于 $10^9$ 的数

实现

#include<bits/stdc++.h>
using namespace std;
const int N=200003,null=0x3f3f3f3f;//模数必须为质数
int h[N];//静态链表
int find(int x){//插入操作
    int k=(x%N+N)%N;//k为映射哈希值，如果x%N是负数会输出负数，于是加上n
    while(h[k]!=null){//坑上有人并且不等于x
        k++;
        if(k==N)k=0;
    }
    return k;
}
int main(){
    int n;
    cin>>n;
    memset(h,0x3f,sizeof h);
    for(int i=1;i<=n;i++){
        char op[2];
        int x;
        cin>>op>>x;
        if(*op=='I'){
            int k=find(x);
            h[k]=x;
        }
        else{
            if(h[find(x)]!=null)puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

二.字符串前缀哈希法

首先预处理出来所有哈希

$h[0]$ 等于 $0$

$h[1]$ 对应第一个字符的哈希值

$h[2]$ 对应前两个字符的哈希值

$h[3]$ 对应前三个字符的哈希值

求 $abcd$ 的哈希值

1.将 $abcd$ 看成一个 $p$ 进制数，有 $4$ 位，第一位是 $a$ 第二位是 $b$……

$abcd$ 可以表示为 $P$ 进制的 $1234$

2.把 $P$ 进制数转化为十进制数（1234）

$p=$$(1*p^3)+(2*p^2)+(3*p^1)+(4*p^0)$

3.取模

将十进制数 $mod$ $Q$

经验

如果将 $P=131$ 或 $13331$ ， $Q$ 取成 $2^64$ 在 $99.99$ %的情况下不会发生冲突。