unordered_set何时调用operator==？不同哈希值元素为何触发比较？

我原本以为unordered_set的插入逻辑是：调用insert时先计算哈希值，在哈希表中查找相同哈希值的桶，找不到就直接存入；只有哈希值相同的元素才会触发operator==比较。但测试代码里，哈希值不同的(song, james)和(kim, james)却触发了比较，把"song"改成"good"后结果又变了。

测试代码 #

#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;
}

运行结果 #

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

使用环境：Apple clang 14.0.3 (clang-1403.0.22.14.1)，std=c++14

原因分析 #

核心问题出在哈希值到桶索引的映射：

• unordered_set不会直接用哈希值定位元素，而是会把哈希值对当前哈希表的桶数量取模，得到实际的桶索引。
• 你看到的两个不同哈希值，对初始桶数量（通常默认是8）取模后得到了相同的索引，所以第二个元素会被放到第一个元素所在的桶里。
• 当插入元素时，unordered_set会遍历目标桶里的所有元素，调用operator==来确认是否存在重复元素，这就是你看到不同哈希值元素触发比较的原因。

当你把"song"改成"good"时，新的哈希值取模后得到的桶索引和kim,james的不同，自然不会进入桶内元素比较，也就不会触发operator==。

补充说明 #

• unordered_set的桶数量会随着元素数量增加自动扩容，但初始桶数量很小，不同哈希值碰撞到同一桶的概率并不低。
• 可以通过两种方式减少这类情况：
  • 设计更优质的哈希函数，降低不同元素哈希值取模后碰撞的概率（比如用异或代替加法，或者结合更散列的计算方式）
  • 创建unordered_set时指定更大的初始桶数量，比如unordered_set<Test> hash_set(100);

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