信竞学习笔记 - 哈希与哈希表

Tiger

发表于 2026-02-28

更新于 2026-04-01

学习笔记

40 2.7~3.5 分钟 1215

1. 哈希

在比较两个字符串时，我们当然可以按字典序逐个比较。然而，当我们想得知两个字符串开始时，除了直接比较，我们还可以将字符串通过一个函数转换成与之一一对应的一串数据（无符号长整型），比较这两组数据来得知两字符串是否相等。这个函数就是哈希函数。

1.1. 哈希的概念和计算

哈希（Hash），又称散列。哈希函数将任意长度的输入转换为固定长度的输出。这个输出就叫做哈希值。以字符串转哈希值的变换为例：具体的说，哈希函数有两个参数 $BASE$ 和 $p$ 。哈希函数将字符串的每一位视作一个 $BASE$ 进制数的每一位，然后在此基础上对 $p$ 取余得到结果。模数 $p$ 越大，不同字符串的哈希值重叠的可能性越小。在数据能够存储下的情况下，部分时候也可以选择不进行取余操作。

一般哈希值都是用十六进制进行表示的，例如文件的 SHA-256 值。

1.2. 哈希函数的代码实现

下面给出了一个简单的不带模数的哈希函数的代码实现：

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

typedef unsigned long long ULL;

// 定义 BASE、h 数组、p 数组
const int BASE = 131, N = 1e6 + 100;
ULL h[N], p[N];

void calc(string s) {
    for (int i=1; i<s.size(); i++) {
        // 哈希值每位应该从 1 开始，不能有 0 出现
        h[i] = h[i-1] * B + (s[i] - 64);
    }
}

int main() {
    
    // 初始化 BASE 的 k 次幂数组
    p[0] = 1;
    for (int i=1; i<s.size(); i++) {
        p[i] = p[i-1] * BASE;
    }
    
    string s;
    
    cin >> s;
    
    calc(s);

}

1.3. 取子串哈希值

哈希值是一种递推计算。要取其中某一段的数值，我们可以将其类比前缀和来寻找规律。假设一个字符串，对其取十进制哈希，不模，前 4 位的哈希值为 123456，前 6 位的哈希值为 1234，那么它第 5~6 位的哈希值就是 56。注意到了吗：

123456 - 1234 * 10^2 = 56

而 2 正是第 5~6 位所占位数。如此，基于 1.2 节的代码，我们可以写出如下求 $[l, r]$ 区间内子串哈希值的函数：

ULL get(int l, int r) {
    return h[r] - h[l-1] * p[r-l+1]; // p[r-l+1] 是 BASE 的 r-l+1 次幂
}

2. 哈希表

我们知道，数组的读写时间复杂度为 $O(1)$ ，但插入和删除的时间复杂度为 $O(N)$ ；而链表插入和删除的时间复杂度为 $O(1)$ ，读写的时间复杂度为 $O(N)$ 。有没有读写和插入删除效率都高的数据结构呢？有，它就是哈希表。

2.1. 哈希表的概念和原理

哈希表（Hash Map），又称散列表，是一种读写和插入删除平均效率均为 $O(1)$ ，但空间效率略低的数据结构。以整数哈希表为例，在构建哈希表的过程中，我们取一个模数，通常是比数据规模稍大的一个质数，例如 $10^5+3$ 和 $10^7 + 19$ 。对于每个整数，将其对所取的模数取模，得到一个结果，就是该数的下标。

2.2. 哈希冲突

在上面的计算过程中，可能会出现一个问题，就是不同的数对模数取余后放到的相同位置上，冲突了。这种情况叫做哈希冲突。哈希冲突通常有两种解决方式——拉链法和开放寻址法。

拉链法将原本一维的哈希表提升至二维，即每个下标都可以存储多个数据。需要时在这些数据中查找。开放寻址法是将冲突的位置顺延向后遇空就放，先到先得。

2.3. 哈希表的代码实现

下面给出使用数组模拟哈希表的一种代码实现，该哈希表实现了插入元素和查找元素是否存在，使用了拉链法：

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

const int N = 1e5 + 10, M = 1e5 + 10, P = 1e5 + 3;

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

int n;

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

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

int main() {
    
    memset(h, -1, sizeof(h));
    
    cin >> n;
    
    while (n--) {
        char op;
        int x;
        cin >> op >> x;
        if (op == 'I') insert(x);
        else {
            if (find(x)) cout << "Yes\n";
            else cout << "No\n";
        }
    }
    
}

2.4. 相关 STL 库

在 C++ STL 库中，unordered_set 和 unordered_map 两个数据结构是基于哈希表实现的。