unordered_set 对的惊人行为

Question

如果 unordered_set 具有相同的散列值，那么 unordered_set 如何同时容纳 (0, 1) 和 (1, 0)？

#include <iostream>
#include <unordered_set>
#include <utility>

using namespace std;

struct PairHash
{
    template <class T1, class T2>
    size_t operator()(pair<T1, T2> const &p) const
    {
        size_t hash_first = hash<T1>{}(p.first);
        size_t hash_second = hash<T2>{}(p.second);
        size_t hash_combined = hash_first ^ hash_second;
        
        cout << hash_first << ", " << hash_second << ", " << hash_combined << endl;
        
        return hash_combined;    
    }
};

int main()
{
    unordered_set<pair<int, int>, PairHash> map;
    map.insert({0, 1});
    map.insert({1, 0});
    
    cout << map.size() << endl;

    for (auto& entry : map) {
        cout << entry.first << ", " << entry.second << endl;
    }

    return 0;
}

输出：

0, 1, 1
1, 0, 1
2
1, 0
0, 1

Link to onlinegdb.

Answer 1

unordered_set 可以保存任何唯一数据值的一个实例；它不仅限于仅保存具有唯一哈希值的数据值。特别是，当两个数据值不同（根据它们的 == 运算符）但都散列到相同的散列值时，unordered_set 将安排保存它们，通常在一个效率略有降低（因为对它们中的任何一个的任何基于散列的查找都会在内部散列到一个包含它们的数据结构，unordered_set 的查找代码将不得不迭代它直到找到它正在寻找）

unordered_set 对的惊人行为

Surprising behaviour with an unordered_set of pairs

c++

hash

unordered-set

stdset