$$ Hash $$

笔记收录至此

• Hash算法是一个广义的算法，也可以认为是一种思想，使用Hash算法可以提高存储空间的利用率，可以提高数据的查询效率，Hash算法也被称为散列算法，Hash算法虽然被称为算法，但实际上它更像是一种思想。Hash算法没有一个固定的公式，只要符合散列思想的算法都可以被称为是Hash算法。
• 主要思想： 类似于函数，将某一希望被压缩的数字或者符号映射到值域上.
• 主要方法：
  1.直接寻址法: 即构造函数 $ H(key) = … $(函数的解析式,最简单的有直接取模等) ,
  2.折叠法:将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。
  (其实只要能够利用特定的计算方法，达到优化空间或者时间的目的即可)

拉链法:

使用的储存有点像链表的存储： 一条类似初始节点的链，每个节点下面再接经过H(key)处理得到相同值的数据

#include <iostream>
#include <cstring>

using namespace std;

//空间(数组长度)最好是质数，离2的整数次幂尽可能的远（减少冲突）
const int N = 1e6 + 3;

int e[N], ne[N], h[N],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(){
    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;
}

开放寻址法

其实也是使用一条链，但是这条链一般会很长，这样就即使H(key）相同，也不用连在一起，只要继续链往后面找哪里有空位，插入即可；但是值得一提的是，这样的冲突会比较大。（当然我们也可以再来一个T(key）判断这个两个映射值相不相同

#include <iostream>
#include <cstring>

using namespace std;

//用开放寻址法空间一般开 2 ~ 3 倍
const int N = 2e6 + 3, null = 0x3f3f3f3f;

int h[N], 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(){
    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;
}

字符串hash

核心：字符映射成 p 进制的数

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, P = 131;
typedef unsigned long long ull;

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

时间原因，还未完成