网站导航
> 文章列表 > 【算法】哈希表

【算法】哈希表

网友: 文章列表 2024-03-21 15:53:01

【算法】哈希表

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

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

文章目录

  • 1.定义
  • 2.优点
  • 3.数字哈希
    • 3.1拉链法
    • 3.2开放寻址法
    • 3.3 例题
  • 4.字符串哈希

1.定义

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

  • 就是把一堆庞大数据映射到一个小的数据结构中，比如把0~10910^9109 映射到0~10510^5105 的数组中。

    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 ≤ 10510^5105
−10910^9109 ≤ x ≤ 10910^9109

输入样例：

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 ，并且把字符串映射到 2642^{64}264 范围内的数字

  • 操作

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

      【算法】哈希表
      防止冲突，不能映射成0。

    2. 求一段区间的哈希值

      【算法】哈希表

    3. 哈希映射的时候，要对数值取N的模，unsigned long long 的范围就是2642^{64}264 ，我们可以用它来巧妙地解决取模，因为正好 超过 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≤10510^5105

    输入样例：

    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 中哈希表用法
    Alt

网络标签：

相关问题