# 哈希表与字符串哈希（Hash Table & String Hashing）

哈希表是计算机科学中最基础、最重要的数据结构之一。它通过一个指定的哈希函数，将任意键（Key）直接映射到数组的存储位置（桶，Bucket）中，从而在平均情况下实现 $O(1)$ 时间复杂度的查找、插入和删除操作。

---

## 1. 数组 + 哈希函数：基本存储逻辑

### 1.1 直观理解：快递储物柜模型
假设你正在管理一个拥有 10,000 个储物柜的大型快递站：
* **传统思路**：将所有包裹随意堆在一起。寻找某个特定客户的包裹时，工作人员必须依次遍历翻找所有包裹，最坏情况下时间复杂度为 $O(N)$。
* **哈希表思路**：制定一个固定规则（**哈希函数**），根据收件人姓名直接计算出一个柜子编号。
  * 收件人 “张三” $\to$ 计算得出 8 号柜。直接放进 8 号柜。
  * 收件人 “李四” $\to$ 计算得出 3 号柜。直接放进 3 号柜。
  当客户“张三”来取件时，系统只需再次输入“张三”，通过哈希规则瞬间计算出柜子编号 8，工作人员直接开柜取件。这一步充分利用了静态数组 $O(1)$ 的随机访问性能。

---

### 1.2 数值场景：大整数的高效查找
假设需要存储约 100 个范围极大（如可达 $10^9$）的整数，例如集合 $\{1022384, 2392743, 2904892, 9348920, 25390, 2835301, \dots\}$，并要求极快地判断某个数是否存在。

* **哈希解决方案（简单取模法）**：
  定义哈希函数：
  $$\text{Hash}(key) = key \bmod 100$$
  该函数将任意大整数映射到 $0 \sim 99$ 的范围内，我们准备一个长度为 100 的数组。
  * $1022384 \to 1022384 \bmod 100 = 84$（存放在 84 号桶）
  * $2392743 \to 2392743 \bmod 100 = 43$（存放在 43 号桶）
  * $2904892 \to 2904892 \bmod 100 = 92$（存放在 92 号桶）

#### 桶存储分布示意（长度为 100 的数组）：
| 桶索引 (Index) | 存储的数值 (Stored Keys) |
| :---: | :---: |
| `0` | 空 (Empty) |
| `1` | `2835301` |
| `2 ~ 19` | ... |
| `20` | `9348920` |
| `21 ~ 42` | ... |
| `43` | `2392743` |
| `44 ~ 83` | ... |
| `84` | `1022384` |
| `85 ~ 89` | ... |
| `90` | `25390` |
| `91` | 空 (Empty) |
| `92` | `2904892` |
| `93 ~ 99` | ... |

当查找大整数 $1022384$ 时，直接计算 $\text{Hash}(1022384) = 84$，直接定位至 84 号桶，只需 $O(1)$ 时间即可确认。

---

## 2. 哈希冲突（Collision）及其解决方法

两个不同的 Key 经过同一个哈希函数可能会算出相同的映射地址。尤其是由于取模的值域被严重缩减，**哈希冲突**在所难免。常用的冲突解决方法有两种：

### 2.1 拉链法（Separate Chaining）
每个桶不再直接存放一个数值，而是挂载一个单链表。当发生冲突时，将相同哈希值的元素直接追加到该桶对应的链表末尾：
$$2835301 \to 7864201 \to 4512401 \to \dots$$
* C++ 中的 `std::unordered_map` 和 Python 的 `dict` 底层正是使用了拉链法。当链表长度超过特定阈值（如负载因子过大）时，底层通常会将长链表自动升级为**红黑树**，以确保最坏情况下的查询性能。

---

### 2.2 开放寻址法（Open Addressing）
如果不使用链表，当位置被占领时，就去寻找下一个空闲的桶。
* **线性探测法**：若 1 号位置被占，则看 2 号；2 号被占则看 3 号……直到找到空位。
* **双哈希法（Double Hashing）**：线性探测容易造成数据在某些连续区间“聚集（Clustering）”。双哈希法的核心是让冲突后的“下一次跳跃步长”不固定，而是根据当前 Key 再次进行哈希运算来决定。它引入两个哈希函数：
  * $\text{Hash}\_1(key)$：决定初始存放的基准位置。
  * $\text{Hash}\_2(key)$：决定发生冲突时，每次向后跳跃的步长。
  $$\text{Index} = \left(\text{Hash}\_1(key) + i \times \text{Hash}\_2(key)\right) \bmod M$$
  *其中 $i$ 为冲突次数（$0, 1, 2, \dots$），$M$ 为哈希表的物理长度。*

> 💡 **设计细节**：为了保证双哈希法能遍历完哈希表中的每个位置，$\text{Hash}\_2(key)$ 算出的步长绝对不能为 $0$，且**步长必须与哈希表长度 $M$ 互质**。因此，工程上通常将 $M$ 取为质数，而 $\text{Hash}\_2(key)$ 的计算结果范围限制在 $[1, M-1]$ 之间。

---

## 3. 字符串哈希 (String Hashing)

对于一个长度为 $L$ 的字符串，如果我们想快速进行相等比较或子串查找，常规的比对时间复杂度为 $O(L)$。字符串哈希技术可以将任意长度的字符串映射为一个固定大小的整数（哈希指纹），从而将长字符串的比对开销优化至 **$O(1)$**。

### 3.1 多项式滚动哈希 (Polynomial Rolling Hash)
对于一个长度为 $n$ 的字符串 $S = s\_0s\_1\dots s\_{n-1}$（字符映射为非负整数值），我们可以将其视作一个 $p$ 进制的数（$p$ 被称为基数 Base）。
多项式哈希值 $H(S)$ 定义为：
$$H(S) = \left( \sum\_{i=0}^{n-1} s\_i \cdot p^i \right) \bmod M$$
*其中 $M$ 为用于防止整型溢出而精心挑选的大质数模数。*

直观上，这类似于十进制。例如数字 `138` 可以表达为 $8 \cdot 10^0 + 3 \cdot 10^1 + 1 \cdot 10^2$。

