哈希表CSP-S

💡 核心思想

哈希表通过哈希函数将键映射到数组下标，实现 $O(1)$ 平均时间的插入、删除和查询。竞赛中常用 unordered_map 或手写哈希（开放寻址法/拉链法）。字符串哈希用于 $O(1)$ 比较字符串是否相等。

🎯 直觉理解

哈希表就像一个"超大的抽屉柜"，每个抽屉有一个编号。你通过一个函数把物品的名称转换成抽屉编号，然后放进去。找东西时也用同样的函数算出抽屉编号，直接打开找。如果两个人被分到同一个抽屉（哈希冲突），就在抽屉里逐个比对。

📝 算法流程

1. 选择哈希函数（字符串常用多项式哈希）
2. 处理冲突：拉链法或开放寻址法
3. 字符串哈希：预处理前缀哈希值，$O(1)$ 比较子串
4. 双哈希：用两个不同模数降低冲突概率

$$H(s) = \sum_{i=0}^{n-1} s[i] \cdot b^{n-1-i} \pmod{M}$$

$$\text{子串哈希：} H(s[l..r]) = H(s[1..r]) - H(s[1..l-1]) \cdot b^{r-l+1} \pmod{M}$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull BASE = 131;
ull h[1000005], pw[1000005];
ull getHash(int l, int r) { return h[r] - h[l-1] * pw[r-l+1]; }
int main() {
    string s; cin >> s; int n = s.size();
    pw[0] = 1; h[0] = 0;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i-1] * BASE + s[i-1];
        pw[i] = pw[i-1] * BASE;
    }
    int q; cin >> q;
    while (q--) {
        int l1,r1,l2,r2; cin >> l1 >> r1 >> l2 >> r2;
        cout << (getHash(l1,r1)==getHash(l2,r2)?"Yes":"No") << "\n";
    }
    return 0;
}

⚠️ 常见坑点

📚 相关题目