hash 哈希表

哈希表是一种期望算法。

一般情况下，哈希表的时间复杂度是 O(1)。

作用

将一个复杂数据结构映射到一个较小的空间 0~N（10^5~10^6），最常用的情景：将 0~10^9 映射到 0~10^5。

离散化是一种及其特殊的哈希方式。离散化是需要保序的，是要求单调递增的。

映射的方法叫做哈希函数。

哈希函数

取模

x mod 10^5将 x 映射到 0~10^5 中。

模数的选择

模的数一般取质数，即 mod 后面的数一般取质数，并且距离2的整数次幂远，这样取冲突的概率最小【由此可以确定映射数组的长度】。

做题时，选择超过数据范围的第一个质数。

存在冲突

因为 x 的定义域比较大，而映射到的值域比较小，就可能将若干不同的数映射为一个相同的数，产生冲突。

处理方式

1. 开放寻址法
2. 拉链法：每个哈希表中的元素都是一个链表的头节点。每当将一个值映射到某个空间，那就将这个值放在该空间所代表的链表中。

存储结构

拉链法

处理冲突

h(x)∈(0,10^5)，开一个宽度为10^5的数组，数组下标是0~10^5-1。{ 将映射的数组当成一个槽，在槽上拉链，如果两个数是冲突的，那么就用一条链将其相连，该链就是单链表 }h(a)=b【将a映射为b】，就在数组下标为b的元素上拉一条链，用于存储a；h(c)=b【将c映射为b】，在数组下标为b的元素的链上再存上c【在该链的末尾和开头增加都可以】。

哈希表是一种期望算法， 从平均情况上看，每条链的长度可以看成一个常数，一般情况下，哈希表的时间复杂度是 O(1)。

操作

一般只有添加、查找操作，没有删除操作。

数据

h，映射得到的数组，数组中每个元素作为该槽对应的单链表的头指针存在

e，单链表的数据域

ne，单链表的指针域

idx，存储当前已经用到哪个点

添加

添加 x，先求 h(x)，根据 h(x) 确定 x 对应的槽【将 h(x) 作为下标查找哈希表中对应的链表】，然后将 x 插到该槽对应的链【单链表】上。

为什么不直接int k=x%N?

如果这样，正数取模结果是一个正数，负数取模结果是一个负数。先取模再加N，使得结果一定是一个正数，然后再取模，这样无论是正数还是负数取模的结果都是正数。

void insert(int x){
    int k=(x%N+N)%N;
    e[idx]=k;
    ne[idx]=h[k];
    h[k]=idx;
    idx++;
}

查找

查找 x，先求h(x)，确定 x 对应的槽，然后遍历该槽对应的链表，查看链表中是否存在 x 即可。

bool find(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;
}

删除

算法中要实现删除操作，不会真的将该点删除。一般情况是开一个数组，在每个点上做一个标记，比如使用 bool 变量。

开放寻址法

只开一个一维数组，该数组的长度要达到题目要求的 2~3 倍【经验值】，此时冲突的概率比较低。这样会导致在查找时在遍历完数组一遍之前一定会停止，不会一直找下去。

处理冲突

h(x)=k，先查看数组中下标为 k 个位置是否被占用，若无，自己占用，若有，去下一个位置，直到找到一个未被占用的位置将其占用。

操作

memset(h,0x3f,sizeof h);为什么不初始化为0x3f3f3f3f?

按字节memset，不是按数memset，h是int型数组，有四个字节，每一个字节都是0x3f，一共有4个字节，就是0x3f3f3f3f。

寻找位置

若x在哈希表中存在，返回其所在位置，不存在返回其应该存储的位置。

若是查找途中越界，则应该从数组开头继续找，直到整个数组遍历了一遍。

int find(int x){//若x在哈希表中存在，返回其所在位置，不存在返回其应该存储的位置
    int k=(x%N+N)%N;
    while(h[k]!=null&&h[k]!=x){
        k++;
        if(k==N)//看完最后一个位置，回到数组开头
            k=0;
    }
    return k;
}

添加

添加 x，x 通过哈希函数计算得到哈希值，将其作为我们所期望的下标，若存在冲突，向后查看，找到后面第一个没有被占用的位置，将数据 x 放入。

int k=find(x);

h[k]=x;

查找

查找 x，x 通过哈希函数计算得到哈希值，将其作为我们所期望的下标进行查找，若当前位置没有数据，则数据不存在，若该位置有数据且是所要查找的值，则查找成功，若该位置有数据但不是所要查找的值，则继续向后进行遍历查找，直到没数据或找到数据为止。若是查找途中越界，则应该从数组开头继续找，直到整个数组遍历了一遍。

int k=find(x);

if(h[k]!=null)

puts("Yes");

else

puts("No");

删除

删除 x，与拉链法类似，按查找的方式找 x，找到后做标记即可。

例题——模拟散列表

题目描述

维护一个集合，支持如下几种操作：

