unordered_set什么时候调用operator==？

Question

在我看来，

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

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

• 在下面的代码中，我分别对

  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

实现会将自己的散列应用于您的散列之上的较小范围（尽管这可能非常微不足道，例如获取散列的最低位）。哈希的重点是将可能的输入值的数量减少到一个小范围，希望是均匀分布的。

因此，即使你的哈希函数计算出的哈希值不同，它们仍然可能被放入同一个桶中，然后由实现决定是否立即使用

==

 来比较属于同一桶的元素，或者是否会首先尝试您的哈希函数的输出进行比较。

更一般地说，原则上没有什么禁止实现进行不必要的比较

==

，尽管这当然不利于实现的质量。