在多项式定义中，我们也可以颠倒基数的幂次顺序，以下定义在后续计算前缀哈希和子串哈希时最为自然（即 $s\_0$ 乘以最高次幂）：
$$H(S) = \left( s\_0 \cdot p^{n-1} + s\_1 \cdot p^{n-2} + \dots + s\_{n-1} \cdot p^0 \right) \bmod M$$

---

### 3.2 基数与模数的合理选择
* **基数 $p$**：
  * $p$ 必须**严格大于字符集的大小**。若处理 26 个小写英文字母，$p$ 至少为 27。一般在竞赛中选择质数，如 `31`、`131`、`13331`。这能确保哈希值分布更加均匀。
* **模数 $M$**：
  * $M$ 必须是一个足够大的质数（如 $10^9+7$ 或 $10^9+9$）。
  * 另一种选择是选用大小为 $2^{64}$ 的自然溢出（在 C++ 中使用 `unsigned long long` 自动产生溢出，免去取模运算，效率高，但有极小概率被专门的数据卡掉）。

---

### 3.3 前缀哈希与递推计算
类似于一维前缀和，我们预处理出字符串 $S$ 每一个前缀的哈希值。
设 $h[i]$ 为前缀 $S[0 \dots i-1]$（长度为 $i$）的哈希值。我们能推导出非常简洁的递推关系：
$$h[0] = 0$$
$$h[i] = (h[i-1] \cdot p + s\_{i-1}) \bmod M$$

这个递推式的计算方式与**秦九韶算法（Horner's method）**完全一致，每次迭代只需 $1$ 次乘法和 $1$ 次加法，能在 $O(N)$ 时间内高效预处理完毕。
在预处理的同时，我们也需要预先计算出 $p$ 的幂次数组：$pw[i] = p^i \bmod M$。

---

### 3.4 $O(1)$ 提取子串哈希值
有了前缀哈希 $h$ 数组和幂数组 $pw$，我们可以在 $O(1)$ 时间内查询任意子串 $S[l \dots r]$（0-based 索引）的哈希值。
子串 $S[l \dots r]$ 为 $s\_l s\_{l+1} \dots s\_r$。其对应的哈希值为：
$$H(S[l \dots r]) = (s\_l \cdot p^{r-l} + s\_{l+1} \cdot p^{r-l-1} + \dots + s\_r \cdot p^0) \bmod M$$

观察前缀哈希 $h[r+1]$（代表 $S[0 \dots r]$）与前缀哈希 $h[l]$（代表 $S[0 \dots l-1]$）：
$$h[r+1] = (s\_0 p^r + \dots + s\_{l-1} p^{r-l+1}) + (s\_l p^{r-l} + \dots + s\_r p^0) \bmod M$$
$$h[r+1] = \left( h[l] \cdot p^{r-l+1} + H(S[l \dots r]) \right) \bmod M$$

移项整理后，我们得到核心计算子串哈希公式：
$$H(S[l \dots r]) = \left( h[r+1] - h[l] \cdot p^{r-l+1} \right) \bmod M$$

为了防范模运算下出现减法负数，C++ 实现中应采用如下安全写法：
$$H(S[l \dots r]) = \left( \left( h[r+1] - h[l] \cdot pw[r-l+1] \bmod M \right) + M \right) \bmod M$$

---

### 3.5 经典单哈希实现模板（C++）
```cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int N = 1000005;
const int P = 131;       // 常用基数 Base
const int M = 1e9 + 7;   // 常用大质数模数 Modulo

string s;
long long h[N];          // 前缀哈希数组
long long pw[N];         // P 幂数组

// 预处理
void init(int n) {
    pw[0] = 1;
    for (int i = 1; i <= n; ++i) {
        pw[i] = pw[i - 1] * P % M;
        h[i] = (h[i - 1] * P + s[i - 1]) % M; // 字符串 0-indexed
    }
}

// O(1) 获取子串 S[l..r] 的哈希值 (0-indexed)
long long get_hash(int l, int r) {
    int len = r - l + 1;
    long long res = (h[r + 1] - h[l] * pw[len] % M + M) % M;
    return res;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    s = "abcdefg";
    int n = s.length();
    init(n);
    cout << "Substring [1..3] (bcd) hash: " << get_hash(1, 3) << endl;
    return 0;
}
```

---

### 3.6 安全双哈希（Dual Hashing）实现模板
单哈希可能存在人为构造的“哈希冲突碰撞攻击”。在关键竞赛或严苛数据环境下，最稳妥、最安全的方案是使用**双哈希**（即计算两个不同基数与模数的哈希对 $(h\_1, h\_2)$ 作为字符串的唯一指纹签名）。
* **碰撞率**：若单哈希碰撞率为 $\frac{1}{M\_1}$，则双哈希碰撞率可骤降到 $\frac{1}{M\_1 \cdot M\_2}$。若两模数都在 $10^9$ 级别，碰撞率低至 $10^{-18}$，在可承受的数据规模下碰撞的概率完全可以忽略不计。

```cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int N = 1000005;

struct HashPair {
    long long h1, h2;
    HashPair(long long a = 0, long long b = 0) : h1(a), h2(b) {}
    bool operator==(const HashPair& o) const {
        return h1 == o.h1 && h2 == o.h2;
    }
};

const long long P1 = 131, M1 = 1e9 + 7;
const long long P2 = 13331, M2 = 998244353;

string s;
HashPair h[N];  // 双哈希前缀数组
HashPair pw[N]; // 幂数组

void init(int n) {
    pw[0] = HashPair(1, 1);
    for (int i = 1; i <= n; ++i) {
        pw[i].h1 = pw[i - 1].h1 * P1 % M1;
        pw[i].h2 = pw[i - 1].h2 * P2 % M2;
    }
    for (int i = 1; i <= n; ++i) {
        h[i].h1 = (h[i - 1].h1 * P1 + s[i - 1]) % M1;
        h[i].h2 = (h[i - 1].h2 * P2 + s[i - 1]) % M2;
    }
}

HashPair get_hash(int l, int r) {
    int len = r - l + 1;
    long long r1 = (h[r + 1].h1 - h[l].h1 * pw[len].h1 % M1 + M1) % M1;
    long long r2 = (h[r + 1].h2 - h[l].h2 * pw[len].h2 % M2 + M2) % M2;
    return HashPair(r1, r2);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    s = "dualhashing";
    init(s.length());
    HashPair res = get_hash(0, 3);
    cout << "HashPair [0..3]: (" << res.h1 << ", " << res.h2 << ")\n";
    return 0;
}
```

