c++ - std :: tuple的自定义哈希不适用于unordered_set(Custom hash for std::tuple doesn't work with unordered_set)

Question

I hope you help me to understand what's wrong with my code.

(希望您能帮助我了解我的代码有什么问题。)

Basically I need an unordered_set of tuples, but every time I call the insert function, I see that even when the hash is the same, the tuple is being inserted which means that I have tuples with the same hash in an unordered_set.

(基本上，我需要一个unordered_set的元组，但是每次调用insert函数时，我都会看到即使散列相同，也会插入该元组，这意味着我在unordered_set中具有具有相同散列的元组。)

To be more clear, let me share a piece of code here.

(更清楚地说，让我在这里分享一段代码。)

So, this is how my example looks like:

(因此，我的示例如下所示：)

#include <iostream>
#include <tuple>
#include <unordered_set>

using namespace std;
using namespace testing;

struct MyHash {
    size_t operator()(const tuple<int, int, int>& t) const
    {
        auto [num1, num2, num3] = t;
        vector<int> v(3);
        v[0] = num1;
        v[1] = num2;
        v[2] = num3;
        sort(v.begin(), v.end());
        string key = to_string(v[0]) + "|" + to_string(v[1]) + "|" + to_string(v[2]);
        auto hashValue = hash<string>()(key);
        cout << "Hash value for " << key << "= " << hashValue << endl;
        return hashValue;
    }
};

int main(int argc, char** argv)
{
    unordered_set<tuple<int, int, int>, MyHash> s;
    s.insert(make_tuple(1, 2, 3));
    s.insert(make_tuple(1, 3, 2));
    s.insert(make_tuple(3, 2, 1));

    cout << "Amount of items = " << s.size() << endl;
}

and this is the output I got:

(这是我得到的输出：)

Hash value for 1|2|3= 12066275531359578498
Hash value for 1|2|3= 12066275531359578498
Hash value for 1|2|3= 12066275531359578498
Amount of items = 3

Why if the hash value for each entry is the same the amount of item inserted is 3?

(如果每个条目的哈希值相同，为什么插入的项数为3？)

I was expecting having only one.

(我期待只有一个。)

Regards

(问候)

  ask by Freddy Martinez Garcia translate from so

Answer 1

It is perfectly normal for two unequal elements to have the same hash (a situation known as "hash collision").

(两个不相等的元素具有相同的哈希值（一种称为“哈希冲突”的情况）是完全正常的。)

After all, there's an infinite number of, say, strings, but only a finite number of values representable in size_t .

(毕竟，有无数个字符串，但在size_t只能表示有限数量的值。)

Observe that std::unordered_set takes two separate template parameters - one to compute the hash, and another to check whether two elements are equal.

(观察到std::unordered_set需要两个单独的模板参数-一个用于计算哈希，另一个用于检查两个元素是否相等。)

If you want to treat make_tuple(1, 2, 3) and make_tuple(1, 3, 2) as equivalent, you need to pass a suitable implementation of equality comparison as a third template parameter of std::unodered_set , in addition to the suitable hash implementation.

(如果你要正确对待make_tuple(1, 2, 3)和make_tuple(1, 3, 2)等同，你需要通过一个合适的实现平等的比较作为第三个模板参数std::unodered_set ，除了合适的哈希实现。)

In short: equal elements must hash to the same value, but the converse is not true - elements hashing to the same value are not necessarily equal.

(简而言之：相等的元素必须散列为相同的值，但反之则不成立-散列为相同值的元素不一定相等。)