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

Question

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

SO中的这个问题为所有STL容器提供了通用打印功能.虽然你可以拥有它,为什么你不能像Hash函数那样定义一切？是的,一个重要的问题是它需要快速有效.

我正在考虑这样做转换的关键值一个简单的哈希函数size_t,做像一个简单的功能这个.

可以这样做吗？

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的"范围哈希"所做的,但是通过使用组合功能可以直接做到这一点.

一旦你完成了你的范围编辑,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 */
}

如果你想模仿漂亮的打印机,你甚至可以做一些更极端的事情并专注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;