---

## 4. 字符串哈希基础应用：不同字符串去重计数

### 4.1 问题场景（洛谷 P3370 【模板】字符串哈希）
给定 $N$ 个仅包含字母与数字的字符串 $S\_1, S\_2, \dots, S\_N$，求其中有多少个本质不同的字符串。
* **数据范围**：$N \le 10000$，串长 $M \le 1500$。

### 4.2 题解分析
如果直接使用 `std::set<string>` 进行存储比对去重，由于每次字符串插入的比较开销为 $O(M)$，最坏情况下总时间复杂度为 $O(N \cdot M \log N)$，在大规模数据下容易产生超时。

采用字符串哈希，我们将每个字符串直接映射到一个 `unsigned long long`（利用 $2^{64}$ 自然溢出机制防碰撞），直接比较整数。复杂度优化为 $O(\sum |S\_i| + N \log N)$。

```cpp
#include <iostream>
#include <string>
#include <set>
using namespace std;

typedef unsigned long long ull; // 自然溢出模 2^64

ull get_string_hash(const string& s) {
    ull h = 0;
    ull p = 131; // 质数基数
    for (char c : s) {
        h = h * p + c; // 自然溢出
    }
    return h;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

int n;
    if (!(cin >> n)) return 0;

set<ull> st; // 利用 set 自动去重存储数值哈希
    for (int i = 0; i < n; ++i) {
        string temp;
        cin >> temp;
        st.insert(get_string_hash(temp));
    }

cout << st.size() << "\n"; // 输出本质不同字符串个数
    return 0;
}
```

---

## 5. 进阶哈希应用

### 5.1 快速判定回文子串（洛谷 P3805 【模板】Manacher）
一个字符串为回文，等价于其正读与反读完全一致。
利用哈希，这等价于其正向哈希值等于其反向哈希值：$H(S) = H(S\_{rev})$。

为了支持在 $O(1)$ 时间判定任意子串 $S[l \dots r]$ 是否为回文，我们可以：
1. 计算原字符串 $S$ 的正向前缀哈希值：$f[i]$。
2. 计算原字符串反转串 $S\_{rev}$ 的前缀哈希值：$g[i]$。
子串 $S[l \dots r]$ 对应反转串在 $S\_{rev}$ 中所映射的子区间为 $S\_{rev}[n-1-r \dots n-1-l]$。我们只需在 $O(1)$ 时间检验其双向哈希是否等价：
$$H\_{f}(S[l \dots r]) \stackrel{?}{=} H\_{g}(S\_{rev}[n-r \dots n-l] \quad (\text{1-indexed}))$$

在寻找最长回文子串时，我们可以利用贪心思想使时间复杂度优化到完全线性的 **$O(N)$**。因为最长回文串长度是单调的，我们无需从 $l=0$ 重新扩展，可以直接从 $l = \lfloor ans / 2 \rfloor$ 开始向两侧尝试扩展。若成功，即可提升全局最大答案 $ans$。

#### C++ 最长回文子串线性哈希代码实现：
```cpp
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

typedef unsigned long long ull;

const int N = 11000010;
const ull B = 131; // 哈希基数

char s[N];
ull f[N], g[N], p[N]; // f: 正向，g: 反向，p: 基数幂
int n;
string t;

// O(1) 获取正向子串哈希
ull get_fwd(int l, int r) {
    if (l > r) return 0;
    return f[r] - f[l - 1] * p[r - l + 1];
}

// O(1) 获取反向子串哈希
ull get_rev(int l, int r) {
    if (l > r) return 0;
    return g[n - l + 1] - g[n - r] * p[r - l + 1];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

if (!(cin >> t)) return 0;
    n = t.length();
    for (int i = 0; i < n; ++i) s[i + 1] = t[i]; // 1-indexed

p[0] = 1;
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i - 1] * B + (s[i] - 'a' + 1);
        p[i] = p[i - 1] * B;
    }

// 预处理反转串的前缀哈希
    for (int i = 1; i <= n; ++i) {
        g[i] = g[i - 1] * B + (s[n - i + 1] - 'a' + 1);
    }

int ans = 0;
    for (int i = 1; i <= n; ++i) {
        // 1. 奇数长度回文 (中心为 i)
        int l = ans / 2;
        if (ans % 2 == 1) l = (ans + 1) / 2;
        if (l == 0) {
            if (get_fwd(i, i) == get_rev(i, i)) {
                ans = max(ans, 1);
                l = 1;
            }
        }
        while (i - l >= 1 && i + l <= n && get_fwd(i - l, i + l) == get_rev(i - l, i + l)) {
            ans = max(ans, 2 * l + 1);
            l++;
        }

// 2. 偶数长度回文 (中心为 i, i+1)
        l = ans / 2;
        if (l == 0) l = 1;
        while (i - l + 1 >= 1 && i + l <= n && get_fwd(i - l + 1, i + l) == get_rev(i - l + 1, i + l)) {
            ans = max(ans, 2 * l);
            l++;
        }
    }

cout << ans << "\n";
    return 0;
}
```

---

### 5.2 提取字符串的最小周期（POJ 2406 Power Strings）
* **定义**：长度为 $N$ 的字符串具有周期 $p$，当且仅当其长度为 $N-p$ 的前缀 $S[0 \dots N-p-1]$ 与长度为 $N-p$ 的后缀 $S[p \dots N-1]$ 完全一致。
  $$S[0 \dots N-p-1] \stackrel{?}{=} S[p \dots N-1]$$

利用哈希，我们可以对每个可能的因子 $p$（$p$ 必须是总长 $N$ 的约数）进行 $O(1)$ 的匹配校验。首个成功通过前缀与后缀哈希值比对匹配的 $p$ 即为字符串的最小周期。

