哈希表

2021-09-20

近似 O(1)的时间复杂度

哈希表一般算法中处理的问题

插入一个数
查找一个数
删除一个数

实现哈希表的两种做法

拉链法

首先选择拉链法来解决问题，拉链法用通俗的话来说，就是数组+单链表的实现
选择 hash 函数将大整数 x 映射成为小整数的

#include<iostream>
#include<cstring>
using namespace std;
const int N = 100002;

int e[N],ne[N],idx;
int h[N];

void insert(int x){
    int y = (x % N + N) % N; //为了缩小y 同时也避免负数的存在
    e[idx] = x; //在每一个数组下面拉出一条链 insert等同于单链表的操作
    ne[idx] = h[y];
    h[y] = idx++;
}

bool find(int x){
    int y = (x % N + N ) % N;
    for(int i = h[y] ; i != -1 ; i = ne[i])
        if(e[i] == x)
            return true;
    return false;
}

int main(){
    int n;
    cin >> n;
    memset(h,-1,sizeof h);
    while(n --){
        char op;
        int k;
        cin >> op >> k;
        if(op == 'I')insert(k);
        else{
            if(find(k))puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

开放寻址法

开放寻址法本质也是从前往后插入，比拉链法更简单的是它只需要开一个数组，操作和理解起来相对容易一点。开放寻址法从前往后找找到空的地方插入，如果已经有了就让当前这个位置的加一

840. 模拟散列表

#include<iostream>
#include<cstring>
using namespace std;
const int N = 200003,null = 0x3f3f3f3f;
int h[N];
int find(int x){
    int t = (x % N + N)%N;
    while(h[t] != null && h[t] != x){
        t ++;
        if(t == N)t = 0;
    }
    return t;
}
int main(){
    int n;
    cin >> n;
    memset(h,0x3f,sizeof h);
    while(n --){
        char op;
        int x;
        cin >> op >> x;
        int k = find(x);
        if(op == 'I'){
            h[k] = x;
        }else{
            if(h[k] == null)puts("No");
            else puts("Yes");
        }
    }
    return 0;
}

字符串哈希

(字符串哈希) O(n)+O(m)

全称字符串前缀哈希法，把字符串变成一个 p 进制数字（哈希值），实现不同的字符串映射到不同的数字。
对形如 X1X2X3⋯Xn−1Xn
的字符串,采用字符的 ascii 码乘上 P 的次方来计算哈希值。

映射公式 (X1×Pn−1+X2×Pn−2+⋯+Xn−1×P1+Xn×P0)modQ

注意点：

任意字符不可以映射成 0，否则会出现不同的字符串都映射成 0 的情况，比如 A,AA,AAA 皆为 0
冲突问题：通过巧妙设置 P (131 或 13331) , Q (264)
的值，一般可以理解为不产生冲突。

问题是比较不同区间的子串是否相同，就转化为对应的哈希值是否相同。
求一个字符串的哈希值就相当于求前缀和，求一个字符串的子串哈希值就相当于求部分和。

前缀和公式 h[i+1]=h[i]×P+s[i]
i∈[0,n−1]
h 为前缀和数组，s 为字符串数组
区间和公式 h[l,r]=h[r]−h[l−1]×Pr−l+1

区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样，只差两位，
乘上 P2
把 ABC 变为 ABC00，再用 ABCDE - ABC00 得到 DE 的哈希值。

作者：chocolate-emperor
链接：https://www.acwing.com/solution/content/24738/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

841. 字符串哈希

#include<iostream>
#include<cstring>
using namespace std;
typedef unsigned long long ULL;
const int N = 100010,P = 131;
ULL p[N],h[N];

ULL get(int l,int r){
    return h[r] - h[l-1]*p[r-l+1];
}


int main(){
    int n,m;
    string str;
    cin >> n >> m >> str;
    p[0] = 1;
    h[0] = 0;
    for(int i = 1 ; i <= n ; i ++){
        p[i] = p[i-1] * P;
        h[i] = h[i-1] * P + str[i - 1];
    }
    while(m -- != 0){
        int l1,r1,l2,r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if(get(l1,r1) != get(l2,r2))puts("No");
        else puts("Yes");
    }
    return 0;
}