c++ - 所有 STL 容器的通用哈希函数

Question

我正在使用 std::unordered_map<key,value>在我的实现中。我将使用任何 STL 容器作为 key 。我想知道是否可以为任何正在使用的容器创建一个通用的哈希函数。

This SO 中的问题为所有 STL 容器提供通用打印功能。虽然你可以拥有它，但为什么你不能拥有定义一切的哈希函数之类的东西？是的，一个大问题是它需要快速高效。

我正在考虑做一个简单的哈希函数，将键的值转换为 size_t并做一个简单的功能，如 this .

这可以做到吗？

PS:请不要使用boost图书馆。谢谢。

Answer 1

我们可以通过模仿 Boost 并组合哈希来得到答案。

警告:组合散列，即从事物的许多散列中计算出许多事物的散列，通常不是一个好主意，因为生成的散列函数在统计意义上并不“好” .许多事物的正确哈希应该从所有成分的整个原始数据构建，而不是从中间哈希构建。但目前还没有一个很好的标准方法来做到这一点。

无论如何:

首先，我们需要hash_combine 函数。由于超出我理解的原因，它没有包含在标准库中，但它是其他一切的核心:

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 的“范围散列”所做的，但您可以直接使用 combine 函数自行实现。

一旦你完成了范围哈希器的编写，只需专门化 std::hash 就可以了:

namespace std
{
  template <typename T, class Comp, class Alloc>
  struct hash<std::set<T, Comp, Alloc>>
  {
    inline std::size_t operator()(const std::set<T, Comp, Alloc> & s) const
    {
      return my_range_hash(s.begin(), s.end());
    }
  };

  /* ... ditto for other containers */
}

如果你想模仿 pretty-print ，你甚至可以做一些更极端的事情，并为所有容器专门化 std::hash，但我可能会更小心地做一个明确的容器的哈希对象:

template <typename C> struct ContainerHasher
{
  typedef typename C::value_type value_type;
  inline size_t operator()(const C & c) const
  {
    size_t seed = 0;
    for (typename C::const_iterator it = c.begin(), end = c.end(); it != end; ++it)
    {
      hash_combine<value_type>(seed, *it);
    }
    return seed;
  }
};

用法:

std::unordered_map<std::set<int>, std::string, ContainerHasher<std::set<int>>> x;