Hash 表

Hash 表

普通hash表的写法、字符串的hash方法

处理冲突的两种方式都非常常用

hash 表的主要作用？

什么情况下需要用到hash表？hash表最主要的作用就是把一个比较庞大的空间 0 ~ 10^9，把它映射到一个比较小的空间。一般情况下，把它映射到从 0 ~ N。N 比较小，一般为 10^5 ~ 10^6 级别

一开始集合是空的，有两种操作，第一种操作：向集合中插入一个数 x，第二种操作：询问某一个数 x 是否出现过，操作的个数是10^5

每一个插入的数或者查找的数的范围是 -10^9 ~ 10^9

在一个比较大的值域里面，从中选出一些数做插入，然后选出另外一些数来查询，操作的总数只有 10^5，为了能够快速地支持这两种操作，应该怎么做？

做法就是通过一个函数，这个函数输入一个 x ，这个 x 是 -10^9 ~ 10^9 之间的一个数，输出的是从 0 ~ 10^5 的一个数：这个函数可以把从-10^9 ~ 10^9 之间的一个数，把它映射到 0 ~ 10^5 之间的一个数，这个函数就被称为哈希函数

x mod 10^5 就可以把一个值域比较大的一个数映射到从 0 ~ 10^5 之间的一个数

哈希函数怎么写？一般情况下直接取模就可以了

由于值域的范围比较大，但是映射的结果比较小，因此这里面必然会产生冲突：就是把若干个不同的数映射成同一个数

冲突的情况是有可能发生的，需要去处理冲突

按照冲突的处理方式，把哈希表分为两种：第一种是开放寻址法，第二种是拉链法

离散化是一种极其特殊的哈希方式：双指针算法、位运算、离散化、区间合并_小雪菜本菜的博客-CSDN博客

离散化有一个很重要的特点是需要保序的，h() 这个函数是单调递增的

hash表是一般意义的哈希方式

下面分别来看一下这两种处理冲突的方式：

拉链法

首先开一个一维数组来存储所有的哈希值，h( x ) 会把 x 映射到从 0 ~ 10^5 - 1 的一个数，开数组的时候，开一个长度是 10^5 的数组就可以了，下标是 0 ~ 10^5 - 1

如何处理冲突？

当我们把一个 x 映射到某一个数的时候，假设第一次把 11 映射到 3，h( 11 ) = 3，就在 3 的下面拉一条链，把 11 存储下来

每一个位置可以当成一个槽，每一个槽下面都拉了一条链，用来存储这个槽上当前已经有的所有的数

假设第 2 次把 23 也映射到 3，h( 23 ) = 3，那么就在 3 这条链的末尾的位置或者开头的位置，在这个链上再增加一个数 23

如果两个数是冲突的，就会用一条链把它全部存下来

拉链法最终的形态如下，每一个槽下面都可能会拉很多数下来

hash表是一种期望算法，虽然每一个槽都会拉一条链，但是在平均情况下来看，每一条链的长度可以看成是常数，可以看成非常短，在一般情况下，哈希表的时间复杂度都可以看成是 O( 1 )

在算法题里面一般情况下，不需要从哈希表里面删除元素，一般只有添加一个数或者查找某一个数这两个操作

添加一个数，假设要添加 x，就先求一下 h( x )，然后看一下 h( x ) 对应的是哪个槽，然后把 x 插到这个槽对应的链上就可以了，这个链就是前面提到的单链表

假设要查找 x，先看一下 h( x ) 在哪个槽上，然后遍历这个槽对应的这个链表里面是否存在 x 就可以了

算法题里面如果要实现删除的话，不会真的把这个点删掉，一般情况下是开一个数组，在每一个点上打一个标记，开一个 bool 变量，如果要把它删掉的话，就在这个标记上记录一下就可以了，把它标记一下它被删除了

模拟散列表

拉链法的实现

一般来说在做hash表的时候，数组长度( 也就是 mod 的这个数 )，一般来说要取成一个质数，而且这个质数要离 2 的整次幂尽可能远，在数学上可以证明：如果这样取的话，冲突的概率是最小的

下面来看一下大于 10 w 的第一个质数是啥

#include <iostream>
using namesapce std;
 
//数据范围:10^5 开10^5个槽即可
const int N = 10010;
 
int main()
{
    //从10w开始遍历 找到第一个质数
    for(int i = 100000;;i++)
    {
        bool flag = true;
        //枚举i的所有质因子
        for(int j = 2;j * j <= i;j++ )
            if(i % j == 0)
            {
                flag = false;
                break;
            }
        //falg=true说明i是质数
        if(flag)
        {
            cout << i << endl;
            break;
        }
    }
    return 0;
}
 
