【算法】哈希表

作者：指针不指南吗
专栏：算法篇

🐾或许会很慢，但是不可以停下来🐾

1.定义

• 哈希表（Hash table），是根据键（Key）直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这样就加快了查找速度。这个映射函数称做散列函数（哈希函数），存放记录的数组称做散列表。

• 就是把一堆庞大数据映射到一个小的数据结构中，比如把0~$10^9$ 映射到0~$10^5$ 的数组中。

  h(x)一般用x mod n，n表示数组大小，一般取一个质数，这样冲突出现的概率比较小。

• 冲突：当两个不一样的数，通过哈希函数，映射成一个数的时候，我们无法确定这两个数了，被称为冲突。

2.优点

查找速度快

• 哈希表是种数据结构，它可以提供快速的插入操作和查找操作。

• 不论哈希表中有多少数据，插入和删除，只需要接近常量的时间即 O( 1 ) 的时间复杂度。

  哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。

3.数字哈希

数字哈希是数字到数字的映射关系。

3.1拉链法

• 操作

  • 开一个一维数组来存储哈希值；

  • 添加值（处理冲突）

    • 把每一个数组变量看成是一个槽，在槽上拉一个链，映射 h(x)出来是对应在槽，即添加在其链上。

    • 每条链上的数的个数，期望值是2个

      • 整个数组链表大致地样子

    

    • 将一个数插在链表上面

    

  • 查找值

    映射h(x)一下 x ，遍历一下，它对应 槽的链上，有没有它

  • 删除值

    我们不会直接把它删掉，而是定义一个标记 bool，在对应想要删除的数值上，打一个标记。

• 代码实现

  • 向哈希表中插入一个数

  void insert(int x) 
  {int k=(x%N+N)%N;  //哈希（映射）函数，先取模再加N，再取模，是为了保证最后的值是正数e[idex]=x;   //插在对应槽的链表里面ne[idex]=h[k];h[k]=idex++;
  }
  

  • 在哈希表中查询某个数是否存在

  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;
  }
  

3.2开放寻址法

• 操作

  • 只开一个一维数组，数组的大小按经验来说一般是 数据范围的2~3倍；
  • 先看一下，对应的槽里有没有数，有数的话，找下一槽，直到找到没有数的槽；

• 代码实现

  int h[N];
  int null=0x3f3f3f3f;
  // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
  int find(int x)
  {int k = (x % N + N) % N;  //函数映射到槽上while (h[k] != null && h[k] != x)  //这个槽里面有数，并且·这个数不是我，循环继续{k ++ ;  //找下一个槽if (k == N) k = 0;  //如果找到最后了，返回0，继续寻找}return t;
  }
  

  • 添加元素：

    find(x)=x x不在哈希表里面，find的返回值就是该插入的位置

  • 查找元素：

    int k = find(x) 如果x不在哈希表中，返回x应该插入的位置,则该位置为空

    h[k]==null 说明哈希表里面没有这个值

  • 删除元素：

    和拉链法一样，定义一个bool变量，用作标记

3.3 例题

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

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<bits/stdc++.h>using namespace std;const int N=100003;  // N取100010的最大质数，100003
  int h[N],ne[N],e[N],idex;  //h表示数组中的槽，剩下的表示链表有关
  int n;void insert(int x)  //添加值的函数
  {int k=(x%N+N)%N;  //哈希（映射）函数，先取模再加N，再取模，是为了保证最后的值是正数e[idex]=x;   //插在对应槽的链表里面ne[idex]=h[k];h[k]=idex++;
  }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()
  {scanf("%d",&n );  //读入操作次数memset(h,-1,sizeof h);  //清空数组，空指针一般用 -1 表示char op[2];   //读入一个字符的时候，直接用字符数组读入，降低出错率int x;  while(n--){scanf("%s%d",op,&x);  //读入要操作的类型以及数据if(op[0]=='I') insert(x);else{if(find(x)) puts("Yes");else puts("No");}}return 0;
  }
  

• 方法二：开放寻址法

  #include<iostream>
  #include<cstring>using namespace std;const int N=200003,null=0x3f3f3f3f;  //N数组长度一般为数据范围的2~3倍且为质数，null表示空指针
  int h[N]; //h表示槽的位置
  int n;// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
  int find(int x)
  {int k = (x % N + N) % N;  //函数映射到槽上while (h[k] != null && h[k] != x)  //这个槽里面有数，并且·这个数不是我，循环继续{k ++ ;  //找下一个槽if (k == N) k = 0;  //如果找到最后了，返回0，继续寻找}return t;
  }int main()
  {scanf("%d",&n);memset(h,0x3f,sizeof h);while(n--){char op[2];int x;scanf("%s%d",op,&x);int k=find(x);if(*op=='I') h[k]=x;  //往哈希表里面插入元素else{if(h[k]!=null) puts("Yes");  //在哈希表里面寻找元素else puts("No");}}return 0;
  }
  

4.字符串哈希

字符串哈希是字符串到数字的映射关系。

我认为这个记住模板就行。

• 映射

  • 我们使用的映射关系是字符串到P进制数的映射关系（P是任意的），保证映射是一一对应的，不能有冲突。
  • 使冲突最小化，我们取P=131 或者 P=13331 ，并且把字符串映射到 $2^{64}$ 范围内的数字

• 操作

  1. 先预处理出来，字符串所有前缀的哈希

     
     防止冲突，不能映射成0。

  2. 求一段区间的哈希值

     

  3. 哈希映射的时候，要对数值取N的模，unsigned long long 的范围就是$2^{64}$ ，我们可以用它来巧妙地解决取模，因为正好 超过 unsigned long long 就会溢出。

• 代码模板

  typedef unsigned long long ULL;
  ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64// 初始化
  p[0] = 1;
  for (int i = 1; i <= n; i ++ )
  {h[i] = h[i - 1] * P + str[i];p[i] = p[i - 1] * P;
  }// 计算子串 str[l ~ r] 的哈希值
  ULL get(int l, int r)
  {return h[r] - h[l - 1] * p[r - l + 1];
  }
  

• 例题

  给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [ l1 , r1 ] 和 [l2,r2]这两个区间所包含的字符串子串是否完全相同。

  字符串中只包含大小写英文字母和数字。

  输入格式

  第一行包含整数 n 和 m，表示字符串长度和询问次数。

  第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。

  接下来 m 行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。

  注意，字符串的位置从 1 开始编号。

  输出格式

  对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

  每个结果占一行。

  数据范围

  1≤n,m≤$10^5$

  输入样例：

  8 3
  aabbaabb
  1 3 5 7
  1 3 6 8
  1 2 1 2
  

  输出样例：

  Yes
  No
  Yes
  

  #include<bits/stdc++.h>
  using namespace std;typedef unsigned long long ULL;  //ULL代替取模，映射哈希函数const int N=100010,P=131;
  ULL p[N],h[N];   //p表示前缀哈希，h表示哈希值int n,m;
  char str[N];ULL get(int l,int r)  //求某段区间的哈希值
  {return  h[r]-h[l-1]*p[r-l+1];  //右端点的前缀哈希值-左端-1的前缀和哈希值*区间进制
  }int main()
  {scanf("%d%d%s",&n,&m,str+1);  //预处理，直接从str+1 开始输入（后面涉及-1操作）p[0]=1;  //初始化，因为后面涉及-1和乘法for(int i=1;i<=n;i++){p[i]=p[i-1]*P;  //哈希映射，P进制h[i]=h[i-1]*P+str[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;
  }
  

  之后补充 STL 中哈希表用法