Hash

Hash(哈希)，是用来将很多数据分开来存储到数据容量小于本身的一种容器，可以达到减少时间的目的

当然Hash表我们可以通过数组来进行模拟

主要分为两种方法

拉链法
开放寻址法

拉链法

拉链法顾名思义，我们在摆放数据的时候，会出现某两条数据或者更多数据位于同一位置的情况，我们可以在该位置上拉一条链，将这些数据进行捆绑形存储

初始化

N：往往是一个质数(数学推理出来的结论)

e[N] 用来存储值，ne[N]用来存储链表中下一位，hs[N]哈希表

插入

插入的值很可能是负数，所以我们应该保证结果是正数

我们需要让x + N，但是这并不正确因为x的取最小值范围远小于N，所以我们应该先去对N进行取模，缩小一下N的范围接着再加上N，最后取模N，才能获取到插入位置的下标

(x % N + N) % N

后面的过程就是向链表头结点插入元素

查找

同理先找到x在哈希表中的下标，然后遍历链表，判断是否出现与x相同的情况，如果有，返回true，否则false

#include <bits/stdc++.h>
using namespace std;
const int N = 100003;
int ne[N],e[N],hs[N],idx;

void insert(int x) {
    int t = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = hs[t];
    hs[t] = idx ++;
}

bool query(int x) {
    int t = (x % N + N) % N;
    for(int i = hs[t];i != -1;i = ne[i]) {
        if(e[i] == x) return true;
    }

    return false;
}


int main(){
    memset(hs,-1,sizeof(hs));
    int n,a;string op;
    cin >> n;
    while(n--) {
        cin >> op >> a;
        if(op == "I") insert(a);
        else {
            if(query(a)) cout << "Yes" << endl;
            else cout << "No" << endl;
        } 
    }
    return 0;
}

开放寻址法(上厕所法)

大体思想

首先我们去查找x对应的hs下标，如果发现hs上已经有人的话，那么我们就查看下一位，直到查找没有人占用的坑位为止

初始化

memset初始化数组，memset是对每一个字节进行初始化，由于int有4个字节，如果我们初始化每一位为0x3f，那么数组中的每一位就是0x3f3f3f3f

N的初始化

N往往初始化为N的2到3倍之间，并且还需要是一个素数

查找x下标的操作

int find(int x) {
		int t = (x % N + N) % N;
		while(hs[t] != null && hs[t] != x) {
				t++;
				if(t == N) t = 0;
		}
		
		return t;
}

完整代码(附带插入和查找)

#include <bits/stdc++.h>
using namespace std;
const int N = 200003,null = 0x3f3f3f3f;

int hs[N];
int find(int x) {
    int t = (x % N + N) % N;
    while(hs[t] != null && hs[t] != x) {
        t++;
        if(t == N) t = 0;
    }

    return t;
}
int main(){
    memset(hs,0x3f,sizeof(hs));
    int n,v;string op;
    cin >> n;
    while(n--) {
        cin >> op >> v;
        int idx = find(v);
        if(op == "I") hs[idx] = v;
        else {
            if(hs[idx] != null) cout << "Yes" << endl;
            else cout << "No" << endl;
        } 
    }
    
    return 0;
}

字符串哈希

所有针对字符串的问题除了使用KMP解决外，还可以使用字符串哈希来解决

初始化

为什么P要定义位131或者是13331 ？

首先我们需要先将字符串看作一个P进制数，并且每一位对应ASCII中的某个数

由于ASCII的范围是0 - 128，为了防止不同字符串出现重复的情况，我们可以将P定为131(经验)这样可以保证每一个字符串由131进制转换成10进制都是不同的数

为什么数组类型为unsigned int int ？

其中可能出现字符串的长度过大的可能，还是131进制，很容易就溢出，所以我们需要对2 ^ 64(8个字节，每一个字节8位) 进行取模运算，我们此时可以使用unsigned int int这个类型在溢出的时候就相当于是对2 ^ 64自动取模

获取每一个前缀字符串对应的值

“abc” -> 前缀分别为”a”,”ab”,”abc” -> (ASCII) a \ (ASCII) a * 13 + (ASCII) b \ (ASCII) a * p * p + (ASCII) b * p + (ASCII) c

for(int i = 1;i <= s.size();i++) h[i] = h[i - 1] * 13 + s[i - 1];

获取字串函数

假如我们想要获取”abc”中从下标1到2(bc)

return h[2] - h[0] * p * p;

其实根据上面前缀字符串对应值的推理，我们大致能写出如下代码

所以如果我们想要获取从l -> r之间的字串值，书写函数如下

void get(int l,int r) {
		return h[r] - h[l] * p[l - r + 1]  //p数组代表了有几个p相乘
}

p数组初始化

p[0] = 1;
for(int i = 1;i <= s.size();i++) p[i] = p[i - 1] * 13;