如何构造哈希冲突攻破GCC标准哈希使unordered_set插入耗时超1.5秒

核心原理 #

• GCC 标准库中 std::unordered_set 插入元素时，会先计算元素的哈希值映射到对应桶下标，同一个桶内的元素会以链表形式存储。如果所有插入元素的哈希值完全相同，所有元素都会被分配到同一个桶，插入的时间复杂度会从均摊O(1)退化为O(n)，15000次插入的总复杂度达到O(n²)，足以让运行时间超过1.5秒。
• GCC的std::hash<std::string>是公开的固定迭代哈希算法，完全可以针对性构造出批量符合字符要求的哈希碰撞字符串。

碰撞字符串构造方法 #

要求的合法字符范围为数字、大小写字母、下划线共63种可选值，字符串长度不超过15，我们可以选择固定长度为10的字符串构造碰撞：

1. 先随便选一个基准字符串，计算它的哈希值作为目标哈希
2. 选取字符串中两个不同的位置作为调整位，枚举这两个位置的合法字符组合，筛选出哈希值和目标哈希完全相等的字符串
3. 两个调整位共有63*63=3969种组合，不够的话再加一个调整位，三个调整位就有25万种组合，完全够生成15000个互不相同的碰撞字符串

构造逻辑参考代码：

#include <string>
#include <vector>
#include <functional>

std::vector<std::string> generate_collisions(int count) {
    const std::string allowed = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_";
    std::vector<std::string> res;
    std::string base = "pre_fix_000"; // 长度为10，符合长度限制要求
    size_t target_hash = std::hash<std::string>()(base);
    
    // 调整第6位和第9位字符筛选碰撞串
    for (char c1 : allowed) {
        for (char c2 : allowed) {
            base[6] = c1;
            base[9] = c2;
            if (std::hash<std::string>()(base) == target_hash) {
                res.push_back(base);
                if (res.size() >= count) return res;
            }
        }
    }
    return res;
}

效果说明 #

你给出的测试代码中，用上述生成的15000个碰撞字符串作为输入，插入std::unordered_set时每次插入都需要遍历整个桶内的链表判断元素是否重复，总操作次数超过2亿次，在普通消费级CPU上的运行时间必然超过1.5秒。

内容的提问来源于stack exchange，提问作者Eraston