hash学习笔记

学长来讲了hash，感觉好香

哈希算法

算法概况

hash是一种思想 是一种广义的算法 不懂的可以百度

而我们常将哈希的思想用在字符串中 用于O(1) 判断给出的两个字符串是否相等（预处理完的情况下）

例题&算法

这里结合例题理解一下：
给出两个字符串A与B 每次询问给出l,r,s,t 判断A[l...r] 与 B[s...t]是否相等

如果我们用裸的暴力的话 显然对于每次询问我们都要用O(n) 的效率 所以对于m次询问效率是O(nm)但是我们用hash可以很轻松的解决这个问题
关于一个字符串我们很显然是无法直接O(1)比较的 但是对于一个数字可以 所以我们可不可以把一个字符串转化为数字呢？
答案是肯定的

• 首先我们存入一个字符串 然后通过把字符串转化为ASCII码值 然后就可以把字符串转化为数字了
• 因此我们定义一个数组f[i]表示当前字符串的第i位 的前缀和 （类似前缀和），那么f[i] 的求法如下

for(int i = 1;i <= strlen(s1+1);++i){
        f1[i] = f1[i-1] * base + s1[i] - 'a' + 1;
}

• 注意我们这里用到了base base其实是自己定义的一个进制位 可以自己随意定义，根据题目自己定义，大小自己定，为了防止出现两个不同的字符串存成相同的值

• 因此这样我们就处理出了前缀和，那么对于取区间的问题 显然不能像普通的前缀和那样直接减 所以我们又要用到一个pw数组，用来辅助我们求区间和

pw[0] = 1;
for(int i = 1;i <= strlen(s1+1);++i){
    pw[i] = pw[i-1] * base;
}

下面给出例题代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
const int base = 223;
int pw[maxn],f1[maxn],f2[maxn];
char s1[maxn],s2[maxn];

int main(){
    scanf("%s%s",s1+1,s2+1);
    for(int i = 1;i <= strlen(s1+1);++i){
        f1[i] = f1[i-1] * base + s1[i] - 'a' + 1;
    }
    pw[0] = 1;
    for(int i = 1;i <= strlen(s1+1);++i){
        pw[i] = pw[i-1] * base;
    }
    for(int i = 1;i <= strlen(s2+1);++i){
        f2[i] = f2[i-1] * base + s2[i] - 'a' + 1;
    }
    int m;scanf("%d",&m);
    while(m--){
        int l1,r1,l2,r2;scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if((f1[r1] - f1[l1 - 1] * pw[r1 - l1 + 1]) == (f2[r2] - f2[l2 - 1] * pw[r1 - l1 + 1]))printf("YES\n");
        else printf("fake u**\n");
    }
    return 0;
}

哈希表

算法概况：

关于一个较大的值域 我们希望在较短的时间内完成查询操作 但是值域太大导致不能用计数数组 （你又懒得用离散化） 就可以用哈希表来处理了

例题导入

对于这样一个数列 {1,75,324,43,1353,91,40}
我们想要查询一个数字 可以选择开一个数组a[7] 然后将这几个数字都存进去
然后如果要查询的话 显然会是O(n) 的效率 如果加上各种奇淫巧技应该还可以再优化到\(log_n\)吧
但是我们也可以选择开一个数组a[1353] 然后将数值作为下标 数组保存出现几次
这样我们要查询某个数字出现次数就是O(1)的效率
显然我们的效率提高了很多 但是看看我们的空间 ……………………………………（泪目就完了）
所以这时我们哈希表闪亮登场

• 我们一开始将数值作为下标 很显然我们有很多地方是没有被用到的 比如a[2] a[3] 都是浪费的空间
• 那么我们可以选择让这个数值取上一个数的模 然后将这个新值作为数组下标
• 举个栗子: 我们这个题可以选择将7作为模数 取完模之后显然数值范围为0～6 而0很特殊 所以我们避免掉0的情况 让数值取模之后+1
• 这样我们的数值范围就变成了1～7 然后开始存数
• 1存进a[1],75存进a[5]，324存进a[2]，43存进a[1] 诶 a[1]存了俩值 vvvvvvvvv
• 所以显然这样出现了两个不同的数值x,y 但是会出现x ≡ y (mod p) 这就是我们常说的哈希冲突
• 如何处理冲突呢？ 我们选择不再将数组存数值 而是存一个链表（和最短路的基本一样 木得学过最短路的同鞋emmm 你想起啥来看哈希的）
• 所以我们的算法模板就有了

板子

背景 ：

• 你有一个序列（别问，问就是我给你的），里面有n个数，有m次查询，询问当前数在序列中出现了多少次
• 第一行输入两个整数n,m 表示有n个数 ，m次询问
• 第二行输入 n 个数字 表示这个序列中的数字
• 第三行输入 m 个数字 询问当前数字在序列中出现次数
• 请根据每次询问给出对应的答案

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
const int mod = 223;//模数

struct node{//邻接表
    int val,cnt,next;
}a[maxn];

int head[maxn],tot;

void add(int x){
    int now = x % mod + 1,u = head[now];//now为哈希操作之后对应的值 u表示链头
    for(;u;u = a[u].next)//遍历整个链表 
        if(a[u].val == x){//如果找到当前值
            a[u].cnt++;break;
        }
    if(!u){//如果链表遍历完仍然为找到对应的值
        a[++tot].val = x;//开个新点
        a[tot].cnt = 1;
        a[tot].next = head[now];
        head[now] = tot;
    }
}

int ask(int x){
    int now = x % mod + 1;
    for(int i = head[now];i;i = a[i].next)if(a[i].val == x)return a[i].cnt;//查找到了对应的值
    return 0;//没有查找到对应的值
}

int main(){
    int n,m;scanf("%d%d",&n,&m);
    while(n--){
        int x;scanf("%d",&x);
        add(x);
    }
    while(m--){
        int x;scanf("%d",&x);
        printf("%d\n",ask(x));
    }
    return 0;
}