0

構造体をキーとしてunordered_mapを使用したいのですが、順序付けは必要ないためです。しかし、ハッシュ関数をすべて使用することはできません。

副次的な質問として..pplが順序付けされていないマップと順序付けられたマップを比較するとき、ハッシュ関数について話すことはありません。悪いハッシュ関数を使用すると、順序付けされていないマップがマップよりも遅くなりますか？（ハッシュ関数のみによる）

struct exemple{

  unsigned char a,b,c;
  unsigned int n;

  bool operator == ( const exemple & other) const {..}
};

namespace std {
template <>
struct hash<exemple> : public std::unary_function<const exemple &, std::size_t>
{
    inline std::size_t operator()(const exemple & exemple_p ) const
    {
        return 0;// what do I do
    }
};

}

-edit- a、b、cは、値'a'、'b'、'c'、または'd'のみを持つことができ、nは約3から60まで変化します。

4

4 に答える 4

4

ハッシュ関数で何をするかは、取得した値に依存し、必ずしもその型に依存するわけではありません。4 つのデータ メンバーすべてに均等に分散された各値が含まれている場合、2 つの文字を に結合し、2unsigned longつの値を xor した結果を返します。

typedef unsigned long ulong;
return n ^ (ulong(a << 16) | ulong(b << 8) | ulong(c));

確かにハッシュ関数です。それがうまく機能するかどうかは別の問題です。結果を と組み合わせることもできますstd::hash<unsigned long>。

于 2012-11-15T00:26:12.337 に答える
2

ベースラインのハッシュ関数は次のとおりです。

unsigned long long h = (n << 24) | (a << 16) | (b << 8) | c;
return std::hash(h);

つまり、メンバーを にパックしてunsigned long longから、作業を にオフロードしstd::hashます。int幅が 32 ビットで 64 ビットの一般的なケースではlong long、char が負でないことを前提として、オブジェクト内のすべての情報をハッシュに使用します。

于 2012-11-15T00:24:18.000 に答える
2

struct全体として、バイトの文字列（正確には7）であると考えてください。これらの 7 バイトに対しては、許容可能な一般的な文字列ハッシュ関数を使用できます。あなたの例に適用されたFNV（Fowler/Noll/Vo）の一般的なビット文字列ハッシュ関数は次のとおりです（指定されたハッシュファンクタークラス内）：

inline std::size_t operator()(const exemple& obj ) const
{
  const unsigned char* p = reinterpret_cast<const unsigned char*>( &obj );
  std::size_t h = 2166136261;

  for (unsigned int i = 0; i < sizeof(obj); ++i)
    h = (h * 16777619) ^ p[i];

  return h;
}

exemple構造体 ( obj) への参照をポインタに変換して、構造体const unsigned charのバイトに 1 つずつアクセスできるようにしたことに注意してください。これを不透明なバイナリ オブジェクトとして扱います。sizeof(obj)コンパイラのパディングに応じて、実際には 7 ではなく 8 になる可能性があることに注意してください(これは、おそらくcとの間の構造体のどこかにガベージ パディング バイトがあることを意味しnます。必要に応じて、ハッシュ関数を書き直してa、b、 、cおよびn順番に (または任意の順序で) のバイト。これにより、struct.

はい、悪いハッシュ関数はunordered_mapよりも遅くなる可能性がありますordered_map。上記の FNV ハッシュのような一般化された高速アルゴリズムは、 を使用する人によって使用されると想定されているため、これは常に議論されるわけではありません。そのようなunordered_map場合、一般にはコンテナの要素を反復処理する能力を犠牲にしてunordered_mapよりも高速です。ordered_map順番に。ただし、はい、データには適切なハッシュ関数を使用する必要があり、通常はこれらのよく知られたハッシュの 1 つを使用するだけで十分です。exempleただし、最終的には、入力データ (ここでは構造体の内容) の分布に応じて、すべてのハッシュ関数に弱点があります。

一般化されたハッシュとハッシュ関数の例についての良い議論は、私があなたに与えたものと同様の C スタイルの FNV ハッシュを含むEternally Confuzzledで見つけることができます。

于 2012-11-15T01:03:04.973 に答える