```cpp
// 核心逻辑框架
void solve(const string& s) {
    int n = s.length();
    init_hash(n); // 预处理
    for (int p = 1; p <= n; ++p) {
        if (n % p == 0) { // 周期长度必须是总长度的因子
            // O(1) 验证前缀 S[0..n-p-1] 和后缀 S[p..n-1]
            if (get_hash(0, n - p - 1) == get_hash(p, n - 1)) {
                cout << n / p << "\n"; // 输出最大重复次数
                return;
            }
        }
    }
}
```

---

### 5.3 哈希值的区间拼接性质
已知两个独立字符串 $S\_1$、$S\_2$ 的哈希值 $H(S\_1)$ 和 $H(S\_2)$。我们可以在 $O(1)$ 时间内合成并计算出它们无缝拼接后的新哈希值：
$$H(S\_1S\_2) = \left( H(S\_1) \cdot p^{|S\_2|} + H(S\_2) \right) \bmod M$$

这一代数拼接性质是利用高级数据结构维护区间动态哈希的底层逻辑。

---

## 6. 哈希与高级数据结构结合

### 6.1 哈希 + 线段树/树状数组
通过线段树的区间维护功能，可以将每个节点设计为存储对应区间子串的哈希值。
利用哈希值拼接公式，父节点的哈希值可以直接由左右子节点的哈希值合并得出：
$$\text{hash}[\text{parent}] = \left( \text{hash}[\text{left\_child}] \cdot p^{\text{len}(\text{right\_child})} + \text{hash}[\text{right\_child}] \right) \bmod M$$

这使得系统能在 **$O(\log N)$** 复杂度下同时支持：
* **单点字符修改**。
* **区间任意子串哈希值动态查询**。

---

### 6.2 树上路径哈希（DFS + LCA 结合）
可以将哈希思想应用到树结构中，用于在对数时间内判断树上任意两条路径代表的字符串序列是否一致。
* **从根向下的哈希（Down）**：从根至节点 $v$。
  $$h\_d[v] = (h\_d[\text{parent}(v)] \cdot p + val[v]) \bmod M$$
* **从叶向上的哈希（Up）**：从节点 $v$ 回溯向根。
  $$h\_u[v] = (h\_u[\text{parent}(v)] + val[v] \cdot p^{\text{depth}[v]}) \bmod M$$

#### 查询路径 $u \to v$ 的哈希：
设 $w = \text{LCA}(u, v)$ 为它们的最近公共祖先。路径可以拆分为向上的 $u \to w$ 与向下的 $w \to v$ 两段：
1. 路径 $w \to v$ 可通过从根向下的前缀哈希值 $h\_d$ 在 $O(1)$ 时间提取出来。
2. 路径 $u \to w$ 可通过自下而上的前缀哈希值 $h\_u$ 在 $O(1)$ 时间提取出来。
3. 利用哈希值拼接公式，将这两段合并，即可得到路径 $u \to v$ 序列的全局哈希值。

---

### 6.3 二维哈希 (2D Hashing)
用于在 $O(1)$ 时间内快速提取并计算任意大小矩阵中任意子矩阵的哈希值。我们通常采取**行、列双向滚动哈希**：
1. **行哈希（Row-wise）**：选择第一个基数 $p\_1$。对矩阵的每一行，分别计算一维前缀哈希值，得到前缀矩阵 $h\_{row}[i][j]$。
2. **列哈希（Column-wise）**：选择第二个基数 $p\_2$。对上述已经处理完的行前缀哈希值矩阵，将其作为新的数，并在每列方向上再次进行一次前缀哈希计算，得到最终的二维前缀哈希矩阵 $h\_{final}[i][j]$。

基于二维容斥原理，提取左上角为 $(r\_1, c\_1)$、右下角为 $(r\_2, c\_2)$ 的子矩阵哈希值公式为：
$$\text{Val}\_1 = h\_{final}[r\_2 + 1][c\_2 + 1]$$
$$\text{Val}\_2 = h\_{final}[r\_1][c\_2 + 1] \cdot p\_2^{r\_2 - r\_1 + 1} \bmod M$$
$$\text{Val}\_3 = h\_{final}[r\_2 + 1][c\_1] \cdot p\_1^{c\_2 - c\_1 + 1} \bmod M$$
$$\text{Val}\_4 = h\_{final}[r\_1][c\_1] \cdot p\_1^{c\_2 - c\_1 + 1} \cdot p\_2^{r\_2 - r\_1 + 1} \bmod M$$
$$H\_{\text{submatrix}} = \left( (\text{Val}\_1 - \text{Val}\_2 - \text{Val}\_3 + \text{Val}\_4) \bmod M + M \right) \bmod M$$

#### C++ 二维哈希预处理框架：
```cpp
// 假设 A 为大小为 M x N 的二维原数组矩阵
long long h_row[N][N];
long long h_final[N][N];
long long pw1[N], pw2[N]; // 对应 p1 与 p2 的幂次数组
const long long p1 = 131, p2 = 13331, M = 1e9 + 7;

void init_2d_hash(int n, int m_len) {
    // 1. 行哈希处理
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j <= m_len; ++j) {
            h_row[i][j] = (h_row[i][j - 1] * p1 + A[i][j - 1]) % M;
        }
    }
    // 2. 列哈希处理 (对行哈希的结果进行二次纵向映射)
    for (int j = 1; j <= m_len; ++j) {
        for (int i = 1; i <= n; ++i) {
            h_final[i][j] = (h_final[i - 1][j] * p2 + h_row[i - 1][j]) % M;
        }
    }
}
```

---

## 7. 解题思维与实践避坑指南

### 7.1 万物皆可哈希
字符串哈希本质上是对一个高维序列对象的有损压缩编码。很多具有序列性质的对象都可以应用这一思想：
* **数字序列**：直接将数值代入 $s\_i$ 计算哈希。
* **树的形状**：可以通过括号序列将一树结构线性化（或利用子树特征排序拼接），用哈希判断两棵树是否同构。
* **集合的判等**：对集合元素排序后视为确定序列进行哈希。

