如何在指定C++模板函数中用unordered_map统计哈希碰撞？

核心概念先理清楚 #

• unordered_map<size_t, unordered_set<string>>里的size_t键，就是哈希函数计算出来的哈希值——C++标准库的哈希函数（比如std::hash）返回值默认都是size_t，所以用这个类型做键刚好匹配。
• 不用把hasher本身转成size_t，而是用hasher去计算每个输入字符串的哈希值，得到的结果就是size_t类型的键。

完整实现代码 #

直接看可运行的模板函数实现：

#include <unordered_map>
#include <unordered_set>
#include <string>
#include <istream>

template <typename Hash>
int FindCollisions(const Hash& hasher, std::istream& text) {
    // 哈希值 -> 对应所有字符串的集合
    std::unordered_map<size_t, std::unordered_set<std::string>> hash_entries;
    std::string current_str;

    // 从输入流逐个读取字符串
    while (text >> current_str) {
        // 用传入的hasher计算当前字符串的哈希值
        size_t hash_value = hasher(current_str);
        // 将字符串插入对应哈希值的集合中
        hash_entries[hash_value].insert(current_str);
    }

    int collision_groups = 0;
    // 遍历所有哈希条目，统计碰撞组数
    for (const auto& entry : hash_entries) {
        const auto& str_set = entry.second;
        // 集合大小大于1，说明多个字符串哈希值相同，存在碰撞
        if (str_set.size() > 1) {
            collision_groups++;
            // 如果要统计总碰撞次数（比如两个字符串算1次碰撞，三个算2次），改成：
            // collision_groups += str_set.size() - 1;
        }
    }

    return collision_groups;
}

关键步骤拆解 #

1. 读取输入：通过while (text >> current_str)从输入流中读取所有字符串（默认按空格/换行分割）。
2. 计算哈希值：调用hasher(current_str)得到当前字符串的哈希值，只要Hash类型符合标准哈希接口（接受字符串参数，返回size_t），这一步就没问题。
3. 存储映射关系：把字符串放到对应哈希值的unordered_set里——unordered_set会自动去重，避免同一个字符串重复统计。
4. 统计碰撞：遍历unordered_map，只要某个哈希值对应的集合大小大于1，就说明存在碰撞，根据需求统计组数或总碰撞次数。

常见疑问解答 #

• 为什么键用size_t？：这是C++哈希函数的标准返回类型，比如std::hash<std::string>()的返回值就是size_t，所以用这个类型做键是天然匹配的。
• 和unordered_set方案的区别？：单纯用unordered_set存哈希值，只能知道有没有重复的哈希值，但看不到具体是哪些字符串撞了；而这个方案能完整记录每个哈希值对应的所有字符串，方便排查碰撞细节。
• 如果我的hasher返回不是size_t怎么办？：那你需要做类型转换（比如static_cast<size_t>(hasher(str))），但通常自定义哈希函数也会遵循标准返回size_t，避免不必要的转换。

测试示例 #

用std::hash<std::string>测试的代码：

#include <iostream>
#include <sstream>

int main() {
    // 模拟输入流，里面apple和banana各出现两次
    std::istringstream test_input("apple banana cherry apple date banana");
    std::hash<std::string> default_hasher;
    int result = FindCollisions(default_hasher, test_input);
    std::cout << "碰撞组数：" << result << std::endl; // 输出2
    return 0;
}

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