std::hash 具有任意数量基本类型属性的对象变体

Question

讨论：

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

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

我知道我必须为它定义一个 hasher-functor，例如：

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

然后将我的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);
}

问题：

他们试图通过在 std::hash.
是否存在"official scheme"到std::hash具有任意数量的基本类型属性的对象？

Answer 1

一个简单的 xor 是对称的，并且在多次输入 "same" 值（hash(a) ^ hash(a) 为零）时表现不佳。有关详细信息，请参阅 here。

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

没有"official scheme"解决这个问题

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

它首先通过 ADL 找到 hash(t)，如果失败则检查它是否在辅助命名空间（用于 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 移动到 tuple，然后使用 hasher::hash 的 std::tuple 重载来获得结果。

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

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

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

Answer 2

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

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

主要思想是使用相同的哈希函数及其状态来哈希多个 value/element/member。

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

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;

std::hash 具有任意数量基本类型属性的对象变体

std::hash variations of object with arbitrary number of attributes of fundamental type

c++

hash

unordered-map

c++11

stdhash

讨论：

问题：