常数复杂度的查找——哈希表

哈希表/散列表

哈希函数

作用：把一个比较复杂的数据结构（特大整数、浮点数、字符串）映射到一个较固定的数据范围内，实现通过映射值(key)查找对应元素(value)

实现：一般情况下我们使用直接使用将键值模上一个较大的质数作为索引，也即取 $f_{(x) \ =\ x\ mod\ P}$ ，很显然我们这样的处理是很容易导致键值的冲突发生的，所以我们需要设计冲突处理解决相应的问题。

冲突处理

拉链法（开散列法）

实现：整个哈希表的每个节点都维护了一个链表每次都将映射到该节点的对应值添加到链表中，查找时需要遍历整个节点链表，如果加入的节点数为 $n$ 取模 $P$ （即索引范围为 $\left[ 0,P\right)$ ）这样插入和查找的期望复杂度就都是 $O_{\frac{n}{P}}$ 的（一般不做删除节点的操作，一般用标记代表删除）

核心代码：

const int N = 100003;

int h[N], e[N], ne[N], idx;

void insert_node(int x){
    int k = ((x%N)+N)%N;//避免x为负数导致k也为负值
    e[idx] = x, ne[idx] = h[k], h[k] = idx++;
}

bool find_node(int x){
    int k = ((x%N)+N)%N;
    for(int i = h[k]; ~i; i = ne[i]){
        if(e[i] == x) return true;
    }
    return false;
}

完整代码

#include<iostream>
#include<cstring>
using namespace std;

const int N = 100003;

int h[N], e[N], ne[N], idx;

void insert_node(int x){
    int k = ((x%N)+N)%N;//避免x为负数导致k也为负值
    e[idx] = x, ne[idx] = h[k], h[k] = idx++;
}

bool find_node(int x){
    int k = ((x%N)+N)%N;
    for(int i = h[k]; ~i; i = ne[i]){
        if(e[i] == x) return true;
    }
    return false;
}

