3

讨论：

假设我有一个struct/class具有任意数量的属性，我想将其用作 a 的键，std::unordered_map例如：

struct Foo {
  int    i;
  double d;
  char   c;
  bool   b;
};

我知道我必须为它定义一个哈希函子，例如：

struct FooHasher {
  std::size_t operator()(Foo const &foo) const;
};

然后将 my 定义std::unordered_map为：

std::unordered_map<Foo, MyValueType, FooHasher> myMap;

不过，困扰我的是如何为FooHasher. 我也倾向于喜欢的一种方法是使用std::hash. 但是，有许多变化，例如：

std::size_t operator()(Foo const &foo) const {
  return std::hash<int>()(foo.i)    ^
         std::hash<double>()(foo.d) ^
         std::hash<char>()(foo.c)   ^
         std::hash<bool>()(foo.b);
}

我还看到了以下方案：

std::size_t operator()(Foo const &foo) const {
  return std::hash<int>()(foo.i)           ^
         (std::hash<double>()(foo.d) << 1) ^
         (std::hash<char>()(foo.c)   >> 1) ^
         (std::hash<bool>()(foo.b)   << 1);
}

我还看到有些人添加了黄金比例：

std::size_t operator()(Foo const &foo) const {
  return (std::hash<int>()(foo.i)    + 0x9e3779b9) ^
         (std::hash<double>()(foo.d) + 0x9e3779b9) ^
         (std::hash<char>()(foo.c)   + 0x9e3779b9) ^
         (std::hash<bool>()(foo.b)   + 0x9e3779b9);
}

问题：

  1. 他们试图通过在结果中添加黄金配给或移位来实现什么std::hash。
  2. 对于具有任意数量的基本类型属性的对象是否有“官方方案” ？std::hash
4

2 回答 2

7

一个简单的异或是对称的，并且在多次输入“相同”值（hash(a) ^ hash(a)为零）时表现不佳。有关更多详细信息，请参见此处。

这是组合哈希的问题。 boost有一个相当不错的 hash_combine。编写一个哈希组合器，并使用它。

没有“官方方案”来解决这个问题。

我自己，我通常会写一个超级哈希器，它可以接受任何东西并对其进行哈希处理。它散列自动组合元组、对和集合，首先散列集合中元素的计数，然后散列元素。

它hash(t)首先通过 ADL 查找，如果失败，则检查它是否在辅助命名空间（用于std容器和类型）中有手动编写的哈希，如果失败则执行std::hash<T>{}(t).

然后我的支持哈希Foo看起来像：

struct Foo {
  int    i;
  double d;
  char   c;
  bool   b;
  friend auto mytie(Foo const& f) {
    return std::tie(f.i, f.d, f.c, f.b);
  }
  friend std::size_t hash(Foo const& f) {
    return hasher::hash(mytie(f));
  }
};

我mytie用来移动Foo到 a 的地方tuple，然后使用 of 的std::tuple重载hasher::hash来获得结果。

我喜欢结构相似类型的哈希具有相同哈希的想法。这让我表现得好像我的哈希在某些情况下是透明的。

请注意，以这种方式散列无序喵是一个坏主意，因为无序喵的不对称哈希可能会产生虚假的未命中。

（喵是地图和集合的通用名称。不要问我为什么：问STL。）

于 2016-05-25T10:01:41.353 回答
5

标准哈希框架在组合哈希方面缺乏。使用组合散列xor是次优的。

N3980 "Types Don't Know #"中提出了更好的解决方案。

主要思想是使用相同的散列函数及其状态来散列多个值/元素/成员。

使用该框架，您的哈希函数将如下所示：

template <class HashAlgorithm>
void hash_append(HashAlgorithm& h, Foo const& x) noexcept
{
    using std::hash_append;
    hash_append(h, x.i);
    hash_append(h, x.d);
    hash_append(h, x.c);
    hash_append(h, x.b);
}

和容器：

std::unordered_map<Foo, MyValueType, std::uhash<>> myMap;
于 2016-05-25T10:38:17.527 回答