哈希表与字符串哈希

哈希表是一种非常带劲的存储方法，它将一定个数内的数据以一种降低数据规模的方式存储着，哈希表的主要操作就是添加数据和查找数据，当然你也可以用标记来标记数据是否被删除（实际上，它只是被你标记删除了，并未被实际删除并释放内存）

上模板题让我们直观感受下：
Acwing840 模拟散列表：传送门：https://www.acwing.com/problem/content/842/

这题就让我们实现了哈希表的存储和查找：

比较好用的两种方法：拉链法和开放寻址法

1.拉链法

一个节点上存储着取模后位置相同的数据，由于存储位置相同，为避免矛盾，采用拉链法将其以拉链形式展开存储

首先创建存储位置的数组，这个数组的每个元素作为拉链的头结点，即每个元素都作为一个单链表的头结点，之后按照数据的模后存储位置存储单链表的数据即可

如图所示：

2. 开放寻址法

为了避免查找时的寻找次数过多，一般数组大小为题目所给数据范围的2~3倍，且数组大小尽量设置为质数减少冲突。

主要思路就是如果数据取模后的位置未被占用，那么就直接将该数据存储着该位置，如果已被占用，则往后寻找直至找到一个未被占用的位置。

这里直接上代码：

题目Acwing840 ：https://www.acwing.com/activity/content/code/content/45308/

#include<stdio.h>
#include<string.h>

const int null = 0x3f3f3f3f;
const int N = 200003; //开为题目数据范围的2倍

int h[N]; //存储的值


void init(){
    memset(h, 0x3f, sizeof(h));
}

//插入值和查找值只需一个函数
int find(int x){
    int k = ((x % N) + N) % N;
    while(h[k] != null && h[k] != x){ //当这个位置被占用了，且x未被存储
        k++;
        if(k == N) k = 0; //如果到了最后一个位置，就返回初位置再开始寻找
    }
    return k;
}

int main(){

    init();

    int n;
    scanf("%d", &n);

    while(n--){
        char op[2];
        int x;
        scanf("%s%d", op, &x);

        if(op[0] == 'I'){            
            int k = find(x);
            h[k] = x;
        }   
        
        else if(op[0] == 'Q'){
            if(h[find(x)] == null) puts("No"); 
            else puts("Yes");
        }
    }

    return 0;
}

字符串哈希

所谓字符串哈希，就是将一个字符串以哈希表的形式存储下来，由于哈希表近乎O(1)的时间复杂度，使得面对大部分问题时，都可以使用哈希表暴力卡过。

这里我们介绍的是字符串前缀哈希法

这里有一个字符串 “ABCD”，给你L1, R1, L2, R2让你求下LR范围内的字符串是否相同

那么我们用哈希可以怎么做呢？

s[] = "ABCD";

h[N]为哈希值

这里我们先预处理出所有前缀的哈希值：

h[i] 是指前i个字符的哈希值，这里定义h[0] = 0

如h[1] = "A"的哈希值， h[2] = "AB"的哈希值，h[3] = "ABCDA"的哈希值，以此类推

那么定义字符串的哈希值时将字符串定义为p进制的数，一般取p = 131或13331

A是第1位：p^0， B是第2位：p^1， C是第3位：p^2，D是第4位：p^3

那么这里h[1] = h[0] * p ^ 0 + 'A'， h[2] = h[1] ^ p + 'B'， h[3] = h[2] ^ p + 'C'， h[4] = h[3] * p + 'D'， h[5] = h[3] * p + 'A'

这里的'A'值也可以不用哈希值，可以使用1~26，但是一定要保证所有字符的相对位置是固定的，即A比B小1，A比C小2等。。

这时候就知道了整个字符串每个子串的哈希值了。所以当我们要求解某两部分是否相等时，就可以直接使用哈希值相减了。

但是需要注意的是：（我们这里定义1~26为'A'~'Z'的哈希值，为了简便计算，p为2）如"ABCDA"

h[1] = h[0] * p + 1 = 1;

h[2] = h[1] * p + 2 = 4;

h[3] = h[2] * p + 3 = 11;

h[4] = h[3] * p + 4 = 26;

h[5] = h[4] * p + 1 = 53;

求1~1到 5~5的两个子串是否相同

"ABCDA"

h[r] - h[l - 1] * p^(r - l + 1)就是这个子串的哈希值，你问我为什么，我说的是，以2~4的子串为例子

BCD这个子串是个3位的p进制数，而ABCD是4位p进制数，A是1位p进制数，因此：要想用ABCD处理A得到一个3位的p进制数BCD，由于A是子串ABCD的最高位第4位，因此我们拿ABCD减去A*p^3即可，通过观察可以发现，每个相减子串的位数相差的是他们最后一个字符之间的距离，即r - l + 1。所以有h[r] - h[l - 1] * p^(r - l + 1)是l~r这个子串的哈希值。

关于模板题：推荐Acwing 841 传送门：https://www.acwing.com/problem/content/843/