哈希表与字符串哈希

哈希表通过哈希函数将键映射到有限个桶中，以较小代价完成查找、插入和删除。它适合需要按值快速判重、统计频次、记录映射关系的场景，例如两数之和、字符计数和访问过的状态。

哈希表的基本思想

设表长为 m，哈希函数计算 h(key)，操作时先定位到对应桶，再在桶中查找键。不同键映射到同一桶称为冲突，因此哈希值相同不代表原键相同。

  • 拉链法：每个桶保存一组元素；冲突元素挂在同一个桶中，删除也较直接。
  • 开放寻址：所有元素存放在表内，发生冲突后按探测规则继续寻找空槽；删除通常需要特殊标记。

装载因子为元素数除以桶数。装载因子越高，冲突越多；标准库会在必要时扩容并重哈希。平均情况下查找、插入、删除为 O(1)，极端冲突时可退化为 O(n)。

C++ 容器与使用步骤

unordered_set 用于存在性判断，unordered_map<Key, Value> 用于键值映射，unordered_map<T, int> 常用于频次统计。需要稳定的最坏 O(log n) 复杂度、键的有序遍历或防范对抗性哈希时，可改用 set/map。

  1. 确定键：例如数值、字符串或状态；确定值：例如下标、次数或答案。
  2. 遍历数据，先查询所需键是否已存在，再按题意插入或更新。
  3. 注意 mp[key] 会在键不存在时创建默认值；仅查询时优先使用 find 或 count。
// 无序数组中寻找和为 target 的两个下标
vector<int> twoSum(const vector<int>& a, int target) {
    unordered_map<int, int> pos;
    for (int i = 0; i < (int)a.size(); ++i) {
        auto it = pos.find(target - a[i]);
        if (it != pos.end()) return {it->second, i};
        pos[a[i]] = i;
    }
    return {};
}

每个元素至多查询、插入一次，平均时间 O(n)，额外空间 O(n)。

字符串哈希

字符串哈希把字符串编码为数值，常用多项式形式：逐字符执行 h = (h × P + code(c)) mod M。它适合大量比较子串、字符串去重和模式匹配的预处理；哈希相等只是“极大概率相等”，不能当作密码学安全校验。

预处理前缀哈希 h[i + 1] = (h[i] × P + s[i]) mod M 与幂 pw[i] = P^i mod M。左闭右闭子串 [l, r] 的哈希为：

H(l, r) = (h[r + 1] - h[l] × pw[r - l + 1]) mod M。

const long long MOD = 1000000007, P = 131;
vector<long long> h, pw;

void buildHash(const string& s) {
    int n = s.size();
    h.assign(n + 1, 0); pw.assign(n + 1, 1);
    for (int i = 0; i < n; ++i) {
        h[i + 1] = (h[i] * P + (unsigned char)s[i]) % MOD;
        pw[i + 1] = pw[i] * P % MOD;
    }
}
long long getHash(int l, int r) {
    return (h[r + 1] - h[l] * pw[r - l + 1] % MOD + MOD) % MOD;
}

建表时间和空间均为 O(n)，每次取子串哈希为 O(1)。对碰撞敏感的算法可使用两组不同的模数与底数进行双哈希，或在哈希相等后再作原串比较。