Hash 哈希

Hash Brown 超好吃！

本文内容：

• 三类 hash（Hash 表、字符串 hash、XOR-hash）的可能存在的问题及解决方案
• Hash 的应用
• 一类用取模来 hash 的方法

引言

• hash 写对了就不会被 hack，被卡的多多少少有些问题（如果正确的 hash 真的被卡了那可以去买彩票了（）。
• Codeforces 作为全网最尊重 hash 的网站，尤其需要注意 hash 的正确性。

本文以 Codeforces 不被 hack 为目标；标有 (hack) 的小标题仅在有 hack 的比赛中需要注意，无 hack 时可忽略。

Part I. 怎么 Hash

一、关于 hash

哈希的本质思想：映射。对于非整数对象，或者对于很大的整数值域，将其映射到一个较小的值域空间。这样就能用数表示，方便比较或用数组存储。

哈希冲突：两个东西映射到了同一个数。

二、Hash 表

可能存在的问题

1. std::unordered 家族 (hack)

如 unordered_set、unordered_multiset、unordered_map 都是使用哈希实现的，可以被特定数据卡掉。

unordered_map 在 GCC 的实现中是维护了一个桶，每个桶对应一条单链表。正常情况下，哈希函数将元素均匀分散到不同的桶中，此时查找、插入、删除的平均复杂度为 $O(1)$。

GCC 的默认哈希函数是直接取模。只需要翻到这个固定的素数表，取这个素数的倍数，取模后的桶索引就恒等于 0。这样，它们就会全部塞进同一个桶里，后续每次都需要遍历这个桶的整个链表，总复杂度退化到 $O(N^2)$，从而 TLE。

2. pbds (hack)

在 __gnu_pbds 中，有两种哈希表：

• __gnu_pbds::cc_hash_table：cc 拉链法解决哈希冲突，和 umap 没什么区别，甚至更慢。
• __gnu_pbds::gp_hash_table：gp 探查法解决哈希冲突，当发生哈希冲突时，通过探测在数组中向后寻找空位，相比于 umap，更快，代价是空间复杂度略大。hack 方法：桶的数量是 $2^k$，构造一组末尾 $k$ 位二进制全部为 0 的数据，哈希索引都会恒等于 0。

解决方案

1. 换 map：多个 log，看时间能否接受。
2. 确定性方法 ：能想到可以用，想不到就没必要了（废话。
3. SplitMix64：一个安全的自定义哈希函数，见下。

#include <unordered_map>
#include <chrono>
#include <cstdint>

template <typename T>
struct safe_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    std::size_t operator()(T x) const {
        static const uint64_t seed = std::chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(std::hash<T>{}(x) + seed);
    }
};

template <typename T, typename V>
struct safe_unordered_map : public std::unordered_map<T, V, safe_hash<T>> {
    using std::unordered_map<T, V, safe_hash<T>>::unordered_map;
    
    safe_unordered_map(std::size_t n = 0) {
        if (n > 0) {
            this->reserve(n);
        }
        this->max_load_factor(0.25);
    }
};

三、字符串 hash

可能存在的问题

1. int 级别模数的单模数哈希

根据生日悖论，不需要特别 hack，比较次数只要达到 $\mathcal{O}(\sqrt{10^9})$ 级别就有超过 $50\%$ 的概率发生碰撞。

设有 $N$ 个等概率的可能取值，随机抽取 $k$ 个样本。则至少有两个样本相同的概率

$$P = 1 - \prod_{i=0}^{k-1} \left(1 - \frac{i}{N}\right) \approx 1 - \prod_{i=0}^{k-1} \mathrm e^{-i/N} \approx 1 - \mathrm e^{-k^2 /2N}$$

取 $k=\sqrt{2N \log 2}$，$P=50\%$。

2. 非素数模数（如自然溢出）

如果模数是素数，随机选择底数时，多项式值为 0 的概率有限。如果模数是合数，这个概率的上界就失效了，更容易产生碰撞。

设字符串长度为 $L$，传统的字符串 hash 是将字符串映射为域 $\mathbb{Z}_p$ 上的多项式 $\displaystyle f(x) = \sum_{i=0}^{L-1} c_i x^{i} \pmod p$。

由于在任意域中，一个 $k$ 次多项式最多 $k$ 个不同的根，所以上述多项式的根 $x$ 的数量最多 $L-1$ 个。随机选择底数，即在所有 $\{0, 1, 2, \dots, p-1\}$ 中均匀随机选择一个底数 $x$，能选到这些根的概率不超过 $\dfrac{L - 1}{p}$。

考虑到只有当模数 $p$ 是素数时，$\mathbb{Z}_p$ 才是域。如果模数是合数，这是是个环，环有大量零因子，导致概率上界失效，更容易产生碰撞。

