pair<int, int> 向量的散列函数

Question

我正在尝试为 vector< pair < int,int> >实现unordered_map。由于没有这样的默认哈希函数，我试着想象一个我自己的函数：

struct ObjectHasher
{
  std::size_t operator()(const Object& k) const
  {
    std::string h_string("");
    for (auto i = k.vec.begin(); i != k.vec.end(); ++i)
    {
      h_string.push_back(97+i->first);
      h_string.push_back(47); // '-'
      h_string.push_back(97+i->second);
      h_string.push_back(43); // '+'
    }
    return std::hash<std::string>()(h_string);
  }
};

主要思想是将整数列表（例如( (97, 98), (105, 107) )更改为像"a-b+ik"这样的格式化字符串，并通过 hash < string >() 计算其哈希值） . 我选择了 97、48 和 43 数字，只是为了让哈希字符串在我的测试期间可以轻松地显示在终端中。

我知道这种函数可能是一个非常幼稚的想法，因为一个好的散列函数应该是快速和强大的对抗冲突。好吧，如果给 push_back() 的整数大于 255，我不知道会发生什么......那么，您如何看待以下问题：

• (1) 我的函数可以用于大整数吗？
• (2) 我的功能是否适用于所有环境/平台？
• (3) 我的函数是否太慢而不能成为散列函数？
• (4) ... 你有什么更好的吗？

Answer 1

您所需要的只是一个“散列”整数的函数。你可以从 boost 中窃取这样的函数：

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

现在你的功能很简单：

struct ObjectHasher
{
  std::size_t operator()(const Object& k) const
  {
    std::size_t hash = 0;
    for (auto i = k.vec.begin(); i != k.vec.end(); ++i)
    {
      hash_combine(hash, i->first);
      hash_combine(hash, i->second);
    }
    return hash;
  }
};