### 7.2 实践避坑要点
1. **防范负数求余**：C++ 中的 `%` 运算符对负数会保留负号。区间哈希相减容易产生负值，必须确保写为 `(h[r+1] - term % M + M) % M`。
2. **字符映射必须大于 0**：转换时必须映射到从 $1$ 开始的正整数（如 `s[i] - 'a' + 1`）。若允许某个字符映射为 $0$，会导致形如 `"a"` 与 `"aa"` 的哈希指纹完全一样，或者 `"b"` 与 `"ab"` 的指纹冲突。
3. **乘法溢出防护**：在计算 $(a \cdot b) \bmod M$ 时，若 $a$ 和 $b$ 都是 `long long` 且接近 $M$ 边界，乘积会爆 $64$ 位整型限制。对于 $10^9$ 级别的模数，使用 `long long` 承载是绝对安全的（$M^2 \approx 10^{18}$ 未超限制）；若使用更高位模数，必须采用 `__int128` 进行过渡强转。
4. **随机化的妙用**：为防止数据被刻意针对性构造而退化。在运行时可使用随机种子（如系统时钟）来动态决定多项式哈希的基数 $p$。这能使攻击者无从推算碰撞极值。

哈希表与字符串哈希（Hash Table & String Hashing）

1. 数组 + 哈希函数：基本存储逻辑

1.1 直观理解：快递储物柜模型

假设你正在管理一个拥有 10,000 个储物柜的大型快递站： * 传统思路：将所有包裹随意堆在一起。寻找某个特定客户的包裹时，工作人员必须依次遍历翻找所有包裹，最坏情况下时间复杂度为 $O(N)$。 * 哈希表思路：制定一个固定规则（哈希函数），根据收件人姓名直接计算出一个柜子编号。 * 收件人 “张三” $\to$ 计算得出 8 号柜。直接放进 8 号柜。 * 收件人 “李四” $\to$ 计算得出 3 号柜。直接放进 3 号柜。当客户“张三”来取件时，系统只需再次输入“张三”，通过哈希规则瞬间计算出柜子编号 8，工作人员直接开柜取件。这一步充分利用了静态数组 $O(1)$ 的随机访问性能。

1.2 数值场景：大整数的高效查找

假设需要存储约 100 个范围极大（如可达 $10^9$）的整数，例如集合 ${1022384, 2392743, 2904892, 9348920, 25390, 2835301, \dots}$，并要求极快地判断某个数是否存在。

哈希解决方案（简单取模法）：定义哈希函数： $$\text{Hash}(key) = key \bmod 100$$ 该函数将任意大整数映射到 $0 \sim 99$ 的范围内，我们准备一个长度为 100 的数组。
$1022384 \to 1022384 \bmod 100 = 84$（存放在 84 号桶）
$2392743 \to 2392743 \bmod 100 = 43$（存放在 43 号桶）
$2904892 \to 2904892 \bmod 100 = 92$（存放在 92 号桶）

桶存储分布示意（长度为 100 的数组）：

桶索引 (Index)	存储的数值 (Stored Keys)
`0`	空 (Empty)
`1`	`2835301`
`2 ~ 19`	...
`20`	`9348920`
`21 ~ 42`	...
`43`	`2392743`
`44 ~ 83`	...
`84`	`1022384`
`85 ~ 89`	...
`90`	`25390`
`91`	空 (Empty)
`92`	`2904892`
`93 ~ 99`	...

当查找大整数 $1022384$ 时，直接计算 $\text{Hash}(1022384) = 84$，直接定位至 84 号桶，只需 $O(1)$ 时间即可确认。

2. 哈希冲突（Collision）及其解决方法

两个不同的 Key 经过同一个哈希函数可能会算出相同的映射地址。尤其是由于取模的值域被严重缩减，哈希冲突在所难免。常用的冲突解决方法有两种：

2.1 拉链法（Separate Chaining）

每个桶不再直接存放一个数值，而是挂载一个单链表。当发生冲突时，将相同哈希值的元素直接追加到该桶对应的链表末尾： $$2835301 \to 7864201 \to 4512401 \to \dots$$ * C++ 中的 std::unordered_map 和 Python 的 dict 底层正是使用了拉链法。当链表长度超过特定阈值（如负载因子过大）时，底层通常会将长链表自动升级为红黑树，以确保最坏情况下的查询性能。

2.2 开放寻址法（Open Addressing）

如果不使用链表，当位置被占领时，就去寻找下一个空闲的桶。 * 线性探测法：若 1 号位置被占，则看 2 号；2 号被占则看 3 号……直到找到空位。 * 双哈希法（Double Hashing）：线性探测容易造成数据在某些连续区间“聚集（Clustering）”。双哈希法的核心是让冲突后的“下一次跳跃步长”不固定，而是根据当前 Key 再次进行哈希运算来决定。它引入两个哈希函数： * $\text{Hash}_1(key)$：决定初始存放的基准位置。 * $\text{Hash}_2(key)$：决定发生冲突时，每次向后跳跃的步长。 $$\text{Index} = \left(\text{Hash}_1(key) + i \times \text{Hash}_2(key)\right) \bmod M$$ 其中 $i$ 为冲突次数（$0, 1, 2, \dots$），$M$ 为哈希表的物理长度。

💡 设计细节：为了保证双哈希法能遍历完哈希表中的每个位置，$\text{Hash}_2(key)$ 算出的步长绝对不能为 $0$，且步长必须与哈希表长度 $M$ 互质。因此，工程上通常将 $M$ 取为质数，而 $\text{Hash}_2(key)$ 的计算结果范围限制在 $[1, M-1]$ 之间。

3. 字符串哈希 (String Hashing)

对于一个长度为 $L$ 的字符串，如果我们想快速进行相等比较或子串查找，常规的比对时间复杂度为 $O(L)$。字符串哈希技术可以将任意长度的字符串映射为一个固定大小的整数（哈希指纹），从而将长字符串的比对开销优化至 $O(1)$。

3.1 多项式滚动哈希 (Polynomial Rolling Hash)

对于一个长度为 $n$ 的字符串 $S = s_0s_1\dots s_{n-1}$（字符映射为非负整数值），我们可以将其视作一个 $p$ 进制的数（$p$ 被称为基数 Base）。多项式哈希值 $H(S)$ 定义为： $$H(S) = \left( \sum_{i=0}^{n-1} s_i \cdot p^i \right) \bmod M$$ 其中 $M$ 为用于防止整型溢出而精心挑选的大质数模数。