1. I x，插入一个数 x；
2. Q x，询问数 x 是否在集合中出现过；

现在要进行 N 次操作，对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 N ，表示操作数量。

接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。

输出格式

对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1 ≤ N ≤ 10^5

−10^9 ≤ x ≤ 10^9

输入样例

5

I 1

I 2

I 3

Q 2

Q 5

输出样例

Yes

No

拉链法

#include<iostream>
#include<cstring>
using namespace std;
const int N=100003;//是质数且距离2的整数次幂远
int h[N];//开的槽
int e[N],ne[N],idx;//链表
void insert(int x){
    int k=(x%N+N)%N;
    e[idx]=k;
    ne[idx]=h[k];
    h[k]=idx;
    idx++;
}
bool find(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(){
    int n;
    scanf("%d",&n);
    memset(h,-1,sizeof h);//清空所有的槽
    while(n--){
        char op[2];
        int x;
        scanf("%s%d",op,&x);
        if(op[0]=='I')
            insert(x);
        else{
            if(find(x))
                puts("Yes");
            else
                puts("No");
        }
    }
}

开放寻址法

#include<iostream>
#include<cstring>
using namespace std;
const int N=200003;//是质数且距离2的整数次幂远
const int null=0x3f3f3f3f;//约定：数组元素值为0x3f3f3f3f时，该位置为空
int h[N];
//若x在哈希表中存在，返回其所在位置，不存在返回其应该存储的位置
int find(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);//按字节memset
    while(n--){
        char op[2];
        int x;
        scanf("%s%d",op,&x);
        int k=find(x);
        if(op[0]=='I'){
            h[k]=x;
        }
        else{
            if(h[k]!=null)
                puts("Yes");
            else
                puts("No");
        }
    }
    return 0;
}

字符串哈希方式

字符串前缀哈希法

先预处理出字符串所有前缀的哈希值，h[0] 具有特殊含义，表示前0个字符的哈希值，h[n] 表示前n个字符的哈希值。之后可以使用前缀的哈希值使用 O(1) 的时间复杂度算出任意一个子串的哈希值。

字符串前缀哈希值的定义方式

将字符串看成 p 进制的数，字符串的每一个字符当作 p 进制数的每一位数字，再将该 p 进制的数换算为一个十进制的数，因此可将整个字符串转化为一个特别大的数，然后再将该数模上一个比较小的数 Q，通过取模就可将该数映射到 0~Q-1 之间的一个数。

注意

1. 一般情况下，不将要字母映射为 0，避免产生冲突【例如，将‘A’映射为0，那么字符串“A”的 p 进制是 0，转化为十进制也是 0；字符串“AA”的 p 进制是 0，转化为十进制也是 0，会产生冲突】。

原因：若该字母映射为0，那一个完全由该字母组成的字符串，无论有多少位，他的hash值始终是0，会冲突。

1. 假定 Rp 足够好，不存在冲突

当 P=131 或 P=13331，Q=264 时，一般不会存在冲突。

1. 其实字母映射的值不重要

其实字母映射出来的值具体是什么其实不重要，进制数主要是用于求取hash值的。所以无论是字母还是数字，只要保证两个不同的字母或数字，二者对应的整型值不同，那将该值对应的整型直接利用即可。·

求前缀子串的哈希值

h[0]=0;

h(i)=h(i-1)*P+str[i];//字母从下标为1开始存储

作用

可以利用前缀哈希，利用一个公式算出任意一个子串的哈希值。

如何求区间[L,R]子串的哈希值？

字符串下标从1开始，已知 1~L-1【h[L-1]】和 1~R【h[R]】的哈希值。

左边是高位，右边是低位。在 h[R] 中，R是第0位，1是第R-1位；在 h[L-1] 中，L-1是第0位，1是第L-2位。

将 h[L-1] 这一段向左移，移到和 h[R] 对齐为止，即 h[L-1]*pR-L+1 ，则区间 [L,R] 子串的哈希值是 h[R]-h[L-1]*pR-L+1 。

直接使用 unsigned long long 存储所有哈希值，就不需要取模了，溢出就相当于取模【溢出等价于模上264】。

预处理完所有前缀的哈希值之后，就可以使用 O(1) 的时间复杂度算出任意一个子串的哈希值。

为什么h[R] - h[L-1]*pR-L+1可以求出[L,R]子串的hash?

因为(a - b) % c == (a%c - b%c) % c

[L,R]子串就是R子串的hash - L子串hash*(p的R-L差值之幂)

为什么不需要取模？

由于unsigned long long 自动取模，所以可用此公式求出子串hash。

例题——字符串哈希

#include<iostream>
using namespace std;
typedef unsigned long long ULL;
const int N=100010,P=131;
char str[N];
ULL h[N],p[N];//p数组用来存储p的多少次方
int n,m;
ULL get(int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}
int main(){
    scanf("%d%d%s",&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];//因为映射字母成多少都无所谓，所以可以直接使用ASCII码
    }
    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;
}