如何将unordered_set用作哈希键？实现顺序无关的哈希与equal_to函数

先解决相等性比较的问题 #

你之前通过遍历元素比较的方式失效，核心原因是unordered_set的迭代顺序不固定。正确的集合相等性判断应该完全忽略顺序，只关注元素是否完全一致：

1. 先比较两个集合的大小，大小不同直接判定不等
2. 大小相同时，验证其中一个集合的所有元素都存在于另一个集合中（因为unordered_set本身不允许重复元素，只要双向包含就是相等）

在C++20及之后，unordered_set自带contains成员函数，实现起来很简洁：

template <typename T>
struct unordered_set_equal_to {
    bool operator()(const std::unordered_set<T>& a, const std::unordered_set<T>& b) const {
        if (a.size() != b.size()) return false;
        for (const auto& elem : a) {
            if (!b.contains(elem)) return false;
        }
        return true;
    }
};

如果用的是C++17或更早版本，把!b.contains(elem)换成b.find(elem) == b.end()即可。

顺序无关的哈希函数实现 #

要生成不受元素顺序影响的哈希值，必须用可交换的哈希组合逻辑，下面两种方案各有优劣：

方案1：轻量型可交换组合（异或/求和） #

直接对每个元素的哈希值做异或或求和操作，这两个操作的结果都不受元素顺序影响：

template <typename T>
struct unordered_set_hash {
    size_t operator()(const std::unordered_set<T>& s) const {
        size_t hash_val = 0;
        std::hash<T> elem_hasher;
        for (const auto& elem : s) {
            // 异或操作：顺序不影响结果，但成对相同元素会抵消哈希值
            hash_val ^= elem_hasher(elem);
            // 可选：求和（注意溢出，可配合模运算降低碰撞）
            // hash_val += elem_hasher(elem);
        }
        return hash_val;
    }
};

注意：异或的缺点是如果集合中有偶数个相同元素，它们的哈希贡献会相互抵消，可能提升碰撞概率。如果在意这点，优先选求和（或对每个元素的哈希值做二次变换后再异或）。

方案2：排序后组合哈希（低碰撞概率） #

先把集合元素复制到临时容器排序，再用常规的哈希组合逻辑计算——这种方式完全避免了顺序问题，且碰撞概率更低，但需要额外的排序开销：

template <typename T>
struct unordered_set_hash {
    size_t operator()(const std::unordered_set<T>& s) const {
        std::vector<T> sorted_elems(s.begin(), s.end());
        std::sort(sorted_elems.begin(), sorted_elems.end());
        
        size_t hash_seed = 0;
        std::hash<T> elem_hasher;
        // 实现一个简单的hash_combine逻辑（类似Boost的实现）
        auto combine = [](size_t& seed, size_t val) {
            seed ^= val + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        };
        
        for (const auto& elem : sorted_elems) {
            combine(hash_seed, elem_hasher(elem));
        }
        return hash_seed;
    }
};

C++23的额外支持 #

C++23并没有直接为unordered_set提供标准的顺序无关哈希特化，但可以利用新特性简化代码：

• 用std::ranges::copy替代手动迭代填充临时容器
• 结合std::views::sort生成排序视图，不过本质和手动排序逻辑一致
• 基础类型的std::hash特化更完善，减少自定义哈希的工作量

使用示例 #

把自定义的哈希和相等性比较传入unordered_map的模板参数即可：

int main() {
    using SetKey = std::unordered_set<int>;
    using MyMap = std::unordered_map<SetKey, std::string, unordered_set_hash<int>, unordered_set_equal_to<int>>;
    
    MyMap map;
    SetKey set1{1,2,3};
    SetKey set2{3,2,1}; // 顺序不同但内容一致
    
    map[set1] = "hello";
    // 此时set2能正确匹配到set1的条目
    std::cout << map[set2] << std::endl; // 输出hello
    return 0;
}

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