无序映射/集合中元组的通用哈希函数

Question

为什么std::unordered_map<tuple<int, int>, string>不能直接使用？定义tuple<int, int>的哈希函数很麻烦。

template<> struct do_hash<tuple<int, int>>                               
{   size_t operator()(std::tuple<int, int> const& tt) const {...}  }; 

《使用元组作为键构建无序映射表》(Matthieu M.)展示了如何自动化使用boost::tuple实现此功能。有没有一种方法可以在不使用可变参数模板的情况下实现c++0x元组的这个功能呢？

真希望这也能成为标准 :(

- Leo Goodstadt

---

如果你使用的是C++0x，为什么不使用可变参数模板？（或者有一个基于元组的实现，但没有可变参数模板吗？） - R. Martinho Fernandes

@RMartinho：VC++ 2010符合该描述（而且似乎下一个版本的VC++也很可能如此）。 - ildjarn

如果std::tuple是通过手动编写1到N元组的模板来实现的（例如boost::tuple），那么我猜测必须手动编写std::hash特化以对元组进行哈希（使用太聪明的预处理？）同样的方式。啊！ - Leo Goodstadt

Answer 1

这在gcc 4.5上可行，它允许所有包含标准可哈希类型的c++0x元组成为unordered_map和unordered_set的成员，无需进一步操作。(我将代码放在头文件中，然后进行包含。)

该函数必须存活在std命名空间中，以便它被参数相关名称查找(ADL)所捕获。

是否有更简单的解决方案？

#include <tuple>
namespace std{
    namespace
    {

        // Code from boost
        // Reciprocal of the golden ratio helps spread entropy
        //     and handles duplicates.
        // See Mike Seymour in magic-numbers-in-boosthash-combine:
        //     https://dev59.com/SW445IYBdhLWcg3wRoPH

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

        // Recursive template code derived from Matthieu M.
        template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
        struct HashValueImpl
        {
          static void apply(size_t& seed, Tuple const& tuple)
          {
            HashValueImpl<Tuple, Index-1>::apply(seed, tuple);
            hash_combine(seed, std::get<Index>(tuple));
          }
        };

        template <class Tuple>
        struct HashValueImpl<Tuple,0>
        {
          static void apply(size_t& seed, Tuple const& tuple)
          {
            hash_combine(seed, std::get<0>(tuple));
          }
        };
    }

    template <typename ... TT>
    struct hash<std::tuple<TT...>> 
    {
        size_t
        operator()(std::tuple<TT...> const& tt) const
        {                                              
            size_t seed = 0;                             
            HashValueImpl<std::tuple<TT...> >::apply(seed, tt);    
            return seed;                                 
        }                                              

    };
}

符合标准的代码

Yakk指出，在std命名空间中专门化事物实际上是未定义行为。如果您希望拥有符合标准的解决方案，那么您需要将所有此代码移入自己的命名空间，并放弃任何自动查找正确哈希实现的ADL的想法。例如：

unordered_set<tuple<double, int> > test_set;

你需要：

unordered_set<tuple<double, int>, hash_tuple::hash<tuple<double, int>>> test2;

其中hash_tuple是您自己的命名空间，而不是std::。

要实现这一点，您首先必须在hash_tuple命名空间内声明一个哈希实现。这将把所有非元组类型转发到std::hash：

namespace hash_tuple{

template <typename TT>
struct hash
{
    size_t
    operator()(TT const& tt) const
    {                                              
        return std::hash<TT>()(tt);                                 
    }                                              
};
}

请确保hash_combine调用的是hash_tuple::hash而不是std::hash

namespace hash_tuple{

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

然后将所有其他先前的代码包含在namespace hash_tuple中而不是std::中。

namespace hash_tuple{

    namespace
    {
        // Recursive template code derived from Matthieu M.
        template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
        struct HashValueImpl
        {
          static void apply(size_t& seed, Tuple const& tuple)
          {
            HashValueImpl<Tuple, Index-1>::apply(seed, tuple);
            hash_combine(seed, std::get<Index>(tuple));
          }
        };

        template <class Tuple>
        struct HashValueImpl<Tuple,0>
        {
          static void apply(size_t& seed, Tuple const& tuple)
          {
            hash_combine(seed, std::get<0>(tuple));
          }
        };
    }

    template <typename ... TT>
    struct hash<std::tuple<TT...>> 
    {
        size_t
        operator()(std::tuple<TT...> const& tt) const
        {                                              
            size_t seed = 0;                             
            HashValueImpl<std::tuple<TT...> >::apply(seed, tt);    
            return seed;                                 
        }                                              
    };

}

- Leo Goodstadt

---

有一个std::hash_combine函数吗？ - Leo Goodstadt

您的模板使用了gcc 4.6.3中的std::hash_combine进行编译。我进行了切换以避免使用boost。 - Bo Lu

不值得冒未定义行为的风险：不要专门针对你没有所有权的内容在std ::中进行特化，例如你没有所有权的std :: tuple <TT ...>。举个具体例子，如果标准的新迭代引入了它自己的哈希特化，会发生什么情况？当有人想到与你相同的主意并引入一个窄的hash <tuple <int>>特化时，会发生什么情况？这些是具体的例子，但未定义行为不仅限于此。你的程序是非法形式的。 - Yakk - Adam Nevraumont

这段话的意思是，虽然很老套，但向 std 命名空间添加特定功能是被建议的。但同时需要明确禁止添加类、函数或其他定义。参考链接为 http://en.cppreference.com/w/cpp/language/extending_std。 - Alex Huszagh

@AlexanderHuszagh 您只能为自定义类型（因此不能为std::tuple）将专业知识添加到std命名空间中。这就是Yakk在他/她的评论中提到的。 - Daniel Langr

Answer 2

#include <boost/functional/hash.hpp>
#include <tuple>

namespace std
{

template<typename... T>
struct hash<tuple<T...>>
{
    size_t operator()(tuple<T...> const& arg) const noexcept
    {
        return boost::hash_value(arg);
    }
};

}

- Вова

---

有一个警告，即在std命名空间中为元组定义哈希函数会导致未定义的行为，正如接受答案的评论中指出的那样。 - nielses

Answer 3

使用C++20，可以使用折叠表达式和通用lambda计算元组的哈希值而无需递归。我更喜欢依赖于std::hash<uintmax_t>而不是手动组合哈希值：

#include <cinttypes>
#include <cstddef>
#include <functional>
#include <tuple>

class hash_tuple {
    template<class T>
    struct component {
        const T& value;
        component(const T& value) : value(value) {}
        uintmax_t operator,(uintmax_t n) const {
            n ^= std::hash<T>()(value);
            n ^= n << (sizeof(uintmax_t) * 4 - 1);
            return n ^ std::hash<uintmax_t>()(n);
        }
    };

public:
    template<class Tuple>
    size_t operator()(const Tuple& tuple) const {
        return std::hash<uintmax_t>()(
            std::apply([](const auto& ... xs) { return (component(xs), ..., 0); }, tuple));
    }
};

- 1在sizeof(uintmax_t) * 4 - 1中是可选的，但似乎可以稍微改善哈希分布。这个类可以同时与std::tuple和std::pair一起使用。

- Vladimir Reshetnikov

---

n ^= n << (sizeof(uintmax_t) * 4 - 1); - Robin Davies

请注意，在默认哈希函数为identity的平台上，行“n ^ std::hash<uintmax_t>()(n);”将仅返回0，使得此哈希函数无用。 - wecx

使用operator,与operator+或operator^，后两者在主观上似乎更为合适。 - user3882729

Answer 4

在我的C++0x草案中，20.8.15表明哈希是针对内置类型进行专门化的（包括指针，但似乎不意味着对它们进行解引用）。看起来它还为error_code、bitset<N>、unique_ptr<T, D>、shared_ptr<T>、typeindex、string、u16string、u32string、wstring、vector<bool，Allocator>和thread::id进行了专门化。（令人着迷的列表！）

我没有使用C++0x变参函数，所以我的格式可能完全偏离轨道，但类似以下的内容可能适用于所有元组。

size_t hash_combiner(size_t left, size_t right) //replacable
{ return left + 0x9e3779b9 + (right<<6) + (right>>2);}

template<int index, class...types>
struct hash_impl {
    size_t operator()(size_t a, const std::tuple<types...>& t) const {
        typedef typename std::tuple_element<index, std::tuple<types...>>::type nexttype;
        hash_impl<index-1, types...> next;
        size_t b = std::hash<nexttype>()(std::get<index>(t));
        return next(hash_combiner(a, b), t); 
    }
};
template<class...types>
struct hash_impl<0, types...> {
    size_t operator()(size_t a, const std::tuple<types...>& t) const {
        typedef typename std::tuple_element<0, std::tuple<types...>>::type nexttype;
        size_t b = std::hash<nexttype>()(std::get<0>(t));
        return hash_combiner(a, b); 
    }
};

template<class...types>
struct tuple_hash<std::tuple<types...>> {
    size_t operator()(const std::tuple<types...>& t) {
        const size_t begin = std::tuple_size<std::tuple<types...>>::value-1;
        return hash_impl<begin, types...>()(0, t);
    }
}

这个版本实际上可以编译和运行

Yakk观察到直接专门化std :: hash 实际上不允许，因为我们正在使用一个与用户定义类型无关的声明来专门化标准库模板。

- Mooing Duck

---

如果您不知道该怎么做，请使用 left() ^ right()。请参阅 https://dev59.com/RG025IYBdhLWcg3wpHl_。但请注意，XOR并不总是正确的选择。如果您预计元组包含重复成员，则使用纯加法可能会更好。这可能是为什么没有标准哈希用于元组的原因。 - Alexandre C.

元组不可哈希肯定是一个疏忽，但现在已经太晚了，无法对标准进行修改 :( - Leo Goodstadt

哦，我刚才才注意到：“不使用变参模板？”糟糕。答案是否定的，不能对所有元组执行此操作，因为元组是一种变参模板类型。 - Mooing Duck

“^”和“+”均满足交换律，因此它们不适合用于合并哈希。考虑一下std::unordered_set<std::tuple<int, int, …>>如何处理{1, 2, …, 10}的排列。相反，请使用非交换的组合器，例如m * left + right，其中m是一个大奇数。 - Marcelo Cantos

专门为您不拥有的类型定制hash意味着您的程序是不完整的。而且您并不拥有所有的hash<tuple<Ts...>>。此外，使用^作为哈希组合器是非常糟糕的。 - Yakk - Adam Nevraumont

Answer 5

如果你想以简单的方式完成，只需执行：

std::unordered_map<std::tuple<int, int>, std::string, boost::hash<std::tuple<int, int>>> mp;

- Ravi Kumar Yadav