c++ - 如何将 unordered_set 与自定义类型一起使用？

Question

我是否需要为自定义类型创建自己的哈希函数？ unordered_set 没有我可以使用的默认值吗？

Answer 1

标准库包含 std::hash<T> 的特化对于基本类型、指针和 std::string (或者更确切地说，对于 std::basic_string 的所有特化)。

不幸的是，该库不包含以下重要的 new-from-old 组合功能，但它是 Boost 的一部分，您应该将其复制到您的代码中:

template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

使用此函数，您可以散列对、元组、数组和任何类型的 范围 本身可散列的元素。浏览 Boost 源代码以获取许多示例和有用的实现。显然你可以使用这个函数为你自己的类型创建一个哈希函数。例如，这里是散列一对:

template<typename S, typename T> struct pair_hash<std::pair<S, T>>
{
    inline std::size_t operator()(const std::pair<S, T> & v) const
    {
         std::size_t seed = 0;
         hash_combine(seed, v.first);
         hash_combine(seed, v.second);
         return seed;
    }
};

但请注意，哈希组合不会产生好的哈希值。结果的统计质量很差(例如，很容易产生哈希冲突)。良好的散列需要能够看到所有原始输入位，并且不能通过部分散列分解。 (这就是为什么在当前的标准库中没有更好的解决方案；没有人能够提出令人满意的设计。)