当Hash与KeyEqual基于不同子对象时，std::unordered_set如何正确检测相等元素？

代码片段 #

struct Foo
{
    int a, b;
};

template<>
struct std::hash<Foo>
{
    constexpr std::size_t operator()(const Foo& obj) const noexcept
    {
        return std::hash<int>{}(obj.a);
    }
};

template<>
struct std::equal_to<Foo>
{
    constexpr bool operator()(const Foo& lhs, const Foo& rhs) const noexcept
    {
        return std::equal_to<int>{}(lhs.b, rhs.b);
    }
};

问题解答 #

这种实现无法让std::unordered_set正确保证元素唯一性，核心原因是违反了C++标准对无序容器的强制要求：如果两个对象被equal_to判定为相等，它们的哈希值必须完全相同。

具体来说，std::unordered_set的唯一性检查逻辑是：

• 插入元素时，先通过哈希函数计算值找到对应的桶；
• 仅在该桶内遍历，用equal_to比较待插入元素与桶内已有元素；
• 若桶内无匹配元素，则完成插入。

现在的实现中，哈希依赖a，相等判定依赖b，会出现这种异常场景：
假设存在两个Foo对象x{1, 5}和y{2, 5}，equal_to会认为二者相等（因为b都是5），但它们的哈希值不同（a分别是1和2），会被分到不同的桶里。插入时，unordered_set只会检查各自桶内的元素，根本不会发现对方的存在，最终集合里会同时存在这两个被判定为相等的元素，直接破坏了set的唯一性语义。

正确的做法是让哈希和相等判定的逻辑保持一致：

• 要么都基于a：哈希取a的哈希值，相等判定比较a；
• 要么都基于b：哈希取b的哈希值，相等判定比较b；
• 若需要同时基于a和b，则哈希要结合二者的哈希值（比如通过哈希合并逻辑将两个值的哈希结果组合），相等判定同时比较a和b。

内容的提问来源于stack exchange，提问作者Sourav Kannantha B