数据结构（三）哈希表 STL使用技巧

//1.看一下题目当中的哪儿些操作可以进行优化 操作有什么特点
//2.寻找一堆数里的最小值 或者最大值的时候用堆来做
//3.当想维护一个有序链表的时候就要用平衡树就是set来做
//4.当想维护区间最大值、区间和可能就要用树状数组或者线段树来做
//5.并查集的题目可能不是很好看出来 不是很直观 所以需要多练题


哈希表
1.存储结构
输入 h(x)
输出 (0, 10^5)
//支持两种操作
1.插入一个数x 数的范围是（-10^9,10^9）
2.询问数x在集合中是否出现过
//一个函数h(x)将（-10^9,10^9）的数映射到(0, 10^5)之间的数
//这个函数称为哈希函数

如何映射？
1.x % 10^5
2.冲突 即很有可能两个数映射到同一个数
//h(5) = 2 h(10) = 2

//所以需要处理冲突
//两种处理冲突的方式
    1)开放寻址法
    2)拉链法
2.常用字符串哈希方式

//离散化 是一种极其特殊的hash方式 需要保序即单调递增




拉链法
开一个一维数组 存储所有的哈希值
在一维数组下拉个链
在算法题中一般只有添加和查找两个操作 一般不会有删除操作
如果在算法题中要实现删除操作 即在链上打上一个bool变量 标记一下即删除

一般来说做hash的时候 数组长度也就是 % 的数一般来说要取质数 并且离2的整次幂尽可能的远
//因为这么取冲突的概率是最小的






字符串哈希
当要快速判断两个字符串是否相等的时候就可以用这个做法
//不能映射成0 A = 0 AA = 0
//Rp足够好，不存在冲突 即 P = 131 或 13331 Q = 2 ^ 64 99%是不会发生冲突的

#include <iostream>
using namespace std;

typedef unsigned long long ULL;

const int N = 1e5 + 10, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];
//因为要 % 2的64次方所以可以直接用unsigned long long 直接溢出

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

int main(){
    scanf("%d%d%s", &n, &m, str + 1);
    
    p[0] = 1;
    for(int i = 1; i <= n; i++){
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];//str[i]只要保证不是0就可以，是多少都可以
    }
    
    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;
}
数据结构（二）

码