特别地，自然溢出的碰撞可以用 Thue Morse 序列 $t$，即 $t(n)=\operatorname{popcount}(n) \bmod 2$。设 $S_0 = \text{a}$, $T_0 = \text{b}$，递归定义 $S_k = S_{k-1} T_{k-1}$, $T_k = T_{k-1} S_{k-1}$，即 $S_k[n] = \text{a} + t(n)$，那么

$$H(S_k) - H(T_k) \equiv (s_0 - t_0) \prod_{i=0}^{k-1} (H^{2^i} - 1) \pmod {2^{64}}$$

利用平方差公式展开，$H^{2^i} - 1$ 每次都会贡献额外的 $2$ 的幂次，最终导致 $H(S_k) - H(T_k) \equiv 0$。

3. 公开模数及底数 (hack)

有固定构造法。

例如取字符集 $\{\text{a}, \text{b}\}$，先折半搜索长度相同且较小的字符串 $A$ 与 $B$，满足 $H(A) = H(B) \pmod P$。然后构造 $S = T_1 T_2 \dots T_k$，其中 $T_i \in \{A, B\}$，这样就能得到 $2^k$ 个不同的字符串，且哈希值完全相同。

4. 其它

注意多项式 $\displaystyle f(x) = \sum_{i=0}^{L-1} c_i x^{i} \bmod p$ 里，不能 $c_{i} \neq 0$。

注意底数不应小于 $c_{i}$。

此外，效率？码量？

解决方案

1. ULL 级别的模数或双模

• 模数：ULL 级别的模数 $2^{61} - 1$，$10^{18}+3$ 等，或双模。
• 底数：建议用 mt19937_64 随机，防止对着卡。

二者比较：

• 碰撞概率：理论碰撞概率差不多，单大模数略好，因为双模产生的 $p_{1}p_{2}$ 实际上是个合数。
• 效率：双模效率较低。
• 码量：ULL 级别的乘法需要 int128 或一些位运算技巧，较复杂。双模的比较略复杂。

代码以 ULL 级别的模数为例，供参考。

#include <random>
#include <chrono>
#include <vector>

using i64 = long long;
using u64 = unsigned long long;
using u128 = unsigned __int128;

struct Hash {
    // ---------------- 模数 ---------------- //
    static constexpr u64 P = (1ULL << 61) - 1;
    static constexpr u64 add(u64 a, u64 b) {
        a += b;
        return a >= P ? a - P : a;
    }
    static constexpr u64 sub(u64 a, u64 b) {
        return add(a, P - b);
    }
    static constexpr u64 mul(u64 a, u64 b) {
        u128 x = u128(a) * b;
        return add(x & P, x >> 61);
    }

    // ---------------- 底数 ---------------- //
    static inline const u64 H = [] {
        std::mt19937_64 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
        std::uniform_int_distribution<u64> dist(P / 2, P - 1);
        u64 base = dist(rnd);
        if (base % 2 == 0) base++;
        return base;
    } ();
    
    // ---------------- 哈希 ---------------- //
    static inline std::vector<u64> powH {1};
    std::vector<u64> pref;

    template<typename T>
    Hash(const T& s) : pref(s.size() + 1) {
        while (powH.size() <= s.size()) {
            powH.push_back(mul(powH.back(), H));
        }
        for (std::size_t i = 0; i < s.size(); i++) {
            u64 c = (s[i] % i64(P) + P) % P;  // 小心有负数 
            pref[i + 1] = add(mul(pref[i], H), c);
        }
    }

    u64 operator()(int L, int R) const {
        return sub(pref[R], mul(pref[L], powH[R - L]));
    }
};

2. 自然溢出

在无 hack 的比赛中，为简便，也可以选取

• 模数：$2^{64}$（自然溢出）。
• 底数：随机一个 奇数 。

四、XOR-hash

可能存在的问题

mt19937_64 是线性的 。设初始状态向量（种子）为 $\boldsymbol{x}$，那么第 $i$ 次生成的随机数 $o_i$ 可以写为 $o_i = \boldsymbol{B} \boldsymbol{A}^i \boldsymbol{x}$。

根据 Cayley-Hamilton 定理，对于任意方阵 $\boldsymbol{A}$，存在一个非零多项式 $p(\lambda) = \sum a_i \lambda^i$ 使得 $p(\boldsymbol{A}) = 0$。将这个多项式系数代入：

$$\sum_{i} a_i o_i = \sum_{i} a_i \boldsymbol{B}\boldsymbol{A}^i \boldsymbol{x} = \boldsymbol{B} \left(\sum_i a_i \boldsymbol{A}^i \right) \boldsymbol{x} = B \cdot p(\boldsymbol{A}) \cdot \boldsymbol{x} = 0$$