直观上，这类似于十进制。例如数字 138 可以表达为 $8 \cdot 10^0 + 3 \cdot 10^1 + 1 \cdot 10^2$。

在多项式定义中，我们也可以颠倒基数的幂次顺序，以下定义在后续计算前缀哈希和子串哈希时最为自然（即 $s_0$ 乘以最高次幂）： $$H(S) = \left( s_0 \cdot p^{n-1} + s_1 \cdot p^{n-2} + \dots + s_{n-1} \cdot p^0 \right) \bmod M$$

3.2 基数与模数的合理选择

基数 $p$：
$p$ 必须严格大于字符集的大小。若处理 26 个小写英文字母，$p$ 至少为 27。一般在竞赛中选择质数，如 31、131、13331。这能确保哈希值分布更加均匀。
模数 $M$：
$M$ 必须是一个足够大的质数（如 $10^9+7$ 或 $10^9+9$）。
另一种选择是选用大小为 $2^{64}$ 的自然溢出（在 C++ 中使用 unsigned long long 自动产生溢出，免去取模运算，效率高，但有极小概率被专门的数据卡掉）。

3.3 前缀哈希与递推计算

类似于一维前缀和，我们预处理出字符串 $S$ 每一个前缀的哈希值。设 $h[i]$ 为前缀 $S[0 \dots i-1]$（长度为 $i$）的哈希值。我们能推导出非常简洁的递推关系： $$h[0] = 0$$ $$h[i] = (h[i-1] \cdot p + s_{i-1}) \bmod M$$

这个递推式的计算方式与秦九韶算法（Horner's method）完全一致，每次迭代只需 $1$ 次乘法和 $1$ 次加法，能在 $O(N)$ 时间内高效预处理完毕。在预处理的同时，我们也需要预先计算出 $p$ 的幂次数组：$pw[i] = p^i \bmod M$。

3.4 $O(1)$ 提取子串哈希值

有了前缀哈希 $h$ 数组和幂数组 $pw$，我们可以在 $O(1)$ 时间内查询任意子串 $S[l \dots r]$（0-based 索引）的哈希值。子串 $S[l \dots r]$ 为 $s_l s_{l+1} \dots s_r$。其对应的哈希值为： $$H(S[l \dots r]) = (s_l \cdot p^{r-l} + s_{l+1} \cdot p^{r-l-1} + \dots + s_r \cdot p^0) \bmod M$$

观察前缀哈希 $h[r+1]$（代表 $S[0 \dots r]$）与前缀哈希 $h[l]$（代表 $S[0 \dots l-1]$）： $$h[r+1] = (s_0 p^r + \dots + s_{l-1} p^{r-l+1}) + (s_l p^{r-l} + \dots + s_r p^0) \bmod M$$ $$h[r+1] = \left( h[l] \cdot p^{r-l+1} + H(S[l \dots r]) \right) \bmod M$$

移项整理后，我们得到核心计算子串哈希公式： $$H(S[l \dots r]) = \left( h[r+1] - h[l] \cdot p^{r-l+1} \right) \bmod M$$

为了防范模运算下出现减法负数，C++ 实现中应采用如下安全写法： $$H(S[l \dots r]) = \left( \left( h[r+1] - h[l] \cdot pw[r-l+1] \bmod M \right) + M \right) \bmod M$$

3.5 经典单哈希实现模板（C++）

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

const int N = 1000005;
const int P = 131;       // 常用基数 Base
const int M = 1e9 + 7;   // 常用大质数模数 Modulo

string s;
long long h[N];          // 前缀哈希数组
long long pw[N];         // P 幂数组

// 预处理
void init(int n) {
    pw[0] = 1;
    for (int i = 1; i <= n; ++i) {
        pw[i] = pw[i - 1] * P % M;
        h[i] = (h[i - 1] * P + s[i - 1]) % M; // 字符串 0-indexed
    }
}

// O(1) 获取子串 S[l..r] 的哈希值 (0-indexed)
long long get_hash(int l, int r) {
    int len = r - l + 1;
    long long res = (h[r + 1] - h[l] * pw[len] % M + M) % M;
    return res;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    s = "abcdefg";
    int n = s.length();
    init(n);
    cout << "Substring [1..3] (bcd) hash: " << get_hash(1, 3) << endl;
    return 0;
}

3.6 安全双哈希（Dual Hashing）实现模板

单哈希可能存在人为构造的“哈希冲突碰撞攻击”。在关键竞赛或严苛数据环境下，最稳妥、最安全的方案是使用双哈希（即计算两个不同基数与模数的哈希对 $(h_1, h_2)$ 作为字符串的唯一指纹签名）。 * 碰撞率：若单哈希碰撞率为 $\frac{1}{M_1}$，则双哈希碰撞率可骤降到 $\frac{1}{M_1 \cdot M_2}$。若两模数都在 $10^9$ 级别，碰撞率低至 $10^{-18}$，在可承受的数据规模下碰撞的概率完全可以忽略不计。

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

const int N = 1000005;

struct HashPair {
    long long h1, h2;
    HashPair(long long a = 0, long long b = 0) : h1(a), h2(b) {}
    bool operator==(const HashPair& o) const {
        return h1 == o.h1 && h2 == o.h2;
    }
};

const long long P1 = 131, M1 = 1e9 + 7;
const long long P2 = 13331, M2 = 998244353;

string s;
HashPair h[N];  // 双哈希前缀数组
HashPair pw[N]; // 幂数组

void init(int n) {
    pw[0] = HashPair(1, 1);
    for (int i = 1; i <= n; ++i) {
        pw[i].h1 = pw[i - 1].h1 * P1 % M1;
        pw[i].h2 = pw[i - 1].h2 * P2 % M2;
    }
    for (int i = 1; i <= n; ++i) {
        h[i].h1 = (h[i - 1].h1 * P1 + s[i - 1]) % M1;
        h[i].h2 = (h[i - 1].h2 * P2 + s[i - 1]) % M2;
    }
}