/* 大于n的第一个质数是100003,因此N最好取成100003 */

读入一个字符，如果使用 scanf，尽量读入一个字符串，读入字符串 scanf 会自动把空格、回车和制表符忽略掉，可以降低出错的概率（有些数据可能会加一些额外的空格）

插入操作

现在已经求出了哈希值 k，要把当前 x 插入到 k 这个位置，这个 k 上可能已经有一个链了，要把 x 插入到这个链里面，应该怎么插入？（和单链表的插入类似）

查询操作

假设找到 k 了，第二步就是在 k 对应的链表里面找一下是否存在 x

for(int i = h[ k ]；i != -1；i = ne[ i ])
        if(e[ i ] == x)
            return true；
    return false；

从 h[ k ] 开始，h[ k ] 存储的就是链表里面第一个节点的下标，e[ i ] 就是当前这个点的值是多少，遍历完这个点后，要去找到下一个点的下标：下一个点的下标就是 ne[ i ]

i = ne[ i ]：从当前这个点的下标变到下一个点的下标

当我们走到空指针的时候，空指针的下标是 -1：所以 i != -1，如果 i = -1 就退出

#include <iostream>
//memset()的头文件
#include <cstring>    
using namesapce std;
 
const int N = 10003;
 
//hash表一般要开一个槽
int h[N];
 
//每一个槽上需要拉一个链:这个链就是前面提到的链表 链表中需要存储值e[]、存储下一个位置在什么地方ne[]
int e[N],ne[N];
 
//idx用来表示当前用到了哪一个位置
int idx;
 
//插入操作
//x的范围:-10^9 ~ 10^9 第一步需要先想一个哈希函数 把x映射到从0 ~ N之间的一个数
 
void insert(int x)
{
    //k表示哈希值
    int k = (x % N + N) % N;
    //在c++中的取模操作 如果是正数,余数就是正数 如果负数,余数就是负数 
    //需要再+N把余数变成正数再%N:目的就是让它的余数变成正数
    //插入就是把当前点插到h[k]上
    e[iex] = x;
    ne[idx] = h[k]; 
    head = idx;
    //当前 idx 的位置已经被使用了 idx 移到下一个位置
    idx++;
    /* h[k] = idx++; */
}
 
//查询操作:bool类型的操作
bool find(int x)
{
    //用同样的哈希函数把x映射到从0 ~ N-1之间的一个数
    int k = (x % N + N) % N;
    //遍历一个链表
    for(int i = h[k];i != -1;i = ne[i])
        //如果e[i]=x说明找到了x
        if(e[i] == x)
            return true;
    //没找到返回false
    return false;
}
 
