哈希表

何为哈希表

散列表又称 哈希表，是一种以 key:value 形式存储数据的数据结构。所谓 key:value 就是 键值对，这种数据结构有一个很大的优势：给定一个 key 它能够在 $O(1)$ 的时间把对应的 value 找出来。

为了达到这种效果，哈希表使用到了一种特殊的函数 哈希函数 也称 散列函数。$hash(key)$ 存储着 key:value 在内存中的地址或是索引。

哈希碰撞

如果对于任意的键值，哈希函数计算出来的索引都不相同，那只用根据索引把 key:value 放到对应的位置就行了。但实际上，常常会出现两个不同的键值，他们用哈希函数计算出来的索引是相同的，这就被称为 哈希碰撞。这时候就需要一些方法来处理冲突。在 OI 中，最常用的方法是 拉链法 和 开放寻址法。

示例题目

维护一个集合，支持如下几种操作：

1. I x，插入一个整数 $x$；
2. Q x，询问整数 $x$ 是否在集合中出现过；

现在要进行 $N$ 次操作，对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 $N$，表示操作数量。接下来 $N$ 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。

输出格式

对于每个询问指令 Q x，输出一个询问结果，如果 $x$ 在集合中出现过，则输出 Yes，否则输出 No。每个结果占一行。

数据范围

$1\le N\le {10}^5$，$-{10}^9\le x\le {10}^9$

输入样例

5
I 1
I 2
I 3
Q 2
Q 5

输出样例

Yes
No

拉链法

#include <bits/stdc++.h>

using namespace std;

const int N = 100003;
int h[N], e[N], ne[N], idx;

// 哈希函数
int mhash(int x) {
    return (x % N + N) % N;
}

