文章目录
前言
一、哈希表
二、哈希方法
存储方式
拉链法
原理
数组长度
开放寻址法
原理
数组长度
字符串哈希
三、例题，代码
AcWing 840. 模拟散列表
本题解析
AC代码
AcWing 841. 字符串哈希
本题解析
AC代码
四、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：哈希表，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、哈希表
哈希表实际上就是一个映射，将一个大区间的数据映射成小区间的数据，在STL中的 map 容器的实现方式就是哈希，在这里，我们介绍哈希的两种方法：开放寻址法和拉链法
二、哈希方法
因为我们处理哈希其实就是一个映射的过程，举个例子，比如我们要把-1e9~1e9的数映射到0~1e5的级别，我们的映射方法其实很简单：直接x mol 1e5，x为将要映射的值。因为把一个数据范围很大的变成很小，所以很容易会有冲突，比如我们把5映射到了7，也把2映射到了7，对于冲突，我们的处理就有两种：拉链法和开放寻址法.
存储方式
拉链法
原理
对于冲突的映射我们做如图所示的处理：
数组长度
对于我们开的数组长度，我们一般取成质数，这样产生冲突的概率是最小的，所以我们在写题之前可以先写一个代码去看一下大于题给要求的第一个质数是多少，如何算质数见博客：数学知识：质数
开放寻址法
原理
处理冲突的方式：我们看一下映射后的那个值是否已经有数了，如果没有的话，就把它放到这个数中，如果已经有数的话，那么就到下一个位置重复上述操作
数组长度
一般开到需要的两到三倍，同样我们也需要保证是质数，所以我们在写题之前可以先写一个代码去看一下大于题给要求的第一个质数是多少，如何算质数见博客：数学知识：质数
字符串哈希
三、例题，代码
AcWing 840. 模拟散列表
本题链接：AcWing 840. 模拟散列表
本博客给出本题截图
本题解析
AC代码
拉链法
#include <cstdio> #include <cstring> using namespace std; const int N = 100003; int h[N], e[N], ne[N], idx; void insert(int x) { int k = (x % N + N) % N; //让取模后的值为正数 e[idx] = x; ne[idx] = h[k]; h[k] = 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 == 'I') insert(x); else { if (find(x)) puts("Yes"); else puts("No"); } } return 0; }
开放寻址法
find函数：返回的是一个位置，如果x存在的话返回的就是x的位置，如果x不存在的话，返回的就是它应该在的位置，首先，我们需要用一个数表示这个位置上是空的，那么我们只需要让这个数不在数据范围内即可，本题就可以去null = 0x3f3f3f3f
#include <cstdio> #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; } int main() { int n; 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; }
AcWing 841. 字符串哈希
本题链接：AcWing 841. 字符串哈希
本博客给出本题截图
本题解析
预处理字符串的前缀哈希：
str = "ABCDEFG" h[0] = 0; h[1] = "A"的hash h[2] = "AB"的hash h[3] = "ABC"的hash ......
如何求字符串的hash：
把每一位当成p进制的数 例如"ABCD" 我们对应来看可以是 A B C D (1 2 3 4)p 那么对于"ABCD"而言的十进制表达为： 1 * P³ + 2 * p² + 3 * p + 4
我们说过，哈希其实就是映射，我们求得的数字可能会非常的大，所以我们可以取模
(1 * P³ + 2 * p² + 3 * p + 4) mol Q
这里我们给出一些规定：
不能把一个字母的hash值映射成0
冲突处理方法：人品足够好没有冲突
我们一般把p取值为131或13331
Q取值为2^64
通过这种处理方法我们就可以算出来任意子区间的hash，计算类似于 前缀和
我们取模的时候，我们可以用unsigned long long去存储h，这样就不需要取模了，溢出就是取模
我们字符串哈希主要是可以处理在一段字符串中，题给出两段区间，询问是否完全相同，当处理数据达到1e5的时候，是 KMP 也无法做到的，只可以用字符串哈希
本题中的p数组是用来存储p的次方
AC代码
#include <iostream> #include <algorithm> using namespace std; typedef unsigned long long ULL; const int N = 100010, P = 131; int n, m; char str[N]; ULL h[N], p[N]; ULL get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; } int main() { scanf("%d%d", &n, &m); scanf("%s", str + 1); p[0] = 1; for (int i = 1; i <= n; i ++ ) { h[i] = h[i - 1] * P + str[i]; p[i] = p[i - 1] * P; } 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; }
四、时间复杂度
关于哈希表各步操作的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
