C++ unordered_map でカスタムクラス型をキーとして使用する質問する

Question

std::unordered_mapユーザー定義のキータイプで（または他の順序なし連想コンテナーのいずれか）を使用できるようにするには、次の 2 つのことを定義する必要があります。

ハッシュ関数。これは、キータイプのオブジェクトを指定したハッシュ値をオーバーライドして計算するクラスである必要がありますoperator()。これを行うための特に簡単な方法の 1 つは、std::hashテンプレートをキータイプに合わせて特化することです。
等価性の比較関数。ハッシュでは、ハッシュ関数が常にすべての異なるキーに対して一意のハッシュ値を提供するという事実に依存できないため（つまり、衝突に対処できる必要がある）、2 つのキーを比較して完全に一致するかどうかを調べる方法が必要です。これは、をオーバーライドするクラスとして、operator()またはの特殊化として実装できますstd::equal。最も簡単な方法は、operator==()（既に行ったように）キータイプをオーバーロードすることです。

ハッシュ関数の難しさは、キータイプが複数のメンバーで構成されている場合、通常はハッシュ関数で個々のメンバーのハッシュ値を計算し、その後何らかの方法でそれらをオブジェクト全体の 1 つのハッシュ値に結合することです。優れたパフォーマンス (つまり、衝突が少ない) を得るには、個々のハッシュ値をどのように結合するかを慎重に検討して、異なるオブジェクトに対して同じ出力が頻繁に得られないようにする必要があります。

ハッシュ関数のかなり良い出発点は、ビットシフトとビット単位の XOR を使用して個々のハッシュ値を結合するものです。たとえば、次のようなキータイプを想定します。

struct Key
{
  std::string first;
  std::string second;
  int         third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};

これは簡単なハッシュ関数です（ユーザー定義ハッシュ関数の cppreference の例):

template <>
struct std::hash<Key>
{
  std::size_t operator()(const Key& k) const
  {
    using std::size_t;
    using std::hash;
    using std::string;

    // Compute individual hash values for first,
    // second and third and combine them using XOR
    // and bit shifting:

    return ((hash<string>()(k.first)
             ^ (hash<string>()(k.second) << 1)) >> 1)
             ^ (hash<int>()(k.third) << 1);
  }
};

これを設定すると、std::unordered_mapキータイプのをインスタンス化できます。

int main()
{
  std::unordered_map<Key,std::string> m6 = {
    { {"John", "Doe", 12}, "example"},
    { {"Mary", "Sue", 21}, "another"}
  };
}

std::hash<Key>ハッシュ値の計算には上記で定義されたが自動的に使用され、等価性チェックにはoperator==のメンバー関数として定義されたが使用されます。Key

名前空間内でテンプレートを特殊化したくない場合はstd(この場合は完全に合法ですが)、ハッシュ関数を別のクラスとして定義し、マップのテンプレート引数リストに追加できます。

struct KeyHasher
{
  std::size_t operator()(const Key& k) const
  {
    using std::size_t;
    using std::hash;
    using std::string;

    return ((hash<string>()(k.first)
             ^ (hash<string>()(k.second) << 1)) >> 1)
             ^ (hash<int>()(k.third) << 1);
  }
};

int main()
{
  std::unordered_map<Key,std::string,KeyHasher> m6 = {
    { {"John", "Doe", 12}, "example"},
    { {"Mary", "Sue", 21}, "another"}
  };
}

よりよいハッシュ関数を定義するにはどうすればよいでしょうか。前述のように、衝突を回避し、良好なパフォーマンスを得るには、適切なハッシュ関数を定義することが重要です。本当に優れたハッシュ関数を定義するには、すべてのフィールドの可能な値の分布を考慮し、その分布を可能な限り広く均等に分散された可能な結果の空間に投影するハッシュ関数を定義する必要があります。

これは難しいかもしれません。上記の XOR/ビットシフト法は、おそらく悪いスタートではありません。もう少し良いスタートを切るには、 Boost ライブラリの関数テンプレートhash_valueとhash_combine関数テンプレートを使用できます。前者は標準型 (最近はタプルやその他の便利な標準型も含まれるようになりました) と同様に動作しますstd::hash。後者は、個々のハッシュ値を 1 つに結合するのに役立ちます。以下は、Boost ヘルパー関数を使用するハッシュ関数の書き直しです。

#include <boost/functional/hash.hpp>

struct KeyHasher
{
  std::size_t operator()(const Key& k) const
  {
      using boost::hash_value;
      using boost::hash_combine;

      // Start with a hash value of 0    .
      std::size_t seed = 0;

      // Modify 'seed' by XORing and bit-shifting in
      // one member of 'Key' after the other:
      hash_combine(seed,hash_value(k.first));
      hash_combine(seed,hash_value(k.second));
      hash_combine(seed,hash_value(k.third));

      // Return the result.
      return seed;
  }
};

以下は、ブーストを使用せずにハッシュを結合する適切な方法を使用した書き直しです。

template <>
struct std::hash<Key>
{
    std::size_t operator()( const Key& k ) const
    {
        // Compute individual hash values for first, second and third
        // http://stackoverflow.com/a/1646913/126995
        std::size_t res = 17;
        res = res * 31 + hash<string>()( k.first );
        res = res * 31 + hash<string>()( k.second );
        res = res * 31 + hash<int>()( k.third );
        return res;
    }
};

Answer 1