Hash表

7.Hash表

哈希表的作用：把一个比较大的空间，通过一个函数映射到一个比较小的空间。

一般做哈希运算时，取一个质数作为模，会使得冲突的概率降低

哈希表的冲突解决方法：

拉链法
开放寻址法

AcWing 840.模拟散列表

（1）拉链法

创建一个数组h，插入一个值时通过哈希函数映射到数组对应位置，每个位置维护一个链表，映射到相同位置值加入当前链表中。

数组h[i]类似于链表的头指针，存储的是其下链表的第一个结点x的数组下标，而不是结点的值x，取值范围0~N，所以可以让数组h的默认值为-1，以此判断该位置下是否为空

插入操作：采用头插法，根据哈希函数计算哈希值，每次冲突的值，插入到链表的第一个位置
查询操作：根据哈希值找到对应头指针即对应链表，再对链表遍历判断。
删除操作：删除操作并不是真正的删除该元素，而是设置一个标记值，来表示该位置的值已被删除（用得少）

哈希函数常用取余法，在本题中找一个大于或等于N且最小的质数

//求大于或等于N且最小的质数(N>1)
int get_prime(int N){
    for(int i=N;;i++){
        bool flag=true;
        for(int j=2;j*j<=2;j++)//在判断一个数是否为质数时，只需要检查其是否能被小于或等于其平方根的数整除。这是因为，如果一个数 n 能被一个比它大的数整除，那么这个因数必然有一个对应的比它小的因数。
            if(i%j==0) {
                flag=false;
                break;
            }
        
        if(flag){
            return i;
        }
    }
}

代码实现：

#include <iostream>
#include <cstring>
using namespace std;
const int N=100003;//大于10^5的最小质数为
int h[N],e[N],ne[N],idx=0;
 
//拉链法：插入操作 采用头插法
void insert(int x){
    int k=(x%N+N)%N;//求哈希值，+N再%N使负数求余为正数
    e[idx]=x;
    ne[idx]=h[k];
    h[k]=idx++;
}
 
//查找操作
bool query(int x){
    int k=(x%N+N)%N;//使负数求余也为正数
    for(int i=h[k];i!=-1;i=ne[i]){//i=-1时结束循环，即空指针
        if(e[idx]==x) return true;
    }
	return false;
}
 
int main() {
    memset(h,-1, sizeof(h));//令数组h初始化值为-1
    int n;
    cin>>n;
    while(n--)
    {
        char op[2];
        int x;
        cin>>op>>x;
        if(op[0] == 'I') insert(x);
        else{
            if(query(x)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

（2）开放寻址法

开放寻址法：当冲突发生时，使用某种探测算法（得出一个偏移量）在散列表中寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。探测法有线性探测法、平方探测法、双散列法、伪随机序列。这里直接使用线性探测法，即冲突则自增1

数组h存储的是具体结点值x，而x取值范围是-10^9~10^9，故应让数组h的默认值不在x的取值范围中，这样才好判断h[k]位置上是否为空（注意和拉链法区分）

查找和查询操作合为一个find函数：首先根据哈希函数计算的哈希值查找当前元素是否在初始映射位置。若该位置为空，则在这个位置插入该元素；若不为空且与该元素不等，则向后继续查找，直到找到该元素或者有空位置则插入该元素。最后返回该位置

#include <iostream>
#include <cstring>
using namespace std;
//将大范围数字映射到小范围数字（10^5）首先将x通过哈希函数映射到哈希表h[x]中。（ps:该方法的哈希表范围要扩大至正常的2到3倍） 
const int N= 200003,null=0x3f3f3f3f;//null超出10^9
int h[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() {
    memset(h,0x3f, sizeof h);//memset按字节赋值，int4个字节，每个字节赋值0x3f，则h默认值就为0x3f3f3f3f 即null
    int n;
    cin>>n;
    while(n--)
    {
        char op[2];
        int x;
        cin>>op>>x;
        int k=find(x);
        if(op[0] == 'I') h[k]=x;
        else{
            if(h[k]!=null) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

（3）字符串哈希

可以求解任意的子串的哈希值！这是KMP也望而却步的！。可以通过字符串哈希值，快速判断两个字符串是否相等或者两个字符串中某个部分是否相等。（用模式匹配需要至少O(n)，而字符串哈希只需要O(1)）

1.字符串哈希值：实际为字符串前缀哈希值，如有字符串 s = ABCDE，用数组h[]存储其各个前缀哈希值，则h[1] = A 的哈希值；h[2] = AB 的哈希值；h[3] = ABC 的哈希值…

2.如何求解一个字符串的哈希值？

将字符串看成一个P进制的数，比如字符串ABCD，假如我们把A映射为1，B映射为2，C映射为3，D映射为4（实际上字母也直接取它的ASCII值也可）。将ABCD这个P进制的数转化为十进制即为其哈希值，则ABCD这个字符串的哈希值为：(1 × P^3 + 2 × P^2+ 3 × P^1 + 4 × P^0 )mod Q

最后modQ即防止转化的十进制数过大，用Q来缩小数据范围，就是哈希散列的意义

**注意：**通常不要把一个字母映射为0，这样会导致重复。比如把A映射为0，则A是0，AA也是0，AAA还是0。

对于P、Q的取值，有一个经验值，将冲突概率降到极低。我们可以取 P = 131或13331，Q = 2^64 。为简化mod Q运算，可以将h数组的类型取成unsigned long long（64位），这样就无需对2^64 取模，溢出就直接相当于取模

**可得一个递推公式，求解某个字符串s[]的（前缀）哈希值：即h[i]=h[i-1]*P+s[i]（类似求前缀和，只是这里每次要乘一个P）**注意：i从1开始；字符串是顺序存储在数组中，低位字符的权值大

3.求解一个字符串某区间[l,r]上的字符串哈希值

这就和前缀和有所区别，不是单纯的h[r]-h[l-1]。因为字符串是顺序存储在数组中，低位字符的权值大，区间1~~l-1的字符串在相减过程中后面应该补0，即抬高各字符的权值，达到与1~~r区间的字符串位数相等，有同等地位。如1~~l-1是“ABC”，而1~~r是“ABCDE”，求DE的哈希值，就应该让“哈希值（ABCDE）-哈希值（ABC00）”

即体现到公式上，先算出两者相差的位数：r-l+1，然后h[l-1]*P^(r-l+1)，再相减得[l,r]区间字符串的哈希值=h[r]-h[l-1]*P^(r-l+1)

注：为了简便的得到P^i的值，用一个数组来存储，即p[i]=P^i

4.由以上步骤，即可通过哈希值来判断任意两个字符串是否相等

AcWing 841.字符串哈希

#include <iostream>
#include <string>
using namespace std;
typedef unsigned Long Long ULL;//无符号的Long long数(64位)，不用再额外mod Q 
const int N=1e5+10,p=131;
int n,m;
int h[N],P[N];//h：哈希值。P：进制权值
char str[N];
 
//得到某个区间字符串的哈希值
ULL get(int l,int r){
    return h[r]-h[l-1]*P[r-l+1];
}
 
int main(){
    cin>>n>>m>>str+1;//字符数组从1开始存储
    P[0]=1;
    for(int i=1;i<=n;i++){
        //计算P
        P[i]=P[i-1]*p;
        //计算前缀哈希值
        h[i]=h[i-1]*p+str[i];//这里字符直接用其ASCII值
    }
    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;
}

编程笔记

探索