C++ unordered_map，其中key也是unordered_map

Question

我正在尝试使用unordered_map和另一个unordered_map作为键(自定义散列函数)。我还添加了一个自定义的相等函数，尽管它可能不需要。

代码不像我所期望的那样，但是我不能对正在发生的事情做出正面或反面的判断。由于某些原因，在执行find()时不调用相等的函数，这正是我所期望的。

unsigned long hashing_func(const unordered_map<char,int>& m) {
    string str;
    for (auto& e : m)
        str += e.first;
    return hash<string>()(str);
}
bool equal_func(const unordered_map<char,int>& m1, const unordered_map<char,int>& m2) {
    return m1 == m2;
}

int main() {

    unordered_map<
        unordered_map<char,int>, 
        string,
        function<unsigned long(const unordered_map<char,int>&)>,
        function<bool(const unordered_map<char,int>&, const unordered_map<char,int>&)>
        > mapResults(10, hashing_func, equal_func);

    unordered_map<char,int> t1 = getMap(str1);
    unordered_map<char,int> t2 = getMap(str2);

    cout<<(t1 == t2)<<endl; // returns TRUE
    mapResults[t1] = "asd";
    cout<<(mapResults.find(t2) != mapResults.end()); // returns FALSE

    return 0;
}

Answer 1

首先，当然需要相等操作符，所以您应该保留它。

让我们看一下无序映射的散列函数：

string str;
for (auto& e : m)
    str += e.first;
return hash<string>()(str);

由于它是一个无序映射，根据定义，迭代器可以按任意顺序遍历无序映射的键。但是，由于哈希函数必须为相同的键生成相同的散列值，因此该散列函数显然会在这方面失败。

此外，除了键本身之外，我还期望散列函数还包括无序映射键的值。我想你可能会这样做，因为两个无序映射被认为是相同的键，只要它们的键是相同的，忽略它们的值。从这个问题上看，你的期望是什么还不清楚，但你可能会想一想。

Answer 2

使用std::unordered_map比较两个==对象，比较映射是否包含相同的键。它无法判断它们是否以相同的顺序包含它们(毕竟，这是一个无序的映射)。但是，您的hashing_func取决于地图中项目的顺序：hash<string>()("ab")一般与hash<string>()("ba")不同。

Answer 3

一个很好的起点是hashing_func为每个映射返回什么，或者更容易地了解hashing_func中的字符串构造所生成的内容。

对于这种类型，一个更明显正确的哈希函数可以是：

unsigned long hashing_func(const unordered_map<char,int>& m) {
    unsigned long res = 0;
    for (auto& e : m)
        res ^ hash<char>()(e.first) ^ hash<int>()(e.second);
    return res;
}