哈希表——C++

目录

一、首先使用拉链法：

 二、开放寻址法

三、字符串哈希

1.具体如何使用进制的方式来存储字符前缀的可以看这个y总的这个图

2.接下来说一说算某个中间的区间的字符串哈希值

---

哈希表是一种数组之间互相映射的数据结构，比如举个简单的例子一个十个的数组要用一个五个的数组表示，我们可以使用取模的方法将十个数组中的数组映射到五个数字的小数组中。

核心思想是将数据项的键值（Key）通过哈希函数转换成数组的索引，从而直接访问数组中的位置来存储或查找数据项。

但是一个大的数组映射到小的数组中是很难避免映射冲突的问题的，为了解决这类问题，我们常用两个方法来解决；

• 拉链法
• 开放寻址法

一、首先使用拉链法：

拉链法顾名思义就是一个数组，每个数组上链接一个单链表，形状类似拉链，故拉链。

 但是如何取模运算，是我们需要解决的问题。

听y总说寻找大于规定范围最小的质数是冲突最小（我不知道为撒，但是听说数学有证明）

#include<iostream>
#include<cstring>
using namespace std;int main()
{for(int i=1e5;;i++){bool flag=true;for(int j = 2 ; j * j <=i;j++){if(i % j == 0){flag=false;break;}}if(flag){cout<<i<<endl;break;}}return 0;
}

例题：https://www.acwing.com/activity/content/problem/content/890/

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+3;
int h[N],e[N],ne[N],idx;void insert(int x)
{int k=(x%N+N)%N;  //保证k的值不为负数e[idx]=x;ne[idx]=h[k];h[k]=idx;idx++;
}bool find(int x)
{int k=(x%N+N)%N;  //保证k的值不为负数for(int i=h[k];i!=-1;i=ne[i]){if(e[i]==x)  return true;}return false;
}int main()
{int m;cin>>m;memset(h,-1,sizeof (h));while(m--){char op[2];int x;scanf("%s%d",op,&x);if(*op=='I'){insert(x);}else{if(find(x)) puts("Yes");elseputs("No");}}return 0;
}

 二、开放寻址法

开放寻址法可以叫它为蹲坑法，通常N要是数据范围的两倍，然后找最小的大于数据范围的质数

然后在相应的地方进行插入数据。

#include<iostream>
#include<cstring>
using namespace std;const int N=200003,null=0x3f3f3f3f;
int h[N];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;//保证k要么是空位置的地址，要么是这个数已经被存放过了
}int main()
{int n;scanf("%d",&n);memset(h,0x3f,sizeof h);while(n--){char op[2];int x;scanf("%s%d",op,&x);if(*op == 'I'){h[find(x)] = x;}else{if(h[find(x)] == null) puts("No");else puts("Yes");}}return 0;
}

三、字符串哈希

一般常使用哈希来解决字符串的问题，常用的方法就是将一个字符串差分成字符前缀，然后存储每个字符前缀的哈希值，然后这个哈希值常使用一种进制的表示方式来确定，然后在进行取余。（要点：一般使用131进制，取余的除数是，而且使用unsigned long long 来存储也就可以通过溢出直接进行自动取余）。

1.具体如何使用进制的方式来存储字符前缀的可以看这个y总的这个图

需要注意的是这里的哈希值的处理方式我们需要认为是不存在冲突的，这一点和之前的数值哈希有所不同，而且还要注意的是在映射的时候是不可以映射成为0的。

举个例子解释一下

如何某个字符前缀会映射成为0，那比如说A是0，那AB也就是0了，这样是不符合要求的。

2.接下来说一说算某个中间的区间的字符串哈希值

如图所示，最重要的公式就是

举个例子方便理解

我们在预处理h[i] 数组的时候,是把左边看成高位,右边看成低位(这与我们的习惯是相同的)
下面给出例子,计算[4,5]之间"de" 的哈希值   高位   a       b   c   d    e  低位  
                                                                               a        b      c  
                                             这是数组的下标        1      2   3    L    R   
                                       这里是P进制下位权    (p^4)  p^3  p^2   p^1   1

   我们在前缀和那节课已经学过了,怎么计算区间的部分和.  h[R] - h[L - 1].
   仔细一看,不对劲,位置对不上. 因此我们将字符串 "左移",为他们补上位权,这样子就能做到一一对应
                                    高位    a       b   c   d    e  低位  
                                                 a      b   c   '\0' '\0'
                 这是数组的下标        1      2   3    L    R   
         这里是P进制下位权    (p^4)  p^3  p^2   p^1   1

    为了方便理解,我用"\0"表示无意义字符. 这个时候就能计算了对吧?
    那位移是多少呢?
    就是 R - L + 1,在本例中, 5 - 3 + 1 = 2,左移两位. 补齐低位.

例题：https://www.acwing.com/activity/content/problem/content/891/

#include<iostream>
using namespace std;const int N=1e5+10,jinzhi=131;unsigned long long h[N],p[N];//h是存放每个字符子串的哈希值，p是存放字符串的权重的
char str[N];int get(int l,int r)
{return h[r]-h[l-1]*p[r-l+1];
}int main()
{int n,m;scanf("%d%d",&n,&m);scanf("%s",str+1);//初始化p[0]=1;for(int i=1;i<=n;i++){h[i]=h[i-1]*jinzhi+str[i];p[i]=p[i-1]*jinzhi;}while(m--){int l1,l2,r1,r2;scanf("%d%d%d%d",&l1,&r1,&l2,&r2);if(get(l1,r1)==get(l2,r2)){puts("Yes");}else puts("No");}return 0;
}