C++中的unordered_map，其中键也是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;
}

- Sean Plot

---

看一下你的哈希函数对这两个映射返回了什么。 - Caleth

Answer 1

比较两个std::unordered_map对象使用==会比较它们是否包含相同的键。但是，它无法告诉您它们是否按照相同的顺序包含它们（毕竟这是一个无序映射）。然而，您的hashing_func取决于映射中项目的顺序：hash<string>()("ab")通常与hash<string>()("ba")不同。请注意保留HTML标记。

- Angew is no longer proud of SO

Answer 2

首先，等号运算符是必需的，所以您应该保留它。

让我们来看看您的无序映射的哈希函数：

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

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

此外，我还期望哈希函数还将包括未排序映射键的值，除了键本身。我想你可能希望以这种方式进行 - 只要它们的键相同，忽略它们的值，就将两个无序映射视为相同的键。从问题中不清楚您的期望是什么，但您可能需要考虑一下。

- Sam Varshavchik

---

是的，那就是问题所在，哈希函数没有为相同的键返回相同的值。它不知怎么从我的脑海中溜走了。 - Sean Plot

Answer 3

一个好的起点是了解每个映射返回的哈希函数，或者更容易理解的是哈希函数中字符串构造生成的内容。

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

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

- Caleth