这是一份为你量身定制的讲义，主题关于 C++ 中 std::unordered_map 的底层原理、为什么会被卡、黑客是如何卡它的，以及你代码中使用的 custom_hash 是如何完美防御这一攻击的。

讲义：C++ std::unordered_map 的安全隐患与 Anti-Hash-Collision（防卡哈希）原理

在算法竞赛（如 Codeforces、LeetCode）或高并发后端开发中，使用 std::unordered_map 时如果不加防范，常常会遇到因“精心构造的恶意数据”导致程序从 $\mathcal{O}(1)$ 的平均时间复杂度退化为 $\mathcal{O}(N^2)$，最终引发 TLE（超时）。

一、 std::unordered_map 的底层原理

要理解为什么会被卡，首先需要知道 std::unordered_map 是怎么工作的： 1. 哈希表结构：它底层通常由一个“桶数组”（Bucket Array）和一个链表/红黑树（处理冲突）组成。 2. 存取过程： * 当你插入一个键值对 (key, value) 时，系统会调用一个哈希函数：size_t h = Hash(key); * 然后通过取模运算决定它应该放到哪个桶里：int bucket_index = h % num_buckets; * 如果多个不同的 key 算出来的 bucket_index 相同，就发生了哈希冲突（Collision）。

二、 为什么会卡？unordered_map 的固有缺陷

在 C++ 标准（C++11/14/17）中，标准库对基础类型（如 int, long long, string）提供的默认哈希函数（std::hash）是极其简单且固定的。

• 对于整数类型（如 long long）：很多标准库实现（如旧版本的 libstdc++）中的 std::hash<long long> 直接就是把这个数字本身当做哈希值（Identity Hash）。即 hash(x) = x。
• 对于字符串类型：通常采用类似 Times33 这样的多项式滚动哈希算法，其系数也是固定的。

由于哈希函数和模数（桶的数量）在程序运行期间是完全确定、不随时间或测试数据改变的，这就给攻击者留下了可乘之机。

三、 黑客如何卡掉 unordered_map？（构造卡哈希数据）

如果出题人或者恶意攻击者知道你的程序使用了默认的 std::unordered_map<long long, ...>，他们可以构造出一组“同余碰撞”的数据。

攻击原理演示：

假设某个时刻你的 unordered_map 底层桶的数量（num_buckets）是 $B$（通常是 2 的幂次或者某个质数）。 恶意用户只需要输入一堆模 $B$ 同余的数字，例如： * $x_1 = 5$ * $x_2 = 5 + B$ * $x_3 = 5 + 2B$ * $x_4 = 5 + 3B$ * $\dots$

因为默认哈希就是数字本身，这些数算出来的桶位置全都是： 5 % B、(5 + B) % B、(5 + 2B) % B $\rightarrow$ 全部落入同一个桶中！

当成千上万个元素全部挤在同一个桶的链表里时，每次查找、插入的时间复杂度就从期望的 $\mathcal{O}(1)$ 退化成了链表遍历的 $\mathcal{O}(N)$。如果插入 $N$ 个这样的元素，总时间复杂度直接飙升到 $\mathcal{O}(N^2)$。对于 $N = 10^5$ 级别的数据，程序瞬间超时。

四、 如何防御？—— 分析你代码中的 custom_hash

为了防止被卡，核心思想是引入随机性，打破“输入数据”与“桶位置”之间的直接线性关系，让黑客无法预测你的哈希规律。

让我们逐行拆解你代码中使用的防卡哈希模板：

1. 核心随机因子：FIXED_RANDOM

size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    // ...
}

• 时间种子：利用 chrono::steady_clock::now().time_since_epoch().count() 获取当前程序启动时的时间戳（纳秒级）。
• 防预测：这个时间戳对于出题人（黑客）来说是不可预测的。每次运行程序，FIXED_RANDOM 都是一个完全不同的随机数。
• 扰动输入：x + FIXED_RANDOM 这一步，直接把用户输入的恶意数据 $x$ 和一个随机数相加。即便黑客知道你想查什么数，由于他不知道每次运行程序时加的这个随机偏移量，他就无法构造出必然碰撞的数据。

2. 强混淆函数：splitmix64

仅仅加上一个随机数还不够，还需要通过一个强力的混淆函数（Hash Mixer）把每一位都充分搅匀：

static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15ULL;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
}

• 来源：splitmix64 是 Sebastiano Vigna 提出的一种极其优秀的 64 位伪随机数生成器/哈希混淆算法。
• 雪崩效应（Avalanche Effect）：它通过连续的位运算（异或 ^）和大质数乘法，使得输入数据的任何微小改变（哪怕二进制下只有某一位变了），输出的哈希值都会发生翻天覆地的、完全随机的改变。
• 这样一来，哪怕恶意用户输入了规律性极强的数字（比如连续的 $1, 2, 3, 4, 5$），经过 splitmix64 搅动后，在哈希表里也会被均匀地打散到各个不同的桶中。

五、 总结与替代方案

通过引入 chrono 随机种子 + splitmix64 强混淆，你的 custom_hash 实现了类似于 SipHash（Rust 和现代 Python/Ruby 默认采用的抗碰撞哈希）的效果，彻底封死了哈希冲突攻击的可能。

💡 扩展小贴士：

1. C++20 的升级：如果你使用的是 C++20 及以上标准，标准库对 std::unordered_map 的安全性做了一定改进（许多实现默认加入了随机盐 random seed），但在老版本（如 C++11/14/17）或部分平台的 GCC 中，依然建议像你这样手写一个 custom_hash。
2. 竞赛习惯：在做算法题时，养成习惯为 unordered_map 或 unordered_set 加上自定义哈希，可以无脑避免绝大多数因数据构造不当导致的 TLE。

题目：两数之和https://hlcoding.com/solution/description/5382/

// 自定义哈希，防止被卡 unordered_map
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, x;
    cin >> n >> x;

    unordered_map<long long, long long, custom_hash> pos; // 值 ->
                                                          // 位置（1-based）

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