unordered_map 的 Unordered_map 与配对密钥 C++ 的自定义哈希函数？

Question

我有一些键是 pair<string, string>。我原本打算编写自己的哈希函数，但认为只实现 unordered_map<string, unordered_map<string, val>> 可能更容易。我应该注意这两者之间是否存在任何性能差异？

Answer 1

我会使用 std::unordered_map<std::pair<std::string, std::string>, Value, [pair_hash][1]> 有两个原因：

性能

当然，你可以用你最喜欢的分析器来衡量你的两个版本，但根据我的经验——分配的数量在这里最重要——所以请看：

flat_map.insert(key, value)); 平均只会创建一个新桶（或扩展一个桶），而

auto it = map2.insert(make_pair(key.first, map1{}));
it->second.insert(make_pair(key.second, value));

必须创建空 map1 - 这可能不是零成本。然后它必须 add/extend 两个桶（与给定哈希值关联的列表）。

Maintainability/Readability

第二个原因对我来说更重要。平面（一）地图易于使用。您已经可以在插入示例中看到它更复杂，但考虑擦除 - 它非常复杂，很容易出错：


void remove(
   std::unordered_map<std::string, 
           std::unordered_map<std::string, Value>>& map,
    std::pair<std::string, std::string> const& key)
{
   auto it1 = map.find(key.first);
   if (it1 == map.end()) return;
   it1->second.erase(key.second);
   // easy to forget part
   if (it1->second.empty())
   {
       map.erase(it1);
   }
}

Answer 2

在您的案例中定义一个简单的哈希函数是微不足道且高效的。如果 std::pair 在语义上是关键，那么这种方法会使您的意图明确。它还允许在地图中复制 std::pair 的第一个成员，因为您只需要整个键是唯一的。在使用方面，您还可以避免使用嵌套映射的附加间接层。

示例实现：

Godbolt

...

using pairSS = std::pair<std::string, std::string>;

namespace std
{
    template<> struct hash<pairSS>
    {
        std::size_t operator()(pairSS const& pair) const noexcept
        {
            return std::hash<std::string>{}(pair.first) ^
                (std::hash<std::string>{}(pair.second) << 1);
        }
    };
}

int main()
{
    std::pair myPair = {"Hi", "bye"};

    std::cout << std::hash<pairSS>{}(myPair) << std::endl;

    struct val{};
    std::unordered_map<pairSS, val> hashMap;
}

unordered_map 的 Unordered_map 与配对密钥 C++ 的自定义哈希函数？

Unordered_map of unordered_map vs custom hash function for pair key C++?

c++

unordered-map