HashPair get_hash(int l, int r) {
    int len = r - l + 1;
    long long r1 = (h[r + 1].h1 - h[l].h1 * pw[len].h1 % M1 + M1) % M1;
    long long r2 = (h[r + 1].h2 - h[l].h2 * pw[len].h2 % M2 + M2) % M2;
    return HashPair(r1, r2);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    s = "dualhashing";
    init(s.length());
    HashPair res = get_hash(0, 3);
    cout << "HashPair [0..3]: (" << res.h1 << ", " << res.h2 << ")\n";
    return 0;
}

4. 字符串哈希基础应用：不同字符串去重计数

4.1 问题场景（洛谷 P3370 【模板】字符串哈希）

给定 $N$ 个仅包含字母与数字的字符串 $S_1, S_2, \dots, S_N$，求其中有多少个本质不同的字符串。 * 数据范围：$N \le 10000$，串长 $M \le 1500$。

4.2 题解分析

如果直接使用 std::set<string> 进行存储比对去重，由于每次字符串插入的比较开销为 $O(M)$，最坏情况下总时间复杂度为 $O(N \cdot M \log N)$，在大规模数据下容易产生超时。

采用字符串哈希，我们将每个字符串直接映射到一个 unsigned long long（利用 $2^{64}$ 自然溢出机制防碰撞），直接比较整数。复杂度优化为 $O(\sum |S_i| + N \log N)$。

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

typedef unsigned long long ull; // 自然溢出模 2^64

ull get_string_hash(const string& s) {
    ull h = 0;
    ull p = 131; // 质数基数
    for (char c : s) {
        h = h * p + c; // 自然溢出
    }
    return h;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    if (!(cin >> n)) return 0;

    set<ull> st; // 利用 set 自动去重存储数值哈希
    for (int i = 0; i < n; ++i) {
        string temp;
        cin >> temp;
        st.insert(get_string_hash(temp));
    }

    cout << st.size() << "\n"; // 输出本质不同字符串个数
    return 0;
}

5. 进阶哈希应用

5.1 快速判定回文子串（洛谷 P3805 【模板】Manacher）

一个字符串为回文，等价于其正读与反读完全一致。利用哈希，这等价于其正向哈希值等于其反向哈希值：$H(S) = H(S_{rev})$。

为了支持在 $O(1)$ 时间判定任意子串 $S[l \dots r]$ 是否为回文，我们可以： 1. 计算原字符串 $S$ 的正向前缀哈希值：$f[i]$。 2. 计算原字符串反转串 $S_{rev}$ 的前缀哈希值：$g[i]$。子串 $S[l \dots r]$ 对应反转串在 $S_{rev}$ 中所映射的子区间为 $S_{rev}[n-1-r \dots n-1-l]$。我们只需在 $O(1)$ 时间检验其双向哈希是否等价： $$H_{f}(S[l \dots r]) \stackrel{?}{=} H_{g}(S_{rev}[n-r \dots n-l] \quad (\text{1-indexed}))$$

在寻找最长回文子串时，我们可以利用贪心思想使时间复杂度优化到完全线性的 $O(N)$。因为最长回文串长度是单调的，我们无需从 $l=0$ 重新扩展，可以直接从 $l = \lfloor ans / 2 \rfloor$ 开始向两侧尝试扩展。若成功，即可提升全局最大答案 $ans$。

C++ 最长回文子串线性哈希代码实现：

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

typedef unsigned long long ull;

const int N = 11000010;
const ull B = 131; // 哈希基数

char s[N];
ull f[N], g[N], p[N]; // f: 正向，g: 反向，p: 基数幂
int n;
string t;

// O(1) 获取正向子串哈希
ull get_fwd(int l, int r) {
    if (l > r) return 0;
    return f[r] - f[l - 1] * p[r - l + 1];
}

// O(1) 获取反向子串哈希
ull get_rev(int l, int r) {
    if (l > r) return 0;
    return g[n - l + 1] - g[n - r] * p[r - l + 1];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (!(cin >> t)) return 0;
    n = t.length();
    for (int i = 0; i < n; ++i) s[i + 1] = t[i]; // 1-indexed

    p[0] = 1;
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i - 1] * B + (s[i] - 'a' + 1);
        p[i] = p[i - 1] * B;
    }

    // 预处理反转串的前缀哈希
    for (int i = 1; i <= n; ++i) {
        g[i] = g[i - 1] * B + (s[n - i + 1] - 'a' + 1);
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        // 1. 奇数长度回文 (中心为 i)
        int l = ans / 2;
        if (ans % 2 == 1) l = (ans + 1) / 2;
        if (l == 0) {
            if (get_fwd(i, i) == get_rev(i, i)) {
                ans = max(ans, 1);
                l = 1;
            }
        }
        while (i - l >= 1 && i + l <= n && get_fwd(i - l, i + l) == get_rev(i - l, i + l)) {
            ans = max(ans, 2 * l + 1);
            l++;
        }

        // 2. 偶数长度回文 (中心为 i, i+1)
        l = ans / 2;
        if (l == 0) l = 1;
        while (i - l + 1 >= 1 && i + l <= n && get_fwd(i - l + 1, i + l) == get_rev(i - l + 1, i + l)) {
            ans = max(ans, 2 * l);
            l++;
        }
    }

    cout << ans << "\n";
    return 0;
}

5.2 提取字符串的最小周期（POJ 2406 Power Strings）

定义：长度为 $N$ 的字符串具有周期 $p$，当且仅当其长度为 $N-p$ 的前缀 $S[0 \dots N-p-1]$ 与长度为 $N-p$ 的后缀 $S[p \dots N-1]$ 完全一致。 $$S[0 \dots N-p-1] \stackrel{?}{=} S[p \dots N-1]$$

// 核心逻辑框架
void solve(const string& s) {
    int n = s.length();
    init_hash(n); // 预处理
    for (int p = 1; p <= n; ++p) {
        if (n % p == 0) { // 周期长度必须是总长度的因子
            // O(1) 验证前缀 S[0..n-p-1] 和后缀 S[p..n-1]
            if (get_hash(0, n - p - 1) == get_hash(p, n - 1)) {
                cout << n / p << "\n"; // 输出最大重复次数
                return;
            }
        }
    }
}

5.3 哈希值的区间拼接性质