void insert(int x) {
    int k = mhash(x);
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

bool find(int x) {
    int k = mhash(x);
    for (int i = h[k]; i != -1; i = ne[i]) {
        if (e[i] == x) return true;
    }

    return false;
}

int main() {
    int n; cin >> n;

    memset(h, -1, sizeof h);

    while (n --) {
        char op[2];
        int x;

        scanf("%s%d", op, &x);

        if (op[0] == 'I') {
            insert(x);
        } else {
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

开放寻址法

#include <bits/stdc++.h>

using namespace std;

const int N = 200003, INF = 0x3f3f3f3f; // INF 表示该位置没有值
int h[N];

// 哈希函数
int mhash(int x) {
    return (x % N + N) % N;
}

int find(int x) { // 如果能找到 x 则返回 x 的索引，否则返回 x 应该存储的位置
    int k = mhash(x);

    while (h[k] != INF && h[k] != x) { // 该位置有值且值不是 x
        k++;
        if (k == N) k = 0;
    }

    return k;
}

int main() {
    int n; cin >> n;

    memset(h, 0x3f, sizeof h); // 初始化所有位置为空

    while (n --) {
        char op[2];
        int x;

        scanf("%s%d", op, &x);

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

    return 0;
}

字符串哈希

如果 key 是字符串，由于不支持以字符串作为数组下标，并且将字符串转化成数字存储也可以避免多次进行字符串比较。所以在 OI 中，一般不直接把字符串作为键值，而是先算出字符串的哈希值，再把其哈希值作为键值插入到哈希表里。关于字符串的哈希值，我们一般采用进制的思想，将字符串想象成一个 $P$ 进制的数（一般取 $131$）。那么，对于每一个长度为 $n$ 的字符串 $s$，就有：

$x=s_0\cdot P^0+s_1\cdot P^1+s_2\cdot P^2+\cdots +s_n\cdot P^n$

我们可以将得到的 $x$ 对 $2^{64}$（即 unsigned long long 的最大值）取模。通常的做法是将 $x$ 的类型设为 unsigned long long，这样 unsigned long long 的自然溢出就等价于取模操作了。可以使操作更加方便。

这种方法虽然简单，但并不是完美的。可以构造数据使这种方法发生冲突（即两个字符串的 $x$ 对 $2^{64}$ 取模后的结果相同）。 我们可以使用双哈希的方法：选取两个大质数 $a,b$。当且仅当两个字符串的哈希值对 $a$ 和对 $b$ 取模都相等时，我们才认为这两个字符串相等。这样可以大大降低哈希冲突的概率。

实际应用

字符串前缀哈希

设有字符串 $s$ 哈希函数 $h(x)$ 表示字符串 $s$ 的子串 $[1,x]$ 的哈希值，且特殊定义 $h(0)=0$

$h(x)=(s_1\cdot P^{x-1}+s_2\cdot P^{x-2}+s_3\cdot P^{x-3}+\cdots +s_{x-1}\cdot P^1+s_x\cdot P^0)\mathrm{mod}Q$；($P=131Q=2^{64}$)

针对上述哈希函数有两点特殊说明：

1. $s_i!=0$
2. 不存在冲突

两个操作：

• 预处理字符串：$h(i)=h(i-1)\ast p+s_i$
• 计算任意子串 $[l,r]$ 的哈希值：$h(l\sim r)=h(r)-h(l-1)\ast P^{r-l+1}$

示例题目

给定一个长度为 $n$ 的字符串，再给定 $m$ 个询问，每个询问包含四个整数 $l_1,r_1,l_2,r_2$，请你判断 $[l_1,r_1]$ 和 $[l_2,r_2]$ 这两个区间所包含的字符串子串是否完全相同。字符串中只包含大小写英文字母和数字。

输入格式

第一行包含整数 $n$ 和 $m$，表示字符串长度和询问次数。第二行包含一个长度为 $n$ 的字符串，字符串中只包含大小写英文字母和数字。接下来 $m$ 行，每行包含四个整数 $l_1,r_1,l_2,r_2$，表示一次询问所涉及的两个区间。

注意，字符串的位置从 $1$ 开始编号。

输出格式

对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。每个结果占一行。

数据范围

$1\le n,m\le {10}^5$

输入样例

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输出样例

Yes
No
Yes

参考代码

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ULL;

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

char s[N];
ULL h[N], p[N];
int n, m;

// 求区间 [l, r] 的哈希值
ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    scanf("%d%d%s", &n, &m, s + 1);

    // 预处理 p^i 以及 h[i]
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + s[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;
}

习题

• 洛谷 P4305. 不重复数字

离散化

AcWing 804 区间和

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。现在，我们首先进行 $n$ 次操作，每次操作将某一位置 $x$ 上的数加 $c$。接下来，进行 $m$ 次询问，每个询问包含两个整数 $l$ 和 $r$，你需要求出在区间 $[l,r]$ 之间的所有数的和。

输入格式

第一行包含两个整数 $n$ 和 $m$。接下来 $n$ 行，每行包含两个整数 $x$ 和 $c$。再接下来 $m$ 行，每行包含两个整数 $l$ 和 $r$。

输出格式

共 $m$ 行，每行输出一个询问中所求的区间内数字和。

数据范围

$-{10}^9\le x\le {10}^9$，$1\le n,m\le {10}^5$，$-{10}^9\le l\le r\le {10}^9$，$-10000\le c\le 10000$

输入样例

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例

8
0
5

参考代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int const N = 3e5 + 10;
int n, m, a[N], s[N];

typedef pair<int, int> PT;

vector<int> alls;
vector<PT> add, query;

// 二分查找
int find(int x) {
    int l = 0, r = alls.size() - 1;

    while(l < r) {
        int mid = l + r >> 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }

    return r + 1;
}

int main() {
    cin >> n >> m;

    // 输入所有的 x c
    for(int i = 0; i < n; i++) {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x);
    }

    for(int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }

    // 去除重复的下标
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    // 处理
    for(auto item : add) {
        int x = find(item.first);
        a[x] += item.second;
    }

    // 预处理前缀和
    for(int i = 1; i <= alls.size(); i++) {
        s[i] = s[i - 1] + a[i];
    }

    for(auto item : query) {
        int l = find(item.first);
        int r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}