3

討論：

たとえば、キーとして使用したい任意の数の属性を持つstruct/があるとします。classstd::unordered_map

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

ハッシュファンクターを定義する必要があることはわかっています。たとえば、次のようになります。

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

そして、 mystd::unordered_mapを次のように定義します。

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

しかし、私を悩ませているのは、 の呼び出し演算子を定義する方法ですFooHasher。私も好む傾向があるそれを行う1つの方法は、を使用すること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

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 に答える