哈希表CSP-S

💡 核心思想

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

🎯 直觉理解

哈希表是"把任意键快速映射到值"的容器：把键通过哈希函数算成一个下标，直接存进数组——插入、查找平均 $O(1)$。它像给每本书按书名首字母分类放好，找书直接去对应书架。

C++ 用 unordered_map，但竞赛里常常手写哈希：把字符串、大数模一个大质数（如 $10^9+7$）变成整数，用数组存储，冲突用链表或开放寻址解决。

风险：哈希冲突与被卡（构造数据让所有键映射到同一位置）——所以模数选大质数，必要时双哈希。哈希 = 用空间换时间 + 概率上的安全。

📝 算法流程

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 
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;
}

⚠️ 常见坑点

📚 相关题目