int main()
{
    //从前往后做一下每一个操作
    int n;
    scanf("%d",&n);
    
    //需要把所有的槽先清空:空指针一般用-1来表示
    memset(h,-1,sizeof h);
 
    while(n--)
    {
        //操作一共有2种 I表示插入 else表示查询
        char op[2];
        int x;
        scanf("%s%d",op,&x);
        //插入操作
        if(*op == 'I') insert(x);
        else
        {
            //查询操作
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}
 
/* 大于n的第一个质数是100003,所以可以取成100003 */

为什么要用负数模上N？

在数学上，不管是正数还是负数，它的余数的定义都是正的：余数_百度百科

但是在 C++ 中不是这样的：一个正数 mod 上一个数余数是正数，一个负数 mod 上一个数余数是负数，为了让余数变成正数就需要麻烦一点：需要写成 (x % N + N) % N

取模运算（C++）_还没想好~的博客-CSDN博客_c++整除符号

直接加 N 再模 N 是不可以的

x 的范围是：-10^9 ~ 10^9，N 只有 10^5，当 x 很小的时候，例如 x = 10^9 的时候，-10^9 +10^5 还是负数，一定要先模 N，再加 N，再模 N

#include <iostream>
 
int main()
{
    cout << -10 % 3 << endl;    //在数学中余数应该是2 但是输出-1
 
    return 0;
}

拉链法其实就是一个单数组外加数组模拟邻接表的写法：链表与邻接表、栈与队列、单调栈、单调队列、kmp 算法_小雪菜本菜的博客-CSDN博客

int h[N]，e[N]，ne[N]，idx；

这一行定义与图论中存点的存储结构和拉链法的存储结构是一模一样的，都是一个数组拉了很多链

开放寻址法

只需要开了一个 一 维数组，没有去开链表，一维数组的长度一般来说要开到题目数据范围的 2 ~ 3 倍，假设题目里面输入了 10w 个数，数组的长度一般要至少开到 20w ~ 30w 的范围，开到这个范围，冲突的概率就比较低了

那么它是如何来处理冲突的呢？

和上厕所是一个道理，假设求出了一个 x 的哈希值是 k 的话，先看一下第 k 个位置有没有人，如果有人的话就去下一个坑位，以此类推，直到找到一个没有人的坑位的时候，就把 x 放进去

添加：先找到 k，然后从第 k 个坑位开始找，如果这个坑位有人的话就去下一个坑位

查找：从第 k 个坑位开始，从前往后找，每次先看一下当前坑位有没有人，如果当前坑位有人并且是 x 的话，那么就找到了 x；如果当前坑位有人，不是 x 就看下一个坑位；如果当前坑位没有人，说明 x 不存在

删除：从前往后找，按照查找的方式找 x，如果找到了 x 的话，一般不会把 x 真的删掉，一般是在数组里面打一个特殊的标记，标记 x 有没有被删掉，90% 的情况只会用到查找和添加，删除可以看成是查找的一种，删除就是找到之后打一个标记

find 函数可以看成是蹲坑法 hhh~

find这个循环的过程是一定会停止的，坑位总共开了两倍，一共 10w 个人，有 20w 个坑位 如果都满的话就会出现死循环，但是坑位的个数是人数的 2 ~ 3 倍，坑位一定比人多，不会发生死循环

null = 0x3f3f3f，是一个大于 10^9 的一个数，一定不在 x 的范围内

哈希表的时间复杂度都是 O( 1 ) 的，用到哈希表的时间复杂度都是 O( n )

memset(h，0，sizeof h) 或者 memset(h，-1，sizeof h) 为什么很常见？

0 这个数字的每一个字节都是 0，因此把每一个字节都赋值成 0 的话，每一个数就是 0

-1 在 c++ 中表示的时候，是每一个位上的数字都是 1，把每一个字节都赋值成 -1 的话，整个就是 -1

#include <iostream>
using namesapce std;
//一般是开成2倍:首先要找到一个大于 20w 的最小质数
//用一个数null来表示这个位置是空的,这个数只要不在数据范围里面就可以了
const int N = 200003,null = 0x3f3f3f;
 
//hash表一般要开一个槽
int h[N];
 
//需要约定一个标志:如果数组里面某一个数等于这个数的话就说明这个位置上没有人[需要保证这个数不在数组里面]
 
//插入操作
//x的范围:-10^9 ~ 10^9 第一步需要先想一个哈希函数 把x映射到从0 ~ n之间的一个数
 
//核心操作是find(x):如果x在哈希表中已经存在的话 返回x所在的位置 如果不存在的话返回的是它应该存储的位置
int find(int x)
{
    //1.用一个哈希函数把 x 映射到数组下标范围内
    int k = (x % N + N) % N;
    //从前往后看,如果说当前这个位置不等于0x3f3f3f,也就是说这个坑位上有人,并且这个坑位上的人不等于x
    while(h[k] != null && h[k] != x)
    {
        //这个人就要往后看下一个坑位
        k++;
        //如果k=N说明我们已经看完了最后一个坑位,就要再循环看第一个坑位
        if(k == N) k = 0;
    }
    //最后返回k,返回k有两种含义:如果x在哈希表中,k就是x的下标;如果x不在哈希表中,k就是x应该存储的位置
    return k;
}
 
int main()
{
    int n;
    scanf("%d",&n);
    
    //初始化的时候把h初始化为0x3f即可:这样h里面的每一个数都等于0x3f3f3f
    /* 为什么是 memset 0x3f? 
       由于这个函数是按字节来进行memset的,不是按数来memset,h是一个int类型的数组
       一共有4个字节,每一个字节都是0x3f,把int每一个字节全部变成0x3f,每一个数就是4个0x3f,就是0x3f3f3f*/
    memset(h,0x3f,sizeof h);
 
    //从前往后做每一个操作
    while(n--)
    {
        //操作一共有2种 I表示插入 else表示查询
        char op[2];
        int x;
        scanf("%s%d",op,&x);
        //先找到k
        int k = find(x);
        //插入操作
        if(*op == 'I') 
        {
            //先找到k
            //int k = find(x);
            h[k] = x;
        }
        else
        {
            //先找到k
            //int k = find(x);
            //查询操作
            if(/* find(x) */h[k] != null) puts("Yes");
            else puts("No");
        }
    }
    /* cout << 0x3f3f3f << endl; */
    return 0;
}
/* 1061109567 比10^9大 */

字符串hash

一个比较重要的 hash 方式，有很多字符串的问题都可以用字符串 hash 来做，不一定要写 kmp

特殊的 hash 方式：字符串前缀哈希法

假设有一个字符串 str = "ABC. . ."，求哈希的时候，首先预处理出所有前缀的哈希

h[ 1 ] 表示前一个字符的哈希

h[ 1 ] 表示前两个字符的哈希

. . .

h[ 0 ] 特殊定义，表示前零个字符的哈希，就是 0

注意：h[ 1 ] 不是等于这个字符串，而是等于这个字符串的哈希值

首先先把每一个前缀的哈希值先求出来，下面遇到两个问题？

如何来定义某一个前缀的哈希值？（把一个字符串哈希成一个数字）

定义方式如下：

把这个字符串看成是一个 p 进制的数，每一位上的字母就表示这个 p 进制数每一位数字，这个字母需要转换成它的 ASCII 码

A 表示 p 进制的第一位是 A

下面举一个例子：

假设现在想求 "ABCD" 这个字符串的哈希值，(第一步把这个字符串看成是一个 p 进制的数)，由于这个字符串一共有 4 个字母，就看成有 4 位，第一位上的数是 A，第 2 位上的数是 B，第 3 位上的数是 C，第 4 位上的数是 D，假设所有的字母都是大写字母 A ~ Z，先把 A 当成数字 1，把 B 当成数字 2，把 C 当成数字 3，把 D 当成数字 4，以此类推，Z 就是 26

ABCD 这个字符串就可以看成是 p 进制的 1234，它对应的十进制数如下图所示（第二步把这个 p 进制的数转换成十进制的数）

通过这样的方式把字符串转化成一个数字，这个数字可能会非常大，因为字符串的长度可能是 10w、20w 级别，所以数字可能是一个几十万位的一个数，不好做存储，所以(最后要对这整个数 mod 一个比较小的数 Q，通过取模就可以把整个数字映射到一个从 0 ~ Q - 1 的数)，这个就是字符串哈希的方式

通过以上操作，我们就可以把任何一个字符串映射到从 0 ~ Q - 1 之间的一个数

注意：不能把某一个字母映射成 0，如果把某一个字母映射成 0，会把不同的字符串映射成同样一个数字，会产生冲突，一般情况下，把它映射成从 1 开始比较好

假设把字母 A 映射成数字 0，A 的哈希值是应该是 0，AA 也是 0（0 的 p 进制数等于 10 进制的 0）

前面哈希数字的时候是可能会存在冲突的，但是我们有一个机制来处理冲突，注意：这里的字符串哈希方法是假定我们人品足够好，假定 Rp 足够好，不存在冲突，完全不考虑冲突的情况

当 p = 131 或者 p = 13331，Q = 2^64 在 99.9% 的情况下可以假定是不会出现冲突的

用这样一种哈希方式配合前缀哈希的好处：可以利用前缀哈希算出任 一 一 个子串的哈希值

如果想求字符串从 L ~ R 这一段子串的哈希值应该怎么求？

字符串的下标从 1 开始，方便处理前缀

已知从 1 ~ R 的哈希值 h[ R ]，以及从 1 ~ L - 1 的哈希值 h[ L - 1 ]，如果通过这两个数把从 L ~ R 的哈希值计算出来

因为是把 1 ~ R 这些字母看成是一个 p 进制的数，h[ R ] 左边是高位，右边是低位，h[ L - 1 ] 也是左边是高位，右边是低位

在 h[ R ] 里面，R 是第 0 位，h[ 1 ] 是 R - 1 位

在 h[ L - 1 ] 里面，L - 1 是第 0 位，h[ 1 ] 是 L - 2 位

第一步需要先把 h[ L - 1 ] 这一段往左移动，移动到与 h[ R ] 的左边对齐为止，第二步就是让 h[ R ] 减去这一部分  

h[ L - 1 ] 最高位 p^L-2，最低位是 p^0

h[ R ] 最高位 p^R-1，最低位是 p^0

最终通过公式：h[r] -h[l - 1] * p[r - l + 1]；就可以求出从 L ~ R 这一段的哈希值

需要 mod Q = 2^64？这里有一个使用技巧：

用 unsigned long long 来存储所有的 h，就不需要取模了，溢出就相当于取模 2^64

因此我们预处理完每一个前缀的哈希值之后，就可以用 O( 1 ) 的时间算出来任意一个子串的哈希值

预处理前缀的哈希值的方式：h[ i ] = h[ i - 1 ] * P + str[ i ]；

    // 预处理 p 数组和哈希数组 h
    for (int i = 1；i <= n；i ++ )
    {
        // 预处理字符串前缀和
        h[ i ] = h[ i - 1 ] * P + str[ i ]； // 将字符转换成P进制的数，+ str[ i ] 是第 i 位字符的 ASCII 码值
        // 预处理数组p[ ]，p[ i ]数组表示的是p的i次方的值是多少
        p[ i ] = p[ i - 1 ] * P；              // 即 p[1] = P，p[2] = P*P，p[3] = P^3
    }

字符串哈希

 

 给定一个长度是 n 的字符串，给定 m 个询问，每一个询问是问：两个区间里面的字符串是不是完全相同的，询问的个数是 10^5，完全相同的话输出 "Yes"，否则输出 "No"

首先把原字符串所有前缀的哈希值求出来，当我们想询问两个区间的时候，就分别使用公式计算出这两个区间的字符串的哈希值，这两个哈希值都是从 0 ~ 2^64 - 1 的数，如果两个哈希值相同的话，就认为这两个字符串相同，如果两个哈希值不同的话，就认为这两个字符串不同

#include <iostream>
 
using namesapce std;
 
//typedef就是用ULL表示某一种类型的变量
typedef unsigned long long ULL;
 
//P一般取131或者13331
const int N = 100010,P = 131;
 
int n,m;
char str[N];
//p数组用于存储p的多少次方:公式里面乘了一个p的多少次方可以先把它预处理出来
ULL h[N],p[N];
 
//用函数来表示公式
ULL get(int l,int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
 
int main()
{
    //str+1表示从下标为1开始存储
    scanf("%d%d%s",&n,&m,str + 1);
    //p的0次方等于1
    p[0] = 1;
    //从第1个字母开始
    for(int i = 1;i <= n;i++)
    {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];
    }
    //m个询问
    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;
}

h 数组表示某一个前缀的哈希值，h[ i ] 表示前 i 个字母前缀的哈希值，P 表示 P 进制

p数组用来存储 h 要乘的 p 的多少次方，h 数组用来存储每个前缀字符串的哈希值
      如str = "ABCD"
        h[0] = 0；
        h[1] = "A"的哈希值      （将字符转换成p进制的一个数字）
        h[2] = "AB"的哈希值    （将字符转换成p进制的一个数字）
        h[3] = "ABC"的哈希值  （将字符转换成p进制的一个数字）
        h[4] = "ABCD"的哈希值（将字符转换成p进制的一个数字）

[AcWing]841. 字符串哈希（C++实现）字符串哈希模板题_Cloudeeeee的博客-CSDN博客

把前 l - 1 位乘上 p 的 r - l + 1 次方（相当于对齐位数并补 0），再用 h[ r ] 减去这个数即可

举个例子：有一个字符串 ABCDE ，下标从 0 开始，输入 l = 1，r = 3
假设哈希值计算出来如下：
        h[3] = 1234
        h[1] = 12
        h[0] = 1
则根据公式：h[r] - h[l - 1] * p[r - l + 1]
        得到：
h[3] - h[1 - 1] * p[3 - 1 + 1] = 1234 - 1*1000 = 234
即这个 234 就表示了 [ l，r ] 的哈希值（注意是左闭右闭）
p[ i ] 数组表示 p 的 i 次方的值是多少

字符串哈希_Tommy Vercetti的博客-CSDN博客_字符串哈希

字符串前缀哈希：要想处理出来字符串任意区间内的hash， 我们首先要处理出来所有的前缀hash，例如：ABCDE我们先处理出来h[1]代表A的hash，h[2]代表B的. . .以此类推，处理办法：进制的求算公式：例如十进制的数字：145，P = 10
1 ∗ 10^2 + 4 ∗ 10^1 + 5 ∗ 10^0 总结公式如下：
a × P^4 + b × P^3 + c × P^2 + d × P^1 + e × P^0，要处理某一个前缀的 hash 值，要把字符串当成一个 P 进制的数，然后每一位的字母的 ASCII 值就代表这一位的数字，则 abcde 的 hash 值为上述式子

当我们需要快速判断两个字符串是不是相等的时候，就可以使用字符串 hash，时间复杂度为 O( 1 )

本来比较两个字符串需要一个字母一个字母比较，时间复杂度为 O( n )

kmp 可以用来求一个字符串的循环节，但是字符串 hash 不能用来求循环节