已知两个独立字符串 $S_1$、$S_2$ 的哈希值 $H(S_1)$ 和 $H(S_2)$。我们可以在 $O(1)$ 时间内合成并计算出它们无缝拼接后的新哈希值： $$H(S_1S_2) = \left( H(S_1) \cdot p^{|S_2|} + H(S_2) \right) \bmod M$$

这一代数拼接性质是利用高级数据结构维护区间动态哈希的底层逻辑。

6. 哈希与高级数据结构结合

6.1 哈希 + 线段树/树状数组

通过线段树的区间维护功能，可以将每个节点设计为存储对应区间子串的哈希值。利用哈希值拼接公式，父节点的哈希值可以直接由左右子节点的哈希值合并得出： $$\text{hash}[\text{parent}] = \left( \text{hash}[\text{left_child}] \cdot p^{\text{len}(\text{right_child})} + \text{hash}[\text{right_child}] \right) \bmod M$$

这使得系统能在 $O(\log N)$ 复杂度下同时支持： * 单点字符修改。 * 区间任意子串哈希值动态查询。

6.2 树上路径哈希（DFS + LCA 结合）

可以将哈希思想应用到树结构中，用于在对数时间内判断树上任意两条路径代表的字符串序列是否一致。 * 从根向下的哈希（Down）：从根至节点 $v$。 $$h_d[v] = (h_d[\text{parent}(v)] \cdot p + val[v]) \bmod M$$ * 从叶向上的哈希（Up）：从节点 $v$ 回溯向根。 $$h_u[v] = (h_u[\text{parent}(v)] + val[v] \cdot p^{\text{depth}[v]}) \bmod M$$

查询路径 $u \to v$ 的哈希：

设 $w = \text{LCA}(u, v)$ 为它们的最近公共祖先。路径可以拆分为向上的 $u \to w$ 与向下的 $w \to v$ 两段： 1. 路径 $w \to v$ 可通过从根向下的前缀哈希值 $h_d$ 在 $O(1)$ 时间提取出来。 2. 路径 $u \to w$ 可通过自下而上的前缀哈希值 $h_u$ 在 $O(1)$ 时间提取出来。 3. 利用哈希值拼接公式，将这两段合并，即可得到路径 $u \to v$ 序列的全局哈希值。

6.3 二维哈希 (2D Hashing)

用于在 $O(1)$ 时间内快速提取并计算任意大小矩阵中任意子矩阵的哈希值。我们通常采取行、列双向滚动哈希： 1. 行哈希（Row-wise）：选择第一个基数 $p_1$。对矩阵的每一行，分别计算一维前缀哈希值，得到前缀矩阵 $h_{row}[i][j]$。 2. 列哈希（Column-wise）：选择第二个基数 $p_2$。对上述已经处理完的行前缀哈希值矩阵，将其作为新的数，并在每列方向上再次进行一次前缀哈希计算，得到最终的二维前缀哈希矩阵 $h_{final}[i][j]$。

基于二维容斥原理，提取左上角为 $(r_1, c_1)$、右下角为 $(r_2, c_2)$ 的子矩阵哈希值公式为： $$\text{Val}_1 = h_{final}[r_2 + 1][c_2 + 1]$$ $$\text{Val}_2 = h_{final}[r_1][c_2 + 1] \cdot p_2^{r_2 - r_1 + 1} \bmod M$$ $$\text{Val}_3 = h_{final}[r_2 + 1][c_1] \cdot p_1^{c_2 - c_1 + 1} \bmod M$$ $$\text{Val}_4 = h_{final}[r_1][c_1] \cdot p_1^{c_2 - c_1 + 1} \cdot p_2^{r_2 - r_1 + 1} \bmod M$$ $$H_{\text{submatrix}} = \left( (\text{Val}_1 - \text{Val}_2 - \text{Val}_3 + \text{Val}_4) \bmod M + M \right) \bmod M$$

C++ 二维哈希预处理框架：

// 假设 A 为大小为 M x N 的二维原数组矩阵
long long h_row[N][N];
long long h_final[N][N];
long long pw1[N], pw2[N]; // 对应 p1 与 p2 的幂次数组
const long long p1 = 131, p2 = 13331, M = 1e9 + 7;

void init_2d_hash(int n, int m_len) {
    // 1. 行哈希处理
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j <= m_len; ++j) {
            h_row[i][j] = (h_row[i][j - 1] * p1 + A[i][j - 1]) % M;
        }
    }
    // 2. 列哈希处理 (对行哈希的结果进行二次纵向映射)
    for (int j = 1; j <= m_len; ++j) {
        for (int i = 1; i <= n; ++i) {
            h_final[i][j] = (h_final[i - 1][j] * p2 + h_row[i - 1][j]) % M;
        }
    }
}

7. 解题思维与实践避坑指南

7.1 万物皆可哈希

字符串哈希本质上是对一个高维序列对象的有损压缩编码。很多具有序列性质的对象都可以应用这一思想： * 数字序列：直接将数值代入 $s_i$ 计算哈希。 * 树的形状：可以通过括号序列将一树结构线性化（或利用子树特征排序拼接），用哈希判断两棵树是否同构。 * 集合的判等：对集合元素排序后视为确定序列进行哈希。

7.2 实践避坑要点

防范负数求余：C++ 中的 % 运算符对负数会保留负号。区间哈希相减容易产生负值，必须确保写为 (h[r+1] - term % M + M) % M。
字符映射必须大于 0：转换时必须映射到从 $1$ 开始的正整数（如 s[i] - 'a' + 1）。若允许某个字符映射为 $0$，会导致形如 "a" 与 "aa" 的哈希指纹完全一样，或者 "b" 与 "ab" 的指纹冲突。
乘法溢出防护：在计算 $(a \cdot b) \bmod M$ 时，若 $a$ 和 $b$ 都是 long long 且接近 $M$ 边界，乘积会爆 $64$ 位整型限制。对于 $10^9$ 级别的模数，使用 long long 承载是绝对安全的（$M^2 \approx 10^{18}$ 未超限制）；若使用更高位模数，必须采用 __int128 进行过渡强转。
随机化的妙用：为防止数据被刻意针对性构造而退化。在运行时可使用随机种子（如系统时钟）来动态决定多项式哈希的基数 $p$。这能使攻击者无从推算碰撞极值。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com