unordered_set什么时候调用operator==？

Question

在我看来，

这就是 unordered_set 插入的工作原理。

• 当调用 insert 时，会调用哈希函数。

• 在下面的代码中，我分别对 <string, string> 进行散列first和值。second

  -> Test(make_pair("good","james"))（创建测试对象）

  -> return hasher(test.get_name().first) + hasher(test.get_name().second)（哈希函数返回）

  -> 8838398861423961495（哈希值）

• 并且它尝试在哈希表中找到相同的哈希值。

• 如果在哈希表中找不到相同的哈希值，则在哈希表中创建其哈希值。

所以，我认为具有不同哈希值的元素不应该在unordered_set中进行比较。

这是我的代码

#include <vector>
#include <string>
#include <iostream>
#include <unordered_set>

using namespace std;

class Test
{
public:
    Test(pair<string, string> n):name(n){};
    
    pair<string,string> get_name() const { return name; };

    bool operator==(const Test &test) const
    {
        cout << "compare " << get_name().first << ',' << get_name().second << ':' << test.get_name().first << ',' << test.get_name().second << '\n';
        return (name == test.get_name());
    }

private:
    pair<string,string> name;
};

namespace std
{
    template<>
    struct hash<Test>
    {
        hash<string> hasher;
        size_t operator() (const Test& test) const noexcept
        {
            cout << test.get_name().first << ',' << test.get_name().second << ':' << (hasher(test.get_name().first) + hasher(test.get_name().second)) << '\n';
            return hasher(test.get_name().first) + hasher(test.get_name().second);
        }
    };
}


int main()
{
    unordered_set<Test> hash_set;
    hash_set.insert(Test(make_pair("song","james")));
    hash_set.insert(Test(make_pair("kim","james")));
    hash_set.insert(Test(make_pair("kim","james")));

    cout << hash_set.size() << '\n';
    return 0;
}

它尝试在 hash_set 中插入三个 Test 对象。

第一个和第二个不应具有相同的哈希值（但有可能发生）

每当它被调用时我都会operator== cout查看它何时被调用。

还有hash功能。

这就是结果。

song,james:1897374899324052084
kim,james:6658567258605789090
compare song,james:kim,james
kim,james:6658567258605789090
compare kim,james:kim,james
2

==即使 (song, james) 和 (kim, james) 不在同一个桶中（哈希值不同），如何（通过调用）进行比较？

而且，如果我将“歌曲”更改为“好”，它会改变结果。

（我使用 Apple clang 版本 14.0.3 (clang-1403.0.22.14.1) 和 std=c++14 ）

Answer 1

哈希表的每个桶都包含许多不同的哈希值。否则，如果您的散列是 64 位宽，则需要在内存中存储 2^64 个存储桶，而您显然没有足够的内存。

或者换句话说，该std::unordered_set实现将把自己的散列应用到您的散列之上的更小的范围（尽管这可能非常简单，例如取散列的最低位）。哈希的全部目的是将可能的输入值的数量减少到一个小范围，希望是均匀分布的。

因此，即使您的哈希函数计算出的哈希值不同，它们仍然可能被放入同一个桶中，然后由实现决定是否立即用于==比较属于同一桶的元素，或者是否将首先尝试哈希函数的输出进行比较。

更一般地说，原则上没有什么禁止实现进行==不必要的比较，尽管这当然不利于实现的质量。