std::tuple 的自定义哈希不适用于 unordered_set

Question

我希望你能帮助我理解我的代码有什么问题。

基本上我需要一个 unordered_set 的元组，但每次我调用插入函数时，我都会看到即使散列相同，也会插入元组，这意味着我有元组unordered_set 中的相同散列。为了更清楚，让我在这里分享一段代码。

所以，我的例子是这样的：

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

这是我得到的输出：

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

为什么如果每个条目的散列值相同，插入的条目数量是 3？我原以为只有一个。

此致

Answer 1

两个不相等的元素具有相同的哈希值是完全正常的（这种情况称为 "hash collision"）。毕竟，比方说，字符串的数量是无限的，但在 size_t 中只能表示有限数量的值。观察 std::unordered_set 采用两个单独的模板参数 - 一个用于计算散列，另一个用于检查两个元素是否相等。

如果要将 make_tuple(1, 2, 3) 和 make_tuple(1, 3, 2) 等同对待，除了合适的哈希实现。

简而言之：相等的元素必须散列为相同的值，但反之则不然——散列为相同值的元素不一定相等。

std::tuple 的自定义哈希不适用于 unordered_set

Custom hash for std::tuple doesn't work with unordered_set

c++

c++11

hash

unordered-set