Блог

Как 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 amp;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 (autoamp; entry : map) {
        cout << entry.first << ", " << entry.second << endl;
    }

    return 0;
}
 

Выход:

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

Ссылка на базу данных onlinegdb.

unordered_set может содержать один экземпляр любого уникального значения данных; это не ограничивается только хранением значений данных с уникальными хэш-значениями. В частности, если два данных значения различны (в зависимости от == оператора), но оба хэш один и тот же хеш-значение, unordered_set будет принимать меры, чтобы удержать их обоих, независимо от того, как правило, несколько снижается эффективность (так как любая хэш-поиска по каждой из них внутренне хеш структура данных, которая содержит оба из них, в котором данная поиска-кода придется перебрать, пока не найдет тот его ищет)