int main(){
    int n;
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    
    while(n--){
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        
        if(op[0] == 'I') insert_node(x);
        else{
            if(find_node(x)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

开放寻址法（闭散列法）

实现（线性探查法）：整个哈希表就只有一个数组（数组的大小一般要在存储数据量的两到三倍这样的冲突较少）同样使用哈希函数得到映射值在对应的下标中查看是否已经插入了元素，如果已经插入了元素则退避至下一个位点依次类推（同样的标记删除法删除节点）。

核心函数：

int find_node(int x){
    int k = ((x%N)+N)%N;
    
    while(h[k] != null && h[k] != x){
        k++;
        if(k == N) k = 0;
    }
    return k;
}

find_node() 函数实现的是将返回查找到的元素位置或者元素可以插入当前元素的第一个空位， null 值代表约定的代表空值的常数

完整代码：

#include<iostream>
#include<cstring>
using namespace std;

const int N = 200003, null = 0x3f3f3f3f;

int h[N];

int find_node(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(){
    int n;
    scanf("%d", &n);
    memset(h, 0x3f, sizeof h);
    
    while(n--){
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        int k = find_node(x);
        
        if(op[0] == 'I') h[k] = x;
        else{
            if(h[k] != null) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

经验值：一般开大数组后查找的次数都小于3

字符串哈希

引入

前面讲的哈希函数可以认为是一种映射关系，将数据范围较大的数据降低通过哈希函数的方式映射到一个较小的值域内，然后通过映射值作为下标存储数据；

这里将要讲的字符串哈希是另一种思路：将字符串通过哈希函数映射成为一个整数，这样就可以通过整数的比较来对应相应字符串的比较；

不难发现，如果将如果忽略 char 所代表的字符意义将其看成一个完整的字节这样由4个 char 就可以构成一个 int 也就意味着这样的四个一组的单位可以与一个 int 值一一对应，也就达到了完美的映射关系，但是同时我们注意到 char 所代表的字符中只有一小部分是以可见字符的形式出现，这里假设题干给出字符串全由小写字母表示，这样就可以将每一个 char 位映射成为一个 26 进制数的形式，这样可以明显增大一个 int 所能完美映射字符串的长度，但是这样虽然能够实现完美映射的一一对应关系但是这样所能表示的范围还是远远不够（就算是使用64bit的无符号长整型也就只能映射19位这样的 char ）。

正文

这时候我们想到了通过哈希函数映射的方式将这样的字符串映射到一个固定的范围内以实现一个较长的字符串的能够与一个整数对应起来以实现通过与字符串对应的整数判等得到字符串的判等，而这里的一定范围我们为了降低冲突的概率必须尽可能地取大故我们一般取为无符号长整型所能表示的范围

这里我们可以总结出哈希函数的两个重要的性质：

Hash函数值不相同时，变量一定不同
Hash函数值相同时，变量不一定（可以做到大概率）相同

我们当然时希望Hash值相同时变量一定相同但是如果真是如此那么就不是将超过表达能力的大范围数映射到小范围了:joy:

冲突率的计算

假定我们用 $b$ 表示选择的进制数， $s[i]$ 把对应字符串的每个字符映射成为数字等到的数组的第 $i$ 个数， $P$ 表示需要映射到的数的范围，考虑哈希函数为

$f(s)\ =\ \sum_{i=1}^{l}s[i]\times b^{l-i}(mod\ P) $

这样我们来看如果两不同的字符串 s ,t 得到相同的Hash值的概率为多少

$0 = f(a) - f(b) = f(s)\ =\ \sum_{i=1}^{l}(s[i]-t[i])\times b^{l-i}(mod\ P)$

可以将这个式子看作 $l-1$ 阶的非零多项式（其中 $l = max(s.length(),\ t.length())$ )，故该式子最多有 $l-1$ 个根故发生冲突的概率约为 $\frac{l-1}{P}$ ,又 $M$ 取在无符号长整型范围内的数量级为 $10^{18}$ 故一般情况下发生冲突的概率都极其小，同时取无符号长整型还有个好处就是结果不会溢出即溢出自动丢弃（相当于不用取模）

经验值： $b$ 一般取 131 或 13331 得到的冲突比较少效果比较好。

注意： $s[i]$ 不能映射成数值0，因为对于一个被映射成0的字符来讲 $n$ 个这样的字符排成一列同样是0，这样就会明显产生不必要的冲突；例如，若字符a被映射成数字0，那么字符串aa 与 aaaa 得到的哈希值都是0（想象一下每个n个0排一列）

字符串的前缀哈希

实现：

利用前缀和的思想求得整个长字符串的前缀哈希值（利用上面的公式）
在求前缀和的时候顺便求得所有 $P$ 的所有次方项数值，保留备用
在需要求字符串中某个子串的哈希值时可以通过子串结尾（ $r$ ）与起始位置处前一位（ $l-1$ ）的哈希值即可得到，由于这两个位置处的权值是存在差距的所以需要将结尾处的哈希乘上 $P^{r-l+1}$ 得到，这里之前所用到的保留 $P$ 的次方项就其作用了

这里给出求位置为 $r$ 和位置为 $l-1$ 处的哈希值的计算公式方便大家理解

$\begin{align*} &f(r)\ =\ s[0]\times b^{r-1}\ + ... +\ s[l-1]\times b^{r-l+1}\ + \ s[l]\times b^{r-l}\ +\ ...+ s[r] \\\\ &f(l-1)\ =\ s[0]\times b^{l-2}\ + ... +\ s[l-1]\\ \end{align*}$

如果对次还有问题可以自行在草稿纸上演算一下加深印象。

核心代码：

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

char str[N];
ULL h[N], p[N];

void init(int n){
    p[0] = 1;
    for(int i = 1; i <= n; i++){
        p[i] = p[i-1]*P;
        h[i] = h[i-1]*P + str[i];
    }
}

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

完整代码：

#include<iostream>
using namespace std;

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

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(){
    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];
    }
    
    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;
}