$\boldsymbol{x}$ 被消掉了，导致计算出的异或和必然是 $0$。

错误地使用 uniform_int_distribution(0, L) 仍然会导致相同的问题。当范围 $L = 2^n - 1$ 时（例如截取低 $n$ 位），主流 C++ 标准库实现只是简单地做了一个位掩码 rng() & mask。这依然是线性映射。

解决方案

依旧是 SM64：

#include <random>
#include <chrono>
#include <cstdint>

struct safe_rng {
    using result_type = uint64_t;  // 这个是适配 std::shuffle 等函数 

    std::mt19937_64 rng;

    safe_rng() : rng(std::chrono::steady_clock::now().time_since_epoch().count()) {}
    explicit safe_rng(uint64_t seed) : rng(seed) {}

    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    
    static constexpr uint64_t min() { return 0; }  // 也是适配 std::shuffle 等函数 
    static constexpr uint64_t max() { return UINT64_MAX; }

    uint64_t operator()() {
        return splitmix64(rng());
    }
} rng;

五、取模

取模也算是一种 hash，可以用于判定分数或大整数的相等。具体应用见下文的五。

Part II. Hash 什么

设 $H$ 表示随机底数，$H(x)$ 表示随机的哈希函数，$P$ 表示大素数。

一般情况，hash 对象都可以转化为 $f(H) \bmod P$，现举数例如下。

一、多重集合

随机一个哈希函数 $H(x)$，取

$$f(S) = \sum_{x \in S} H(x) \bmod 2^{64}$$

令 $c_x$ 是两个集合中元素 $x$ 的出现次数之差，碰撞概率为 $2^{-(64-\min \nu_{2}(c_x))}$。说人话就是如果所有的数的出现次数都包含 2 的幂次，低位就无效，更容易碰撞。

若选用 $\bmod P$，碰撞概率为 $\dfrac{1}{P}$。

二、不重集合

采用 xor-hash，随机一个哈希函数 $H(x)$，取

$$f(S) = \bigoplus_{x \in S} H(x) \bmod 2^{64}$$

或采用上述多重集 hash 方法。

应用：

• 区间染色问题，如 CF1996G
• 判定图的边子集是否为图的一个割

三、多项式 / 幂级数

直接取这个多项式为 hash 函数，即随机一个哈希值 $H$，代入 $f(H) \bmod P$。

字符串 hash 本质是构造了一个多项式。

四、树

对于有根树，取

$$H(u) = 1 + \sum_{v \in \text{children}(u)} \operatorname{SplitMix64}(H(v)) \bmod P$$

对于无根树，取重心为根。若有两个重心，分别计算后判定 $\text{pair}(\max, \min)$。

五、分数 / 大整数

（这个似乎鲜为人知）

将分数 $\dfrac{p}{q}$ 映射为 $p \cdot q^{-1} \bmod P$，将大整数 $n$ 映射为 $n \bmod P$。其实是评测机判断概率准确的一种方法。

举个例子：

• 题意 ：已知 $S=\dfrac{n!}{m}$ 及 $1 \le m < n \le 10^6$，求 $n,m$。(2025 CCPC Harbin Practice A)
• 思路 ：选模数 $P$（至少满足 $P>n,\ P> m$，最好是 ULL 级别），在模意义下计算并验证。
• 实现 ：枚举 $n$，计算 $m=\dfrac{n!}{S} \bmod P$。如果 $m\in[1,n-1]$，就说明找到了答案；否则说明此时 $m$ 不是整数，不是答案。复杂度 $\mathcal{O}(\log S + n \log P)$。
• 正确性 ：对于一个错误的枚举值 $n$，其对应的阶乘模数 $n! \bmod P$ 与 $X$ 无关。因此，计算出的 $m = (n! \cdot X^{-1}) \bmod P$ 在区间 $[0, P-1]$ 上可视为均匀分布，恰好落在合法区间 $[1, n-1]$ 内的概率为 $\dfrac{n - 1}{P}$。遍历所有 $n \in [2, 10^6]$ 时，整个算法期望出现的错误答案总个数 $E = \dfrac{n^{2}}{P} = \dfrac{10^{12}}{P}$。可见 $P$ 最好是 ULL 级别。

一个练习：2024 ICPC Shenyang G。

六、网格

取两个独立的底 $(H_1, H_2)$，格子 $(i, j)$ 的权值为 $H_1^i H_2^j A_{ij}$。

参考

• 一种比较科学的字符串哈希实现方法 - 知乎
• HashKiller——如何优雅地卡掉单模数哈希 - 洛谷专栏
• Blowing up unordered_map, and how to stop getting hacked on it - Codeforces
• Hacking Incorrect XOR Hashing with mt19937_64 - Codeforces